mits58のメモ

メモ　参考にしないでください

IPCO 2019 目を通したリスト

IPCO って思ったより Integer Programming よりなんですね……

1. Integer Programming and Incidence Treedepth - Eduard Eiben, Robert Ganian, Sebastian Ordyniak, Michal Philipczuk and Marcin Wrochna.

  • 整数計画問題の容易さは、制約行列の構造と深く関係しているってのが最近わかった。具体的には、制約行列の Gaifman graph の primal (or dual) treedepth と、絶対値最大の係数に関して FPT ってのがわかった。
  • これを、より広いクラスの整数線形計画問題に対して拡張してみたらどう？ってのがこの論文らしい。結果としては、FPT ではなくて、すべての係数の絶対値が 1 で、incidence treedepth が 5 であるときでさえ NP-hard だったらしい。
  • Gaifman graph とはなんぞや……と思ったら、ノードが変数で、ある制約条件に共起する場合、そのノード間に辺を張ってできるグラフらしい。
  • Treedepth もよくわかっていないので調べたら、TREE-DEPTH AND VERTEX-MINORS に、スターグラフにどれくらい近いかを測る指標っぽい（小さいとスターグラフに近いって感じ）
  • 問題に対応するグラフ構造を使って解析しているのは面白いなぁ、こういうのやってみたい。

2. Strong mixed-integer programming formulations for trained neural networks - Ross Anderson, Joey Huchette, Christian Tjandraatmadja and Juan Pablo Vielma.

  • 訓練済みニューラルネットワークに対応する、高次の区分的線形関数に対する強い混合整数計画定式化を提案。
  • この定式化は、画像分類ネットワークが敵対的入力に対しロバストであることの証明や、機械学習モデルが目的関数である決定問題を解く際に用いることができる。
  • このMIP定式化を ReLU とか Max Pooling とかに適用してみて、画像分類タスクにおけるネットワークで推論時間がかなり改善したっぽい。
  • 正直？？？という感じだけど、面白そうではある。ただ、Neural Network そのものに対しての解析はかなりやられてそうだし今更感も……？

3. A Bundle Approach for SDPs with Exact Subgraph Constraints - Elisabeth Gaar and Franz Rendl.

  • 厳密部分グラフアプローチってのは、いくつかのグラフ上の NP-hard な問題に対するよりタイトな半正定値計画緩和を得るための階層的なスキーマなんだけど、これを解くのは禁止部分グラフ制約が多すぎてつらい。
  • 部分的なラグランジュ双対を導入して、その評価が2つの独立した部分問題になるという事実を利用するらしい。よくありそうなテク。

arXiv になかったのとかもあって悲しみ。

Descriptors Generation Using the CDK Toolkit and Web Services

読書メモ ケモインフォマティクス

Tutorials in Chemoinformatics（Alexandre Varnek）の9章の読書メモ

Molecular Descriptor（分子記述子）の話と分子記述子を生成するソフトウェアだったり、Webサービスだったりの話

 

What's 記述子

  • Molecular Descriptorは、分子情報に由来する、分子の属性や表現である
    例えば:　分子の重さ、原子の個数〜複雑なものまで様々
  • 分子構造のある側面を捉えるために設計されている
    e.g. 定量的構造物性相関(QSPR)とか定量的構造活性相関(QSAR)とかに用いられる
  • 実験結果の値もMolecular Descriptorとして使われるよ
    e.g. 分配係数*1とか、分光学的特性とか（他のアクセスしにくいエンドポイント[？？？]を予測するのに関連性があるらしい）
  •  本質的な記述子は、分子全体の特性を含む
    i.e. 分子の重みや原子の数、結合の数、回転可能な結合の数、分子量などを含む

記述子の分類

  • Fragment Descriptor:　官能基や前もって決められた部分構造の出現頻度をカウントするもの
  • Topological Descriptor:　分子構造を数学的なグラフとして考え、グラフ理論を用いグラフ不変量を求めそれを用いる
  • Geometrical Descriptor:　分子の三次元構造をエンコードしたもの（特に3D Descriptorと呼ばれる）異なる立体配座*2のもの（conformations）、ジアステレオ異性体*3（diastereoisomers）を区別することができる

