NTCIR 14 QA poliinfo Segmentation

NTCIR 14 の論文含め終わったようなのでまとめます．

当方は，インターンで segmentation に関わった程度です． 論文までは関わってないのでカンファレンスには参加していませんが，どれに関わっていたかは読めばわかってしまうかも．半分は2018/08のインターン参加報告ですね．

とりあえず，segmentation について書いて，summarization と classification は興味があればという感じです．

NTCIR について

NII Testbeds and Community for Information access Research の略だそうです． NII の project の1つということみたいですね．

こういった試みとしては， SemEval - Wikipedia は知っていましたが，NTCIR は正直知りませんでした．

今週行われた NTCIR-14 の QA のタスクに関する詳細はこちらにあります． https://poliinfo.github.io/NTCIR-14-QALab-PoliInfo-4thRoundTableMTG.pdf また，論文形式でも自然言語処理学会で発表されたようです． https://www.anlp.jp/proceedings/annual_meeting/2019/pdf_dir/C2-2.pdf

これらについては，github でも公開されており，議論には応じたいとどこかで見た気がします． github.com

segmentation task について

スライドに基づいて説明していきます．

このタスクでは 入力を議会会議録に含まれる「発言」と要約の「制限字数」と「議会会議録」として，引用を理解するために読むべき発言の範囲（「開始行」「終了行」）を予測します．

発言と要約についてはこのようになっています．

Segmentation Task

先ほどの発言者，要約，日付等の譲歩が json 形式で配られ，それらが書かれている行数を当てようという感じです．

予測

また，今回の場合は東京都議会を対象としているため，こちらのページで閲覧可能です． www.gikai.metro.tokyo.jp こんな感じで取れます．time sleep については robots.txt には記述なし？？？怒られたくないので，10で書いてます． https://github.com/jackee777/some_codes/blob/master/crawling/tokyo_meeting/scrape_tokyo_info.ipynb

スライドの例ですと， 平成二十三年東京都議会会議録第八号がそれに当たります．

どうやら，村上英子氏の発言の前半部分というのが正解のようです．

まとめると

1. 「Date」と「Meeting」の情報から会議録を「平成二十三年東京都議会会議録第八号」に限定
2. 「*Speaker」から発言の候補の抜出
3. 「*Summary」等から，該当する発言箇所について導出

みたいな感じです．

例としては

1. 「23-6-23」と「平成23年_第２回定例会」の情報から会議録を「平成二十三年東京都議会会議録第八号」に限定
2. 「村上英子（自民党）」から「村上英子」氏の発言の抜出
3. 「国難のもとにおける東京の役割について～」等から，該当する発言箇所「初めに、東日本大震災～二つの課題に、（中略）知事の所見をお伺いいたします。」について導出

このタスクを解く利点については，膨大な議事録から該当箇所を容易に得られることだと思います． 確かに，議事録すべてを読むのは心が折れます．「〇月〇日に知事が～～って言ってた」などと言われても，はあ・・・調べんの嫌だなあって感じです．

このタスクの難しい点としては

• 東京都議会側の回答者は複数回登壇する点
• 一つの質問，一つの回答がひじょーーーーに長い点
• 該当箇所の1文は比較的容易にわかるが，「引用を理解するために読むべき発言の範囲」は容易ではない点（precision の方が簡単で，recall の方が難しい）

です．

今後の発展としては，１．２．で与えられている情報を使わないことが考えられます． 正直言ってしまうと，回答者は難しいですが，質問者については現在与えられている情報があれば 該当箇所を見つけることはそこまで難しくないというのが理由です．

実際問題，「〇月〇日に知事が～～って言ってた」とまで明確に言うのは学術系の人間くらいでは？と思います． 一般の人は「なんかチラッとTV見てたら※※って言ってたような・・・」みたいな情報としても微妙だし，喜怒哀楽も取れない文が全然ある気がします．

逆に，そういったちょっとした情報から，都議会議員の発言と都民の感情を結びつけることができれば，非常に意味のあるタスクになるなと感じています（これはこのタスクが現状意味がないという意味ではなく，より良いタスクへの方向性がいくつか考えられるという意味です）．

データについて

github を見るのが早いですが，先ほどの json と行ごとに区切った都議会の文章が渡されます． 行ごとに区切ったものを配布するのは公平性のためだと思います．

