1期が終わる前から2期のことを考える

日記

アニメの話じゃないです。授業の話です。

今週はテスト週間。NAISTは1年4期制なので、今週で第1期が終わります。ぎゅっと濃縮された授業でいいんですけど、テストが短いスパンであるのはキツイ。それで、来週からは第2期が始まります。第1期が終わってから考え始めるという悠長なことは言ってられないので、今日第2期の1週間の予定を考えた。なかなかハード。授業だけならともかく、松本研の勉強会やその準備と、CS研での勉強会や活動があって、予定の段階では第1期よりもハードなものになりそう。
# ダブルブッキングのところとかあるので、そこはCS研優先で。でも、勉強会で自分が担当になってる時はちゃんと出ます。

そういえば、研究が予定に入っていませんが、いいんですか？＞俺

JSAI2011の面白そうな論文リスト

研究 メモ 論文

2011年度人工知能学会全国大会（第25回） JSAI2011
人工知能学会の全国大会の論文PDFが出ていたので、パラパラと見てみた。学部時代から分野は近かったけど、未だに出したことも行ったこともない。今年は岩手県でやるらしい。来年あたり出したいですよね（希望）。
パラパラと見ていたわけだけど、途中からその数に負けて、興味ありそうなセッションを狙い撃ちになってしまった。探した中では、学部の時の先生の論文が2本あった。今回は学生は出していないらしい。

グラフばっかり。NLP縛りがあるわけではないので、別に悪いことではないんだけど。あと、手法よりもタスクの面白さに惹かれるところがあるので、僕はどっちかというとそういう人間なのかなとか思ったり。何をやりたいか考えろって言われたら間違いなく手法よりもタスクのことを考える。この2年間は手法よりで基礎研究をしようと思ってますけど、ちゃんとできるかどうかちょっと心配。
ちなみに、ちゃんと読むのは来週以降。

ICML2011の読むかもしれないリスト

メモ 研究 論文

正確に言うと、ICML2011の読んでみたいけど読めるかなリスト。読み会で読むためのリストアップではなく、個人的に。

  • Dynamic Egocentric Models for Citation Networks (pdf)
    • Duy Vu, Arthur Asuncion, David Hunter, Padhraic Smyth
    • ネットワークの形成と時間による進化の分析は、いろんな分野で基本的な重要項目である。長期間のネットワークデータセットがあるのに、多くの研究ではある時期のデータしか使っていない。この論文では、多変量計量プロセスを使って連続時間のネットワークデータをモデル化する動的エゴセントリックフレームワークを導入する。推論においては、我々の方法が大規模なネットワークデータに対してもスケールするように、効率的な部分尤度アプローチが使われる。我々はこのテクニックを様々な引用ネットワークに適用し、予測の力と学習した統計的モデルの説明可能性について示す。
  • Large Scale Text Classification using Semi-supervised Multinomial Naive Bayes (pdf)
    • Jiang Su, Jelber Sayyad Shirab, Stan Matwin
    • 数多くの半教師学習法はラベルづけされてない文書を使ってMultinominal Naive Bayes (MNB)を増やすことを提案してきた(??)。しかし、実装の難しさや一貫性のない予測性能、または高い計算コストためにそれらの使用には制限がある。 この論文では、Semi-supervised Frequency Estimate(SFE)と呼ばれる新しくてとてもシンプルな半教師のMNBの拡張を提案する。我々の実験では、提案法がAUCと精度の観点から追加データ(ラベルあり or ラベルなし)でMNBが改善することを示す。我々はこれの要因をEM+MNBやラベル付きの学習データによるMNBよりも、SFEがよりよい条件付き対数尤度を常に生成することにあると思っている。
  • Preserving Personalized Pagerank in Subgraphs (pdf)
    • Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich
    • 巨大な現実のネットワークを簡易に表現する部分グラフを選ぶことは、多くの場面で役に立つ。よくある戦略は元のグラフの次数分布やクラスター係数などにマッチするサブグラフを誘導するノードをサンプリングすることである。しかし、クラスタリング、分類、ランキングのアプリケーションに重要なノード間の関係をきめ細かく保存するような試みはない。この研究では、Personalized PageRank Value (PPV)の考えに沿って上記の関係をモデリングする。我々は、今あるサンプリング法によって誘導された部分グラフの出力はPPVを保存していないことを示し、あらゆる与えられたノードの部分グラフ上でPPV保存部分グラフを作るためのアルゴリズムを提案する。3つの現実の強大なネットワークによる実験では、提案法によって作った部分グラフが、PPVの保持やクラスター精度、基本的なグラフの性質の保持の観点から誘導された部分グラフを改良することを示す。
  • Sparse Additive Generative Models of Text (pdf)
    • Jacob Eisenstein, Amr Ahmed, Eric Xing
    • テキストの生成モデルでは全てのクラスやトピックで多項分布を想定している。シンプルなモデルの場合でさえ、数千ものパラメータ推定を要求される。この論文では、テキストのついての代替の生成モデルを提案する。中心となるアイデアは、全てのトピックとクラスは定数の背景分布から対数の頻度における偏差のモデルによって与えられる。このアプローチでは2つの優位な点がある。1つは、過学習をさせずにスパースを実行出来る。もう1つは、隠れスイッチ変数が必要に鳴るのを避けて、対数空間で簡単な足し算で生成ファセットを組み合わせることが出来る。我々は、分類、トピックモデリング、より複雑な多面的な生成モデルのシナリオの範囲に対して、このアイデアの適用性を示す。
  • Predicting Legislative Roll Calls from Text (pdf)
    • Sean Gerrish, David Blei