分子記述子の例

  • Wiener Index [Topological Descriptor]
    分子内の水素以外の原子に対しペアを考えた際の距離の総和
    距離は2つの原子間に存在する結合の数で定義される
    = 距離行列の全ての要素を加算し2で割ると得られる
    分岐の兆候を示し、ファンデルワールス面に対する簡単なアプローチである（？）
  • 2D autocorrelation vectors [Topological Descriptor]
    原子同士のトポロジカル距離と、それぞれの原子の特性（部分電荷、分極率とか）の値の積により表現される。
  • Radial Distribution Function code（RDF descriptors）[3D Descriptor]
    さっきの2D autocorrelation Descriptorの距離の部分を３次元距離にしたもの

 

あとはソフトウェアの解説なので飛ばす。解説してたのは

  • CDK Descriptor Calculator
  • E-DRAGON Web Service
  • OCHEM Web Service

の3つ。

 

 

 

ジアステレオ異性体とかの話↓

1-2 3） エナンチオマーとジアステレオマー - YAKU-TIK ～薬学まとめました～

こんな風に生物学的活性が異なるようなペアが存在するらしい（すごい）

ってことはQSARとか考えるときは3D Descriptorがよくない？（しらん）

 

*1:水と油のような、２つの混ざり合わない液体を同じ容器に入れ、どちらの液体にも溶ける第三の物質を加えてよく振ると、両方の液体中の第三の物質の濃度の比がある値に一定になる、そのときの値。疎水性を表したりする、あと固体と液体でも定義可能

*2:ぐるぐる動かせる単結合などの結合に関して、その位置が異なる関係の化合物

*3:キラル中心が存在する物質に関して、鏡像関係にあるもの、乳酸とか

Aizu Online Judgeで手を付けるべき問題

螺旋本に書いてるやつ。考察は簡単だから実装力強化ということで後でやる。

データ構造

全探索

グラフ

DP（Difficult Problems）（動的計画法）

幾何

複合？と数論

 

南極料理人

南極料理人を見ました。

www.amazon.co.jp