training 用の json は合計で298個あり，訓練データは298個しかないことになります．8月のインターン時にはもっと少なくて，機械学習なんて無理ぽよって思いました．

test 用の json は合計で82個あり，これらは非公開でした．多分

加えてですが，会議録では同じフレーズが使いまわされることが多いようです． 例としてはこんなです．

• 文頭には，「まず」や「次に」といった接続詞
• 質問時には，「を伺います」などのフレーズ
• 回答時には，「検討してまいります」や「対応してまいります」などのフレーズ

件数を見るとすぐわかるのですが，質問に比べると回答の方が多岐にわたることが分かります． この点においても，回答の方が抽出が難しいことがわかります．

一応，見れるようにしておきました． https://github.com/jackee777/some_codes/blob/master/crawling/tokyo_meeting/check_NTCIR14/check_NTCIR.ipynb

評価指標について

Precision, Recall, F値です．※F値は github 上にはなく，Formal Run ではある感じです．

github では次のようにあります．

• Precision列: [一致] / [解答範囲が表す個数]（Question と Answerを合わせたもの）
• Recall列: [一致] / [正解範囲が表す個数]（Question と Answerを合わせたもの）

※一致というのは解答（予測）行数が80~89であり，正解行数が85~90であれば，85~89が一致となります． この時

• Precision = (89-85+1) / (89-80+1)
• Recall = (89-85+1) / (90-85+1)

となります．

Formal Run の結果

NTCIR_Formal_RUN_結果

https://poliinfo.github.io/NTCIR-14-QALab-PoliInfo-5thRoundTableMTG.pdf

NAMI の結果が分かりやすいですが，解答行数が少ないほど Precision は出しやすいので，解答範囲によって Precision と Recall が trade off します

論文について

RICT，NAMI と KSU について見ることにしました（F値 0.8 越えしてたもの）． 後ろ2つの解説はちょっとサボったのもありますが，図が見やすかったので，それで十分というのが強いです．

各論文はこちらからhttp://research.nii.ac.jp/ntcir/workshop/OnlineProceedings14/NTCIR/toc_ntcir.html

RICT

http://research.nii.ac.jp/ntcir/workshop/OnlineProceedings14/pdf/ntcir/02-NTCIR14-QALAB-YongJ.pdf by リコー

Introduction 要約と文章を対応させることは必須ではないが，一部の文章だけを抜粋してしまうと誤解を招く恐れがある．そこで，segmentation step と search step という2段階で解くことで考えることにした．

• segmentation step: 会議録をトピック毎に分割
• search step: 要約に相応しい segment を分割した segment の中から探索

概要 * データの用意

与えられたデータは，segment 用にはできてなかったため，自分たちでラベル付けして training と test 用に分割

• segmentaion step について

dry run （formal run の前にあったテスト）では，segmentation には nltk の TextTilling *1を使っていたけれども，従来の segmentation では要約にある手掛かりとなるフレーズが分割に使われていなかった．そこで formal run では手掛かりとなるフレーズが使われる手法をいくつか試した．

segmentation を解くにあたって，分割するかしないかの2クラス分類として問題を解いた． 手法はいくつかあって

1. ルールベース

   

   RICT_segmentation_rule

2. 分割候補の前後10単語（計20単語）を入力とする SVM．入力ベクトルは BoW を Latent Semantic Indexing で100次元に圧縮したもの

3. semi supervised ここだけはかなり厄介なことをしている．次のようなことを繰り返す． （１）すでに分割されている箇所に基づき，分類器を学習（２）分類器によって分割（３）分割数に基づき，negative を適切にサンプリング これを繰り返すことで，最終的に分割することができる．分類器には Logistic 回帰と SVM を用いた模様． すなわち，正解を作り出しながら，再帰処理的なことをしているぽい．賢い． ※一番最初の分割は「話者」．議事録上で分割されている

4. なんもしない

5. LSTM 前後の文の「前10単語後10単語」の計20単語を入力とする LSTM．入力ベクトルは100次元の word2vec

6. HAN https://www.cs.cmu.edu/~./hovy/papers/16HLT-hierarchical-attention-networks.pdf formal run の後に走らせたらしい．入力は LSTM と同じだが，embedding 層，attention 機構，双方向の GRU を使った NN．