なんか、こうやって読みたい論文探してると自分のやりたいことがだんだん分かってくるような気がするので、これからいろんな会議の読みたいリストを作るといいのかも。でも、当然ですけどネットワーク科学の研究室で2年やってきているのでどうしてもそっち系の論文に目が行く。勉強2ヶ月目のNLPはまだまだアウェイです。また今度、WWW2011も見てみます。

五月

日記

五月病（ごがつびょう）とは、新人社員や大学の新入生などに見られる、新しい環境に適応できないことに起因する精神的な症状の総称である。

五月病 - Wikipedia

新しい環境に適応出来ていないわけではないので、僕のこの怠けは五月病のそれじゃないみたいです。

今日は朝起きて朝御飯食べて身支度して、未使用のバスタオルがなかったから洗濯していたらいつの間にか寝ていて、結局お昼ごろ大学へ。1、2限はどうしたのでしょうか。3限はゼミナールがあったけど、今回はスルーさせていただいて、周りが勉強会に出ている時間に課題をやって、今日は最後のD-Mathだけ参加になりました。松本先生と面談がまだ出来ていない。研究は向こうでも、何かヒントが得られそうなので是非とも話をしたいが、なかなかタイミングが合わない。明日こそ。

帰ってきて昨日の残りのコンソメスープに、業務スーパーで買った10個248円の冷凍ロールキャベツを入れてみた。普通に美味しい。パスタに若干飽きてきて、冷凍のおかずが普通に安くて美味しいので、炊飯器が欲しくなってきた今日この頃。

NMFについてまとめ

研究 論文

ことの発端はこれ→NMFを勉強中 - シコウサクゴ（）で、知ってる人に教えてもらったりしてやっと理解できたので、まとめ。今日はちゃんと書く・・・つもり。ベースは[1]の論文だが、使っている記号は全然それに則ってないのであしからず。

NMFとは

NMF(Non-negative Matrix Factorization: 非負値行列分解)では、ある非負行列Vを2つの行列の積WHに分解する。つまり、

V \approx WH

となるような、W, Hを決めることである。どの世界でどのように使われているかはよく分からないけど、恐らく画像処理、音声処理、そして自然言語処理で使われているはず。一般に、Wは特徴的なパターンを表し、HはWのパターンの出現回数と見ることができる。

コスト関数