アマゾンプライムさまさま……と思っていたら1/19までで期限切れになるので見たい方はお早めに。

 

  • 髪の毛が伸びる描写が凝ってるなぁと感じた(そういうのすき
  • 実際にあるのかわからんけど、いきなり「南極行ってください～」と言われるのは辛そう
  • 体がラーメンで出来てるオタクは多そうだなぁと思いました

ROCとAUCについて

下記を読んだ。メモ。

www.randpy.tokyo

 

  • 偽陽性率 : 本当は負例だけど、間違って正って予測しちゃったものの、負例データに対する割合
  • 真陽性率 : 本当は正例で、正しく正例と予測したものの、正例データに対する割合

感覚的には

  • 偽陽性率 : 実はガンの人の中で、「お前大丈夫やでｗ」と診断された人の割合
  • 真陽性率 : 実はガンではない人の中で、「お前大丈夫やでｗ」と診断された人の割合

みたいな（わかりにくい）

What's the ROC curve?

偽陽性率を横軸、真陽性率を縦軸においてプロットしたもの

  • 2値分類問題で、なんかのスコアを出して、その閾値より上か？下か？でわけることを考える
  • んで、その閾値をminからmaxまで変えていくと色々な（偽陽性率, 偽陰性率）のペアができます
  • これをプロットしたもの

これっていうのは、しきい値を大きい値から下げていくと、偽陽性も真陽性も大きくなる  = なんでもかんでも正と判定することになるので、大丈夫な人の中で「お前ガンじゃないでｗ」って言われる人の確率も増えるんだけど、本当はガンの人にも「お前ガンじゃないでｗ」って言われる人の確率も増えてしまう。

だから大事なのは

  • 間違った判定を小さくする(偽陽性率が小さい)
  • 本当に大丈夫な人を大丈夫と判定する(真陽性率が高い)

モデル

ってことは、ROC曲線がぐいっと左上に曲がってるモデルの方がよい

Why? : 偽陽性率が小さいのに真陽性率が高くなってるから

 

ぐいっと曲がってるってどう判断するねん…… : AUC

  • AUCはROC曲線とx軸とy軸で囲まれた右下部分の面積の値になる
  • ランダムに選んだときは0.5になるので、それより大きいとアドって感じ 1に近いほどよい

ネットワークの表現学習

下のやつを読んだまとめ(ほぼコ……)
ただ、元記事自体は参考になるしアド

www.ai-gakkai.or.jp

 

What's the 表現学習？

  • 画像、音、自然言語、時系列データの要素を予測問題を解くことでベクトル(分散表現)として抽象化する手法
  • 人手で定義した特徴量を並べて〜ではない
  • Deep Learningは多層のニューラルネットを使って表現学習を行っている

ネットワークの表現学習について

  • DeepWalk(2014)とか
  • 既存の複雑ネットワークのクラスタリング手法よりもラベル推定や分類タスクの精度良し
  • 大規模グラフの可視化、画像や文章の内容と関連性からラベルを推定、といった手法へ応用
  • ネットワークの表現学習手法は自然言語処理の表現学習手法から大きく影響を受けている
  • 異種データを分散表現を介して結びつけるとかいうのがある
  • ネットワーク構造とラベル情報、画像データやテキスト情報とネットワーク構造などを同時に表現学習

DeepWalk

  • 自然言語における分布仮説をネットワーク構造へ転用
  • 「ある人の周りはある人を反映してる」、「論文の内容は引用関係から推測できる」という考え方と類似
  • 周囲の関係性から要素の性質を推定する
  • ネットワークのリンク上をランダムウォーク、辿れるノードの列を文脈としてword2vecしてノードの分散表現を計算している
  • Spectral Clustringより高速かつ高精度（既存のクラスタリング手法）
  • LINEとかGraRepとかいうのも出てきた（DeepWalkよりも精度良し）
  • 各要素がもつ画像やテキストからの分散表現とネットワークの分散表現を結びつける研究も

言語の学習表現のSomething to read

チェックする人・研究室

表現学習の国際会議

  • ICLR : 表現学習
  • EMNLP（ Conference on Empirical Methods in Natural Language Processing）
  • ACL（Annual Meeting of the Association for Computational Linguistics）
  • COLING（International Conference on Computational Linguistics）

  • ACL-IJCNLP（ International Joint Conference on Natural Language Processing）

  • ACM sigKDD, ICML, AAAI, IJCAI, WWW, CIKM, NIPS

ライブラリ

 

ネットワークの表現学習のSomething to read

ネットワークの表現学習を行うアド : 「要素の分類や要素間の関係性の容易な推定」を活かせる

今までは　→　パラメータ依存性や精度、Complexityの問題あり、ネットワークのノード間の距離の定量化も難しかった

but now → 要素間の距離を定量化することで要素のラベル推定、分類の精度が向上

  • DeepWalk : 前述のノードの表現学習を獲得する手法
  • LINE : 分布仮説に基づいた表現学習手法を二次の近接性と定義，直接つながっているノードが近いという一次の近接性を定義してどっちも使ってDeepWalk より精度アップ
  • GraRep : ネットワークの構造を抽象化して変換し、上記2つの手法より精度アップ
  • PTE : 要素、ラベルのそれぞれのネットワークを同時に表現学習、一部の要素のラベルから他の要素のラベルを推定
  • Heterogeneous Network Embedding : 画像とテキストと画像同士の関係性をもとに要素を分散表現化，画像のラベル付けやクラスタリングを行う手法
  • text-associated DeepWalk : ノードのテキスト情報とネットワーク情報を組み合わせて表現学習を行う手法
  • Visualizing Large-scale and High-dimensional Data : 数百万単位のノードを可視化

チェックする研究者

ライブラリ

 

 

キーワード

  • network and embedding
  • network and representation

 

 

研究者になりたい

理系のための研究者の歩き方を読むことにした

2章
  • 研究者になるなら「言葉の定義と論理を大切にする」
    →そのためには自分の理解を他人に説明し、ディスカッションすることが重要
  • 修士 : 学会発表とか、自分が今まで身につけた知識の整理とかを通し、「研究活動」の体験をする期間
  • 博士 : 得た知識を下に、論理を構築、新しい理解に向ける期間
    →研究者になるなら必須の期間？
  • 研究職はいっぱいある
    公立 : 大学、大学共同利用機関法人、国立の研究機関、独立行政法人の研究機関……
    民間 : 企業……
3章
  • 研究者に求められるのは以下の2つの能力
  1. 文化としての研究
    多くの人が納得するモデルを構築、普遍的なストーリーを描き、話を展開していく、博士論文みたいなやつ
  2. 開発としての研究
    専門分野の特技を生かして研究していく(よくあるやつ)
  • どっちらも説明力が大事
  • 学術用語や普段の会話の論理に対する意識を常に持っておく必要がある
  • 人の話を聞くときは話の内容を強くイメージ、一歩先を読みながら聞いていく
    →理解できない箇所があったらその場で質問、整理して聞く
  • 逆にしゃべるときは、何をわかってもらうのかを頭に描き、それに向かってストーリーを描くことを心がける
    →「何を伝えたいの？」がわからない話し方はダメ。
  • 論文の書き方も読み方も、ストーリーに沿っていくと
    →だけど矛盾があったりするけどそこを放置してはダメ　少し書き換えるだけで直ることが多いので
    →読むときは他人にざっと説明できることを目指す
  • 評価される業績 : 原著論文・総説・図書の質と量 +獲得した受賞歴・外部資金の一覧 
    →研究をまとめて説得力ある文章や口頭公演で発表するプレゼンの力があらゆる場面で必要
  • 研究成果の位置付けを正しく認識してもらうためには時間を掛けた対話による議論力が必要
    →学会に行くとこれができてよい + 大勢の人が関心ある分野、自分が抜け落ちている大切な分野も見えてきてなおよい
  • 適切な質問ができるようになることも必要(ドクターに入ったあたりでできるようになっておけ)
  • 専門分野を広げよ : 他人の研究にもどんどん首を突っ込んでいけ、他人の立場と概念を知るために
  • コミュニケーション力とリーダーシップを磨け : 研究室はその最適な場
    →自分の理解力・ストーリー構築力を試して磨いていけ
  • ストーリーの描き方 : 研究のサイクルを1回でも多くこなす(学会発表・論文執筆に向けて自分がどう動いていくかを考えて実行する)
  • 研究資金獲得 : 自分が果たせる役割を考え、論文や申請書を書ける力をつけられるよう努力する+学振とか取れるように頑張る
  • オリジナリティの確立 : オリジナリティを確立するのが目指すべき目標 -> 異なるコンセプトを示せるか？
  • オリジナリティには２つ
  1. 他人が真似できない程高度な内容
    →理論・技術などに格段の高度化が必要 but コンセプトとしての斬新さはあまり必要ない
  2. まったく新しい発想を伴う内容
    →競争相手が居ないのでアド but  実現できる見通しが立ちにくいため大きな賭けとなる
  • 30代の半ばまでには自分のオリジナリティを確立しておく必要がある……
  • 実験結果の異常に気づく力 → なぜこの実験結果が出たのか？を意識しておく必要がある
    →誰もが受け入れられるストーリーを構築することにつながる
  • 研究内容を客観的に俯瞰できる力を身に着けよ
    →研究の位置づけを説明できるようにする (自分の研究室のテーマとどう関連してる？)
    →他分野の話を聞くときも自分の仕事との位置を測りながら聞くとアド(難しいけど)
    →器用さは武器になっても評価対象にならない(一本の筋が通った研究をしていくことが必要)
  • 博士号は理系の免許みたいなもん(なので取っておいたほうがよい)
  • 自分の売りを磨け！
    どうやって見つける？→ゼミとかで褒められた部分を伸ばして、ダメ出しされた部分を改善して行くことで発見
    早めに得意分野が通用しそうかどうかを見極める必要がある
    自分が理想とする研究者像を明確にし、足りない点を克服していく必要がある
  • 人脈を広げよう : 国際学会とかおすすめ
  • 地道な努力と忍耐力 と 運や縁 -> よい研究者になるために必要
    →同じ仕事をいろいろな見せ方にするのは良い(いろいろな学会で発表するっていうの)

うーん、いろいろ考えること多いわね(できるところからやっていきます)