HAN

• search step について

dry run では，e Amazon Elasticsearch Service を使っていたが，要約の中には”[1]〇〇について[2]××について”という複数の segment からなるものがあったため，必要以上に segment が連なってしまっていた．閾値の設定が難しかったため，自ら実装したものを使用．

実装はシンプルな確率モデルでなされ，summary 中の単語が文章に連続して現れる確率を計算して導出． （ちょっと疲れたので略）

結果 * segmentation の結果 rule base が最も良いが，SVM と HAN も強い

RICT_segmentation_result

• formal run に対する結果（平均） segmentation の結果とほぼ相関があり，HAN が強い segmenta

  

  RICT_formal_result

まとめ semi-supervised のところも検証されてたりする．気になる方は見てください．

• segmentation task に手掛かりとなるフレーズを導入することに成功
• rule base が最も良かったが，機械学習による手法も同じくらいの精度を達成
• semi-supervised の手法を使えば，ラベルを振らなくても済むかもしれない
• こういった手法の benchmark になるのでは

感想 個人的には，試したものが多かった．考え方はほとんど同じで，自分も2段階だなと思ったし，classification task として解こうということも同じだった． （参加したのはここではないが，自分は前後の文を入力にした LSTM を組む直前でインターンが終わってしまったので，仕方なく Random Forest を組んだが．あと，GRU は？データ少ないし，パラメータの少ない GRU の方が強かったのでは？という疑問も試してくれていて良かった．）

著者としても，semi-supervised が推しなのかな？とは思ったのと，semi-supervised が一番面白いと思った．

NAMI

http://research.nii.ac.jp/ntcir/workshop/OnlineProceedings14/pdf/ntcir/15-NTCIR14-QALAB-YokoteK.pdf by 日立

概要

1. 役職の検知（会議録の冒頭等に情報がある）
2. 発話者の対応付けによる segment の絞り込み（誰に対しての会話かを検知）
3. クエリの再構築

4. オントロジーに基づくクエリの拡張

   

   NAMI_概要

5. クエリに基づいて全組み合わせを探索 カバレッジ（cov），出現頻度（occ），チャンクサイズ（chu）の長さの3つの評価軸を用意し，文章を評価している（効果的には，簡易的なアンサンブル？）．

   

   NAMI_Q_数式

結果 一番，F値が上がった場合だが，query の拡張が効果を示していることがわかる．

NAMI_result

感想 クエリを拡張することで recall が改善していることから，単語の置き換えを検出することで，summary の情報の網羅性が上がると考えられる．よくよく考えると，この手法だけ segment の境界についてはあまり触れていないので，recall と segment の正確さの関係性が気になると思いました．

＜追記＞ この手法ですが，オントロジーを使わなくてもクエリの拡張というのは可能という点で，最も他のサービスには使いやすいのでは？と思います．実際，私は学部4年生に対して「難しいことをやる前に，今のあなたにもできる単語ベースなところからやってみては」と提案しました．最近の多くの手法では，文単位の similarity を取る例は多いですが，容易な technique である doc2vec などでは目的の意味での文章の類似度を取れないことがあるかと思います．そういった場合には簡易的な用法として，単語ベースな手法は十分に聞くかと思います．例えば，tf-idf の重みと word2vec のベクトルを組み合わせて文章ベクトルを得る手法が論文としても出ていたと思います（気になる方は How to get vector for a sentence from the word2vec of tokens in sentence - Stack Overflow や 文書ベクトルをお手軽に高い精度で作れるSCDVって実際どうなのか日本語コーパスで実験した(EMNLP2017) - Qiita を参考にしてください）．

KSU

http://research.nii.ac.jp/ntcir/workshop/OnlineProceedings14/pdf/ntcir/12-NTCIR14-QALAB-KimuraT.pdf by 京都産業大学

概要

1. 質問と回答の分割
2. 日付と Speech Type (ST) によるフィルタリング（質問，回答，報告，まとめ，etc）
3. SD から抜き出す際に Speaker Filtering を適用（話者の限定．例外あり）
4. 単語頻度（WF）によるテキストの大まかな分割*2
5. ルールベース（RB）による segmentation 範囲の決定

   

   KSU_概要