どうやって求めるかというと、コスト関数を最小化するいわゆる最適化の方法で求める。コスト関数は、二乗誤差バージョンとダイバージェンスバージョンがあって、二乗誤差バージョンは
J(W,H) = \sum_{i,j} [ v_{ij} - \sum_k (w_{ik} h_{kj}) ]^2 = \sum_{i,j} [v_{ij}^2 - 2v_{ij}\sum_k (w_{ik} h_{kj}) + (\sum_k w_{ik} h_{kj})^2]
v_{ij}^2の項は観測Vのみに依存する定数なので最適化に直接関係ないから
J(W,H) = \sum_{i,j} [- 2v_{ij}\sum_k (w_{ik} h_{kj}) + (\sum_k w_{ik} h_{kj})^2]
と書き変えられる。また、ダイバージェンスバージョンは
J(V||WH) = v_{ij}\log\frac{v_{ij}}{\sum_k w_{ik}h_{kj}} - v_{ij} + \sum_k w_{ik} h_{kj}
である。どちらを使うかはタスクによるとのこと。二乗誤差の場合は誤差平面が対称で、ダイバージェンスは非対称なので、例えば自然言語処理でトピック分類として使う場合はダイバージェンスを使ったほうが直感的に合っていていいらしい。ここでは二乗誤差の場合のみを考えていく。ダイバージェンスはまた今度やるかも。

高速な解法：補助関数法

直接J(W,H)を最小化することはやめて、補助関数A(W,H,R)を導入する。突然出てきたRという変数は、J(W,H)とA(W,H,R)の間でイエンセン(Jensen)の不等式が成り立つように決めている。つまり、
J(W,H) \leq A(W,H,R)
J(W,H) = \min_R A(W,H,R)
を満たすようにRを決める。もし、この2つの条件を満たすようにRが決められれば、以下の2つのステップを繰り返すことで誤差を最小にすることができる。

  1. A(W,H,R)をRについて最小化
  2. A(W,H,R)をW,Hについて最小化

補助関数の導出

それでA(W,H,R)をどうやって決めるのか。上で出てきた目的関数
J(W,H) = \sum_{i,j} [- 2v_{ij}\sum_k (w_{ik} h_{kj}) + (\sum_k w_{ik} h_{kj})^2]
のi,jの総和についての第二項
(\sum_k w_{ik} h_{kj})^2
に着目すると、イエンセンの不等式から
(\sum_k w_{ik} h_{kj})^2 \leq \sum_k \frac{(w_{ik}h_{kj})^2}{r_{ijk}}
をつくることが出来る*1。これを使って、
A(W,H,R) = \sum_{i,j} [- 2v_{ij}\sum_k (w_{ik} h_{kj}) + \sum_k \frac{(w_{ik}h_{kj})^2}{r_{ijk}} ]
とする。

A(W,H,R)をRについて最小化

Rについて最小化することは、(\sum_k w_{ik} h_{kj})^2 \leq \sum_k \frac{(w_{ik}h_{kj})^2}{r_{ijk}}で等式になるようなRを求めることと等しい。一般に、イエンセンの不等式で等号が成り立つ場合というのは、
f(\sum_k p_k x_k) = \sum_k p_k f(x_k)　ただし、 p_k \geq 0, \sum_k p_k = 1で、x_1=\cdots=x_K
なので、A(W,H,R)の場合では、
\frac{w_{i1}h_{1j}}{r_{ij1}} = \cdots = \frac{w_{iK}h_{Kj}}{r_{ijK}} = const だから、 r_{ijk} = \frac{w_{ik}h_{kj}}{const}
\sum_k r_{ijk} = 1という条件を使って、
\sum_k r_{ijk} = \sum_k \frac{w_{ik}h_{kj}}{const} = 1 \Longleftrightarrow const = \sum_k w_{ik} h_{kj}となり、r_{ijk} = \frac{w_{ik} h_{kj}}{\sum_k w_{ik} h_{kj}}の点で最小となる。

A(W,H,R)をW,Hについて最小化

A(W,H,R)をw_{ik}とh_{kj}で偏微分して0と置いて解いてみると、
\frac{\partial A}{\partial w_{ik}} = \sum_j [ -2v_{ij}h_{kj} + 2\frac{(w_{ik}h_{kj})h_{kj}}{r_{ijk}} ] = 0 \Longrightarrow w_{ik} = \frac{\sum_j v_{ij} h_{kj}}{\sum_j \frac{h^2_{kj}}{r_{ijk}}}
\frac{\partial A}{\partial h_{kj}} = \sum_i [ -2v_{ij}w_{ik} + 2\frac{(w_{ik}h_{kj})w_{ik}}{r_{ijk}} ] = 0 \Longrightarrow h_{kj} = \frac{\sum_i v_{ij} w_{ik}}{\sum_i \frac{w^2_{ik}}{r_{ijk}}}