上でいう4がstage1，5がstage2です．

KSU_イメージ

結果 * スピーカーのフィルタリング（SF）は非常に有効 * 単語頻度による境界の決定（WF）とルールベースによる境界の決定（RB）はどちらも効果を示したが，RB の方が

KSU_result

感想 一文を当てる制度は非常に高かったことが見て取れますが，質問者側の精度がよろしくなかったみたいですね．単語頻度による分割は読みながら，RICT にもあったように上手くいかなそうだなと思ったので，そんな感じでした．ただ，単語頻度による分割をしたときは precision が異様に高いので，segment が大きいと starting point が間違いやすかったのかなあなんて思いました（わからぬ）．

Discussion（個人的な感想）

先に，こうでも良いなあと思ったことを書きます．

• NTCIR についてのところで書きましたが，「日付」，「議会名」，「発言者」の情報がない場合についても検証
• データ数の増加（データが少ないので，機械学習とルールベースのどちらが良いのか議論の余地が残るのではと感じました）
• 参加者の増加
• 正解に関する一貫性の担保（引用を理解するために読むべき発言の範囲が人によって違う）

最後のところだけ補足すると，「引用を理解するために読むべき発言の範囲」というのは曖昧で，わざと曖昧にしているのかなとも思いました．

若輩者が言うのは申し訳ないですが，この曖昧性は予測モデルの設計の上では非常に重要なのではないか？と思いました． 具体的には，「それでは、都議会公明党を代表して質問いたします。」は「日本観測史上最大のマグニチュード九を～」と続くのですが，この「日本観測史上最大のマグニチュード九を～」から切り取っている箇所もあるのではと思いました．

おそらく，タスク全体に影響を及ぼすほどではないとは思いますが．それも含めて，結構難しいなあと思いました．

まとめ

そもそも，このページを書こうと思ったのが，RICT で LSTM のフレーズを見たからなので，RICT の論文はとても面白かったです． ルールベースが一番いいのはわかっているから，それをどうするかというのは正しいように思います．

（一方で，ルールベースでできるものをわざわざ機械学習でやる意味というのも考える必要はあるんだと思いますが，ちゃんと時間をかけて作ったルールベースに勝てるのかな？というのは疑問です）

なんというか山本さんの

研究者としての私の思いです。これを書いた時点ですでに退職を決めていました。当時、ちょうどいいタイミングで執筆依頼をいただいたなと思っていました。
山本 和英. 知識を書こう. 自然言語処理, Vol.24, No.4, pp.521-522, 言語処理学会 (2017.9)https://t.co/YBszXzA4Lv

— 山本 和英 (@y8o) 2019年6月10日

を見た後だと色々考えてしまいます．

RICT に釣られて読みましたが，応用タスクも面白いですよね． こうして，ブログも書けるしインターンが無駄な時間でなくてよかったと思います（インターン先には落ちたので笑笑）．

属性的には，質問と回答で分けているものはありましたけど，モデル全体として質問と回答で分けた例はなかったのかな？とふと思いました．

*1:http://kesin.hatenablog.com/entry/2013/07/23/%E3%83%86%E3%82%AD%E3%82%B9%E3%83%88%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%86%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E7%A0%94%E7%A9%B6%E7%B4%B9%E4%BB%8B

*2:https://pdfs.semanticscholar.org/4b5a/3e77fa3ca6b2cf91cda4e602bdf2ad3e9969.pdf

AtCoder の D からが難しい

最近思うのだが，300 点問題が解けて，400 点問題が死ぬ
(diverta のはほぼ解けたけど，あれは企業コンだし点数はね)

解けない理由はわかっていて，グラフ問題が全部解けない．幅優先探索と深さ優先探索の違いしか分からないので，非常に辛いなあ・・・

本職は自然言語処理だけども，ネットワーク分析とかに役立つのかなあ？形態素解析が一番近いのかな

AGC 033 A - Darker and Darker を python で

最初に言いたい・・・これ難しすぎない？？？？ python がどれだけ遅い言語かを思い知る結果となった・・・

悔しくて悔しくて，リファクタリングをしてやっと通った・・・ （30回出した・・・すまんかった）

考え方や解説をする気はないので，こちらを参照してください．