以上をひとつにまとめて、NMFアルゴリズムの完成

上の(2)で求めた w_{ik}と h_{kj}の r_{ijk}の部分に(1)で求めたr_{ijk}を代入してまとめれば更新式の完成。
t_{ik} \leftarrow t_{ik}\frac{\sum_j v_{ij} h_{kj}}{\sum_j\sum_l(w_{il}h_{lj})h_{kj}}　　　　 h_{kj} \leftarrow h_{kj}\frac{\sum_i v_{ij} w_{ik}}{\sum_i \sum_l(w_{il} h_{lj})w_{ik} }
この更新式のことを[1]では、"multiplicative update rules"と呼んでいる。この更新式をくるくる回して、二乗誤差の値の変化がとても小さくなったら終了。

参考文献

[1] Lee, D. D., & Seung, H. S. (2001). Algorithms for non-negative matrix factorization. Advances in neural information processing systems, 13(1), V-621-V-624.

*1:だいぶ省いた。。。

NMFを勉強中

日記 研究 論文

テキトーなことを書きます。
昨日の夜あたりから、集合知プログラミング10章で出てくるNMF（非負値行列因子分解）についてちょっと勉強中。集合知プログラミングでは、NMFのアルゴリズムが与えられちゃってるので、ちゃんと導出知りたいと思って、ネットで検索かける。
はてなの近藤さんのブログやらが出てくるんだけど、しっかりめに書いてあったのはNon-negative Matrix Factorization（非負値行列因子分解） - あらびき日記でここを見てみた。ただ、導出については論文参照となっていたので、結局論文の方へ。

  • Lee, D. D., & Seung, H. S. (2001). Algorithms for non-negative matrix factorization. Advances in neural information processing systems, 13(1), V-621-V-624.

6枚くらいの論文だからさらっと行けるかと思ったが、思ったよりもイミワカラナイ。EMっぽくやってるってことなんだけど、固有値問題を解くときのパワー法みたいな反復法に見える。
それで、論文は一度諦めてまたネットを探す。すると、LDAとNMFの両方を扱う記事を見つけた。

そこで参照している論文はまた別のもので、今度はこれを見てみることにした。

  • Xu, W., Liu, X., & Gong, Y. (2003). Document clustering based on non-negative matrix factorization. Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval (p. 267-273). New York, New York, USA: ACM.

今度は割と分かりやすいかもと思った。目的関数の最小化問題にして解くという筋道がはっきり見える。というか、本当に前の論文と同じことやってるんですか、これはという感じ。これでいけるかと思ったけど、制約条件の入れ方が分からなかった。ラグランジュの未定乗数法で、制約条件が等式の場合は知ってますけど、不等号の場合は知りません。クーン・タッカー条件知りません。
という感じになったので、クーン・タッカー条件を勉強しておこうと思って、自宅にある本から

サポートベクターマシン入門

サポートベクターマシン入門

を手にとって、見てみる。この本、難しいｗ←今ここ

ネットが開通して土曜日

日記

金曜日の午前中にモデムが届いて、NTTの業者の人が何かやってくれてネットが開通。プロバイダはGMOっていうところで、価格ドットコムで調べた最安値のところにした。光にすることもできたが、少々お高いことと2年縛りがあってADSLにした。実家もADSLだったが、基地局との距離の関係で速度が全然でなかったので今回もこれを心配していたが、今回は速度は良好。下りは15Mbps出ていて全く問題ない。
今日は自宅にネットが繋がったので、自宅からサーバにつないで実験。あまり良い結果ではないので再実験が何度かありそうだけど、とりあえず先生にメールは送り、返信待ち。
夕方から買い物へ。「一週間分の買い物を一度にして節約」とどっかの記事で見たので、一週間分の朝夕食の材料を買ってくる。とは言っても、主食はもはやパスタなので、あとは何を具にするかの問題。朝食はいままでパンだったが、パンは消費期限が短いのでコーンフレークを買ってみた。加えて、お酒やお菓子などを買って約2000円。既に足りない感があるが、大丈夫だろうか。
明日は午後大学に行って、少し作業をする予定。←行ってない