drken1215.hatenablog.com

まず，愚直に実装すると，次の2つ

1つ目はマスを順に黒くしていき，全部のマス目が黒になれば探索は終わるという話

初期の黒から距離1のマスを全部埋めるのを1回目

初期の黒から距離2のマスを全部埋めるのを2回目

・・・

初期の黒から距離nのマスを全部埋めるのをn回目

として，n を出力すればよい

queue を使う必要はないので，list でやってしまった．

H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)
 
cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_blacks = []
  for black in blacks:
    for cand in cands:
      i = black[0] + cand[0]
      j = black[1] + cand[1]
      if i >= 0 and i < H and j >= 0 and j < W:
        if L[i][j] == ".":
          L[i][j] = "#"
          next_blacks.append([i, j])
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1
 
print(result)

これだと，4/15AC

2つ目は解説通りに探索すると，こっちかなという感じ

すべてのマス目の黒からの距離を計算し，それの最大値を出す

from collections import deque
 
H, W = list(map(int, input().split()))
all_count = H * W
L = [input() for i in range(H)]
 
reached = [[-1]*W for i in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if L[i][j] == "#":
      reached[i][j] = 0
      q.append((i, j))
 
cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
  i, j = q.popleft()
  for ch, cw in cands:
    nh, nw = i + ch, j + cw
    if nh < 0 or nh >= H or nw < 0 or nw >= W:
      continue
    if reached[nh][nw] == -1:
      reached[nh][nw] = reached[i][j] + 1
      q.append((nh, nw))
    elif reached[nh][nw] > reached[i][j]:
      reached[nh][nw] = reached[i][j] + 1
 
result = max([max(reached[i]) for i in range(H)])
print(result)

こっちは3/15AC

うん・・・まあ，到底間に合わないのだ・・・ 山ほど試したが，試したことを書くと大変そうなので，抜粋

15/15 AC となったコードと工夫点

• name == "main" の使用
• 代入式の削減と比較式の削減
• 黒マスのカウントの廃止
• for 文の廃止

name == "main" の方が速いのは知られていると思うので，触れない（正確な理由を知らないし）

代入式の削減と比較式の削減について

if reached[nh][nw] == -1: は基本遅い．今回は訪れたかどうかの True or False で十分 reached[nh][nw] = reached[i][j] + 1 も True を代入して終わり

黒マスのカウントの廃止

黒マスをカウントしなくても，重複なしで queue に値をいれてけば，q が空になって自然に終わる

for 文の廃止

最初からこれをやれば良かったのでは？と思うくらい速くなった． for 文で 4方向回すのをやめて地道に書いた．python の for が遅いのは知っていたが，ここまでとは・・・

これらを実装すると

from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()

13/15 AC となったコードと工夫点

これも結構工夫したので，通らなくてすごい悲しかった・・・

• name == "main" の使用
• 代入式の削減と比較式の削減
• 4方向を見た際の重複の廃止
• 2次元配列がダメかな？と思ったので1次元配列に

各マスに対して4方向見ていくため，見るべき箇所には基本的に重複箇所が生まれる． そこで，見るべき箇所をユニークにして，比較箇所を削減

2次元配列だとメモリ配置の計算で（ちょっとだけだと思うけども）損するかなと思ったので 1次元で処理

これらを実装すると

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1
 
  print(result)
 
if __name__ == "__main__":
  main()

正直言うと，15/15 よりも 13/15 のコードの方がずっと好きである．

必要なところは内包表記で処理で来ていて，コードの見直しがしやすいし if 文が縦につながるのは嫌いなので． この2つのコードの速度差は 100 ms もないと思われる． （numpy による一斉代入や内包表記での True 代入も試したが，変化せずむしろ落ちたような？） こういう問題が出たら，ちゃんと時間を見て 他の言語で通した方が良いんだろうなあと強く感じた． （ほかの方の回答も結構見たので，numpy の関数で高速化できるらしいというのは見た）

一応，python を主戦場にしつつ，cpp, java はもうちょっと練習してかないと駄目かなあと思った． python や c に比較すると，cpp, java の言語全体のイメージがわからんから書かないんですよね・・・

明日の ABC ? は出たいけど時間をさけそうにないなあ・・・灰色のまんま

diverta 2019 で D を modulo にした人

どうも，diverta 2019 で D 問題の sample 2が 999,999 ずれた人です． （C も分岐対処したつもりが，漏らしてたんですけどね．オーバーフローも初体験で動作を知らなかったし大変だった．）

999,999 ずれるのは半分はオーバーフローのせいです．半分は実装のせいです． （ここ，混乱してます・・・オーバーフローが出ていたが該当箇所を忘れたので修正）

オーバーフローの内容

999,999 ずれますが，最後に加算されたのは 1,000,000 です． オーバーフローして，加算値が 999,999 になってます． (N - i) % i == 0 を 1,000,000 は満たしますが答えの条件には一致してません． 要するに，999,999 ずれている人は 1,000,000 の排除が基本方針です．

このエラーが出た人や，moduloでやったがACでない人の解法は

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0:
    result += (N - i) / i
 
print(int(result))

なのかなあ．と思います． floor(N/m) = N %m を変形させて，(N - m) % m = 0 かなあと思って解きました． 正規の解法は N = k(m+1) なので正しいように思えますが，この解法は少し間違っているようです（出せばわかる）． 薄々気づいていた人もいると思いますが，余剰では k の値が考慮されていないというのが問題です． とりあえず，解決してしまう実装として再度チェック．

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0:
    temp = (N - i) // i
    if temp != 0 and N // temp == N % temp:
      result += temp
      
print(int(result))

はい，まあ冷静になれば漏れることはあるだろうなあって感じです． これでも AC は取れましたが非常に気持ち悪いです．

漏れる例としては N=9 の時，1, 3, 9 が候補にありますが，答えは8(=9-1)のみです． しかし， (N - i) % i == 0 では，2(=3-1)が答えに浮上します． 他にも，2, 4, 6, 12, 16 等色々なところで，これが起きます． 原因を考えると，(N - i) // i の値が i より大きいときにエラーが起きてます． （小さいケースはfor文の範囲外なので）

で，(N - i) // i > i を N について解くと，N > i ** 2 + i です． これで全部通ります．

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0 and i ** 2 + i < N:
    result += (N - i) // i
      
print(int(result))

i について解いて，range の範囲を狭めることもできると思いますが それは本気の実装かなんかかなって感じします． i について解くだけなので

import math
N = int(input())
 
result = 0
for i in range(1, math.ceil(((1+4*N)**0.5-1)/2)):
  if (N - i) % i == 0:
    result += (N - i) // i
      
print(int(result))

院進か就職か

学部3年生のイベントに駆り出されるので
院進か就職かどっちがいいかを聞かれる予定が降ってきた．
でも，その場でうまく話せる気はしないので，web に置いとけば良いかという感じ．

院進か就職かは別にどっちでもいい
ここで悩む場合，どちらにも向いている面はあるだろうと思うし，
悩まない人間は，どちらかに特化している人が多いと思う．

ただ，惰性で院や社会に進むよりかは自分で決めてやってほしいと思う．
個人的には，理由がなんとなくという人の気持ちはあまりわからんとです．
自分の院進理由は，
自分一人で物事を完結させる能力が欲しかったのと
院進せずに社会に入ったら自分を語るものが大学名と会社名になると思ったので，それだけは嫌，って感じです．

要するに，誰かではなく自分で自分を語りたいということです．まだ成れてないですが．

利点や欠点という対照的な話題ではないので，自分の思う特徴を書きます．

あえて表現するなら，自分のためか他人のためかはあるかもしれない．

違うなと思う箇所はこんな感じです．これらについて話します．

- お金

- 考え方

- 自分に使える時間

ビジネス感とか，上司との拘束時間や付き合いとか，あると思いますが，わかることだけ書きます．

お金について
- 院進は基本お金貰えません（未踏プロジェクトや大学・会社の奨学金などがあります）
- 就職すれば，お金は絶対もらえます．
GTX 1080 くらいの10万円のお買い物や高いコートなんて余裕みたいです．

考え方について
- これは研究室に寄るんでしょうが，テーマを自分で見つけて好きにやれる身としては，純粋に自分の興味だけでやれるのは大きい利点です．
- 企業では，ユーザのための開発であり，ユーザのための研究であることが多く，お金があって初めてという価値観はある程度持つ必要があります．

自分に使える時間について
- 見ての通り，自由です．研究してますが，午前4時にブログが書けます．競プロの問題も見れますし，論文も読み放題です．遊ぼうと思えば遊び放題です．
- 会社に入れば，そうではないですね．10時前に寝る人もいるみたいです．

あと，思うんですが，たかだか2年くらいでは人間差が付きません．
うさぎvsかめではなくて，自分vs自分では2年では差が付かないと思います．

自分は研究分野に対する知識，開発力，プログラミング能力，数学力，英語など全部成長したなと思います．でも，多分企業に行っても同程度の努力をしたと思うので，同じ成長を実感できたと思います．

まあ，婚期は間違いなく遅れていってるなと思う．

発表用スライドで気を付けていること

タイトル通り，パワーポイントで作成するスライドで気を付けていること，です．

個人的には，パワーポイントでスライドを作成するのが一番苦手です．
でも，最近気づいたのですが，
スライドを良くするためにマニュアルで整備していることは人の役に立つようです．
（B4の指導をしていて気づきました．）

なので，基本的にスライド製作が上手い人には見る価値がないでしょう．

以下，チェック項目です

全体のレイアウトに対する注意

• 目的とまとめは対応性があるか
• 全体を総括可能なページが1枚以上あるか
• 強調色，否定色は固定した色を使用しているか
• 定義や言葉の紹介については固定のレイアウトか
• 発表会場の環境に依存することはないか（色飛びすることはないか）

ページに対する注意

• スライド単体で意味がわかるか（切り取って話せるか）
• 一枚に1.5回程度の主張で済んでいるか
• 主語と述語が一枚で完結しているか
• 話し言葉で保管される言葉は20文字程度が良い（所感）

論文の引用に対する注意

• 前提の見逃しはないか，著者の本意から外れていないか
• 言葉の定義が自分固有のものになっていないか
• 引用のフォーマットは共通しているか

最後に

slideshare など，どこかに発表できる自信はあるか

そうでないなら，何のためのスライドなのか

こんな感じで，チェック項目を作っています．
世の中には，もっとうまい人が沢山いますが，
私みたいなスライドが苦手な人は硬いスライドの方が楽かもしれません．

個人的に好きなスライドは公開しているので，そちらも含め，少しだけ書きます．

論文形式はこんな感じです（背景，目的，関連研究，概要，詳細，実験，結果，まとめ）．

Deep residual learning for image recognition 

 

本の紹介だと，構成は本通りでパーっとやってます．

PRML 上 2.3.6 ~ 2.5.2 

適当な解説

論文紹介は，ResNet は画像系の機械学習モデルとして有名で，メインキーワードは「深い」です．
ResNet のスライドに対してはチェック項目について次のように考えてました．

• 目的とまとめは対応性があるか
  ⇒ 劣化せず，深いが共通
• 全体を総括可能なページが1枚以上あるか
  ⇒ やったことが目的だけでわかる（ResNetがシンプルなのでこれだけです）
• 強調色，否定色は固定した色を使用しているか
  ⇒  強調色は青，否定色は赤にしています．なので，スライド全体のレイアウトは青系統しか自分は使えません．
• 定義や言葉の紹介については固定のレイアウトか
• 一枚に1.5回程度の主張で済んでいるか
  ⇒ ここでは，主張をオレンジの枠で固定しています．オレンジだけわかってくれればいいやって思っています．黒の枠を使っているときは主張したくないけど大事な前置きとかです．
• 話し言葉で保管される言葉は20文字程度が良い（所感）
  ⇒ 目的の場合は，図のところだけ口頭で捕捉します．まとめに関してはスライドにある事しか話しません．
• 前提の見逃しはないか，著者の本意から外れていないか
• 言葉の定義が自分固有のものになっていないか
  ⇒ この論文の重要なところは「深い」です．ですが，深いという意味は相手の価値観に依存します．なので，今回は何が・どのように・どれくらい「深い」のかをわかってもらうために，「深い」の感覚について話しています．

目的のスライド

まとめのスライド

あと，自分は物凄く前置きが長い人です．
前置きが長いと，自分の良さが伝わらないことがあることには注意した方が良いように思います．
それでも，自分の前置きが長い理由は，基本的に重要なことは前置きだと思っているからです．前置きがわからないと，主張の良さが理解されないと思っています．

まとめ

アドバイスください．

あと，スライドを丁寧にチェックしてくれる人はもれなくいい人だと思います．

学会発表のスライドもいつか公開したいものです・・・論文書ければ・・・

python の転置 zip(*list) を理解する

初見では，？？？だったけど，書いてるうちに理解した・・・

タプル型への転置は list(zip(*L))

リスト型への転置は list(map(list, (zip(*L))))

※全て zip で囲むのは，zip object, map object となるのを避けるため．複数で受け取る場合は，m, n = map(list, (zip(*L)) とも書ける

追ってみていくと，次のような感じ python で numpy を使わずに，転置（transpose）する場合 

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
L = list(zip(*L))
L

>>> L
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

このままではタプル型なので，リスト型にする時は

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
L = list(map(list, (zip(*L))))
L

>>> L
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

ちなみに，numpy を使うならで良い

import numpy as np
L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
L = np.asarray(L).T
L

>>> L
array([[1, 4, 7],
       [2, 5, 8],
       [3, 6, 9]])

最初から numpy 使えば良いよね，と言われればそうなのだが， この記法-zip(*L)-は直感的でなく，理由が気になったので調べる．

とは言っても，zip(L) と zip(*L) の違いを把握すれば話は終わる．

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in zip(L):
    print(i)

for i in zip(*L):
    print(i)

# copy しやすいようにしてるだけ

>>> for i in zip(L):
...     print(i)
...
([1, 2, 3],)
([4, 5, 6],)
([7, 8, 9],)
>>> for i in zip(*L):
...     print(i)
...
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)

実行すれば，わかるが既に転置している． この実行結果を見てから気づいたのだが，よくよく考えると， zip(*L) とは zip(L[0], L[1], L[2]) と同じ処理をしていることになる． *L と書くと，L は unpack されて行ごとに分解されるため，*L = (L[0], L[1], L[2])

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(*L)
print((L[0], L[1], L[2]))
for i in zip(L[0], L[1], L[2]):
    print(i)

# copy しやすいようにしてるだけ

>>> for i in zip(L[0], L[1], L[2]):
...     print(i)
...
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)

python 2？における実装はかなりシンプルで，初めての人もこれくらい書けそう． PEP 201 -- Lockstep Iteration | Python.org

def zip(*args):
    if not args:
        raise TypeError('zip() expects one or more sequence arguments')
    ret = []
    i = 0
    try:
        while 1:
            item = []
            for s in args:
                item.append(s[i])
            ret.append(tuple(item))
            i = i + 1
    except IndexError:
        return ret

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in zip(*L):
    print(i)

# copy しやすいようにしてるだけ

python 3 では，map, zip, filter といった関数は次のように iterator 形式なっていて 無駄な try とかないし，yield によってメモリ消費量の削減を考えているぽい． Built-in Functions — Python 3.7.3 documentation

def zip(*iterables):
    # zip('ABCD', 'xy') --> Ax By
    sentinel = object()
    iterators = [iter(it) for it in iterables]
    while iterators:
        result = []
        for it in iterators:
            elem = next(it, sentinel)
            if elem is sentinel:
                return
            result.append(elem)
        yield tuple(result)

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in zip(*L):
    print(i)

# copy しやすいようにしてるだけ

一応，python 3 でメモリ消費が少なくなっているのをチェックしました． AtCoder のコードテストのメモリ消費量によって確認しています（使い方としてはよろしくないです．すいません）． こんな感じのコード

N = 100
L = [[j for j in range(N)] for i in range(N)]

# それぞれ def zip(*args) を書いて実行

for i in zip(L):
  pass

やっぱりメモリ消費量がわずかながら抑えられてましたね． なんというか，3000行3000列でやっとこさ，0.2MB というのは 普段からそこまで iterator を意識しなくても良いというのと プログラミング言語としては組み込み関数が洗練されていくのは良いって感じますね

zip の種類	N=100	N=1000	N=3000
上の zip (python 2?)	5,532 KB	37,904 KB	345,424 KB
下の zip (python 3.7.3)	5,516 KB	37,732 KB	345,200 KB

はい，以上です．