はじめに 確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いてくれているのはなさそうだったので、手計算確認用にプログラムを書いた。 Inside-Outsideアルゴリズムとは 内側・外側アルゴリズム 確率文脈自由文法の生成規則(チョムスキー標準形)の確率値をコーパスを求める際に、内側確率βと外側確率αを導入することで効率よく求められる 隠れマルコフモデルにおける前向き・後ろ向きアルゴリズムに似た感じ 内側確率 : 非終端記号Aから終端記号列w_i^jが生成される確率 外側確率 : 導出中に出現するAについて、Aが支配しているw_i^j以外の両側の終端記号列w_1^{i-1}とw_{j+1}^Nが現

はじめに 勾配ブースティング木の高速化はどうすればいいだろうと調べていたら、arxivで流れているのを見かけたのでメモ。 FastBDT: A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate classification https://arxiv.org/abs/1609.06119 https://github.com/thomaskeck/FastBDT Stochastic Gradient Boosted Decision Tree(SGBDT) 勾配ブースティングの各イテレーションで、学習データから非復元抽出でサンプリングしたデータを用いる https://statweb.stanford.edu/~j

はじめに 単語をベクトルや確率分布などの数学的表現で扱いたい場合があったりする。 しかし、「どのようなベクトル・確率分布にすべきか？」などはタスクに依存したりして、自明じゃない。 たくさんあって、派生や新しいものもどんどんでていると思うので、どんなものがあるか調べたかぎりメモ。 One hot表現 各次元が「その単語か否か」を表すベクトルで表現 次元の大きさ＝ボキャブラリ数 例: スカイツリー = (「船」か否か, 「スカイツリー」か否か, ... ) = (0,1,0,...) 素性のどれか1つしか1にならなくてスパースネスの問題がでる 未知語はゼロベクトルになってしまう 文字nグラムによる表現 単語の表層から得られる情報を利用 単語に出現している文字nグラムを利用 カタカナ語とか有効そう 例: スカイツリー = (「スカ」の出現回数, 「カイ」の出現回数, 「イツ」の出現回数, 「アア

はじめに 検索エンジンのトークナイズ処理の部分で行われている基本処理や工夫を少し調べてみたのでメモ。 トークナイズ処理 「検索クエリ」に対してマッチする「ドキュメント」を高速に検索するためにインデクス(索引)を作成する 本の最後の方にある「用語 - ページ」のような感じで、速く目的の用語が書いてあるページを調べられる インデクスは、日本語の場合文字が連続しているため、「形態素」や「(文字)N-gram」などが使われる 文1「六本木ヒルズに行った」 文2「青山さんから電話があった」 【形態素でインデクスを作成する場合の例】 文1：「六本木ヒルズ」「に」「行く」「た」 文2：「青山」「さん」「から」「電話」「が」「あっ」「た」 【文字2-gram(bigram)でインデクスを作成する場合】 文1：「六本」「本木」「木ヒ」「ヒル」「ルズ」「ズに」「に行」「行っ」「った」 文2：「青山」「山さ」「

はじめに 形態素解析とかの解析時に使うラティス(形態素候補をグラフにしたもの)のうち、1番ベストな解だけが欲しい場合が多いが、2番目以降の解も欲しい場合がある。 N番目までの解を効率よく求める方法があり、使いたいケースが出てきたのに書いてみる。 Nbestとは 解析したときに、スコアが良い順に、第一候補(1best)の解だけでなく、第二候補、第三候補・・・の解が考えられるとき、第N候補までのことをNbestという Nbest解 前向きDP後ろ向きA*アルゴリズム http://ci.nii.ac.jp/naid/110002725063 ラティスにおいて、効率よくNbestを求める方法が提案されている 最初に、1bestを求める方法と同じようにスタートノードからあるノードまでの最小コストhをすべてのノードについて求めておく 1bestの時は、ゴールノードからスタートノードに向かって、最小コ

はじめに プロフェッショナルな「深層学習」本で紹介されているRNNの一種のElman netを書いてみる。 Recurrent Neural Network(RNN)とは 再帰型ニューラルネット ネットワーク内部に内部有向閉路を持つようなニューラルネットの総称 Feedforwardの時は、入力層から出力層へ一方方向 この構造のおかげで、時系列や言語モデル、系列ラベリングなど前の状態を持つような問題に対して考慮できる いろんな種類がある(以下はwikipediaから) Fully Recurrent network Hopfield network Boltzmann machine Simple recurrent network Elman net Jordan net Echo state network Long short term memory(LSTM) network Bi

はじめに FeedForwardNeuralNetwork。プロフェッショナルな「深層学習」本のバックプロパゲーションの導出が丁寧にされていてわかりやすかったので、それに合わせて書いてみる。 各層の活性化関数はロジスティック(シグモイド)関数、出力層の活性化関数はソフトマックス関数、誤差関数は交差エントロピー。 コード 1インスタンスごとに重みを更新(SGD)。 直近TERM個のインスタンスの誤差平均が終了条件を満たしたら終了。 学習が収束してくれているので大丈夫そう。 #include <iostream> #include <vector> #include <cstdio> #include <algorithm> #include <cmath> static const double PI = 3.14159265358979323846264338; //xorshift //

はじめに Sill et al., Feature-Weighted Linear Stacking, 2009 http://arxiv.org/abs/0911.0460 最近、コンペ上位者の手法としてよく見かける手法「Stacking」の一つについてメモ。 Stacking 複数の機械学習モデルの予測結果をブレンドすることで、さらによい予測結果を得る方法 アンサンブル学習やメタ学習の一種 「学習モデルを一つずつ積み重ねる＝スタックする」 一般に2段階で構成され、1段階目は入力に対して各学習モデルが結果を出力、2段階目はその各出力をまとめあげ最終結果を出力 BlendingやStacked generalization、日本語だとスタック汎化、スタッキングと呼ばれたりする http://shindannin.hatenadiary.com/entry/2015/03/13/101945

はじめに 今年の目標にしていた係り受け解析関係の資料について雑多にメモしておく。リンク集。 拾いきれていない、最新の論文まで追えていないので、あとで追加・整理し直す。 Wikipedia http://en.wikipedia.org/wiki/Dependency_grammar 文節単位がよいか、単語単位がよいかの議論 http://togetter.com/li/164400 https://plus.google.com/107334123935896432800/posts/KHoDsDssycf http://plata.ar.media.kyoto-u.ac.jp/mori/research/public/flannery-NLP12.pdf 解析処理について説明している日本語資料 海野, 統計的係り受け解析入門 http://www.slideshare.net/unnon

はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。 AdaDeltaとは M. D. Zeiler, ADADELTA: AN ADAPTIVE LEARNING RATE METHOD http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf 学習率を自動調整する方法の一つ 他の関連手法の問題点等を改良 過去すべての勾配を考慮→直近の勾配だけを考慮したいので、指数関数的に減衰するように考慮 グローバルな学習率を指定→second order methodsの特性を持つように、パラメータの変化について直近のパラメータの変化から計算し

はじめに 複数のアルゴリズムの結果の有意差検定に使用されていたので、メモ。 より詳細に紹介されているのは以下の論文。 Demsar, Statistical Comparisons of Classifiers over Multiple Data Sets, 2006 http://jmlr.csail.mit.edu/papers/volume7/demsar06a/demsar06a.pdf 1999年から2003年のICMLの論文で使われた検定について調査して、アルゴリズムやデータセットの種類によって使うべき検定方法を紹介している。 Friedman test 対応のある順序尺度の3群以上の平均順位に有意差があるかどうかを検定(ノンパラメトリック検定) repeated-measures ANOVAのノンパラメトリックに相当 帰無仮説(H0) : μ_0=μ_1=…=μ_k (すべ

はじめに S. Wang & C. D. Manning, Baselines and Bigrams: Simple, Good Sentiment and Topic Classificatioin Naive Bayes素性を利用したSVM(NBSVM)なるものを試してみる。 SVM with NB features(NBSVM) Log-count ratio r = log( (p / ||p||_1) / (q / ||q||_1) ) 正例カウントベクトル p = α + Σ_{i:y_i=1} f_i 負例カウントベクトル q = α + Σ_{i:y_i=-1} f_i f_i : 各事例iにおける素性ベクトル α : スムージング用パラメータ モデル w' = (1-β) * w~ + β * w w~ : ||w||_1 / |V| β : 補間パラメータ(0〜1)

はじめに 簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで) dpができなすぎるので、「dpやるだけ」って言えるようになりたい。 編集距離とは ある文字列sからある文字列tへ、文字の削除、挿入、置換などの操作をするとき、最小の操作回数(または最小操作コスト) dp[i][j] := s[0..i-1]からt[0..j-1]にするのにかかる最小操作回数(または最小操作コスト) さまざまな変形や拡張が研究されてる 近似文字列照合 許可する操作による違い 編集距離(Levenshtein distance) 挿入、削除、置換 Damerau distance 挿入、削除、置換、隣接文字同士の入替 Longest common subsequence distance 挿入、削除 ハミング距離(Hamming distance) 置換の

はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf 上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。 (論文で提案されている手法ではないことに注意) コード #include <iostream> #include <vector> #include <map> #include <sstream> class KPSummary { // T[i][k] := 文iまでで最大要約長がkのときの最適解値 // U[i][k] := 経路復元用(文iを利用したかどうか) std::vector< std::vector<int

はじめに 巨大だけどほとんどの要素がゼロであるような疎行列は、そのまま保持するより、要素がゼロじゃないところだけをうまく保持する事でメモリや計算量を減らせたりする。 扱う行列のタイプによって、効率のよい形式がいくつかあるようなので代表的なものをメモしておく。 Coodinate(COO) Format 非ゼロ要素の(row indices, column indices, value)を要素数分持たせる形式 非ゼロ要素が散らばっている場合に有利 0 4 0 0 2 0 0 0 1 を row 0 1 2 column 1 1 2 value 4 2 1 のように保持する。 compressed sparse row(CSR) Format / compressed sparse column(CSC) Format Coodinate Formatにおいて、左から右、上から下へ順番に要素を

はじめに ちょっと気になったので、liblinearで扱われているモデルのフォーマットについて確認する。 言語処理などで高次元なものを扱う場合、線形カーネル(ただの内積)を扱った方が精度がよい場合が結構あるので、自力でモデルファイルをパースできるようにしておくと便利かも。 確認の仕方 liblinear-1.93のソースコードの「linear.cpp」のload_model関数を追ってみる モデル形式 パラメータ情報 solver_type 学習器の種類 L2R_LRやL1R_L2LOSS_SVCなど文字列 nr_class クラス数 整数値 nr_feature 素性数 整数値 bias バイアス値 小数値 label ラベル名 nr_class数だけ、整数値番号が並ぶ w 重みの値 この行以降、nr_feature数分、重みのデータが並ぶ また、この行が終わった後の情報は無視される(よ

9/1にVOYAGE GROUPさんで行われたDSIRNLP#4勉強会で発表させていただきました 聴いていただいた方、ありがとうございました 勉強会のページ http://partake.in/events/76854228-ba38-4f6e-87b9-f79e30add75c 発表資料 http://www.slideshare.net/phyllo/weighted-finitestatetransducer Weighted Finite-state Transducerについて from phyllo 補足 「高速化できる」と口走ってしまっていたのですが、ケースに依存している話で、WFSTへの変換にかかる時間や構造の持ち方の問題で、元のモデルより必要なメモリが多くなったり、時間がかかることがあると思います どうやってモデルをWFSTに直すの？って部分は、例をはしょってしまっていた

はじめに テキスト分類でよく使われるNaive Bayesにはいくつかの厳しい仮定や条件があり、それによって性能が落ちてしまっている。 経験則をいれたりして性能を向上させたTWCNB分類器を試してみる。 多項モデルによるNaiveBayes l_MNB(d) = argmax_c{ log P(c) + Σ_w{f_w * log P(w|c) } } l_MNB(d) : 多項モデルでの文書dの予測クラスラベル P(c) : クラスcである確率 f_w : 文書での単語wの出現頻度 P(w|c) : クラスcでの単語wの出現確率 P(w|c)の推定値=(N_cw + α_w) / (Σ_w {N_cw} + 単語の種類数) N_cw : クラスcで単語wが出現する訓練文書数 α_w : パラメータ(=1) 【メモ】P(c)の推定値=(N_c + α_c) / (Σ_c {N_c} + ク

はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(＝トピック)」を発見するための統計的なモデルのこと トピックモデルのいろいろ Unigram Mixtures ナイーブベイズでクラス数kと各パラメータをEMで繰り返し推定していく http://www.kamalnigam.com/papers/emcat-mlj99.pdf Probabilistic Latent Semantic Indexing(PLSI) 検索技術であった潜在意味解析(LSI,1990年)を確率的に解析、開発された生成モデル(1999年) 各単語ごとに別なトピックから生成されたと仮定する http://cs.brown.edu/~th/pap

はじめに 分類器の決定版(？)的なSoft Confidence Weighted Learningを試してみた。 Soft Confidence Weighted Learningとは 2012年に提案された、各重みを正規分布と考え更新時にその分布が変わるようにしたConfidence Weighted(CW)関係のノイズに強くなった版 オンライン学習 http://icml.cc/2012/papers/86.pdf 詳しい解説記事 http://d.hatena.ne.jp/kisa12012/20120625/1340616659 使用したデータ LIBSVMのページにあるUCIデータセットのa9aを用いた http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 学習データ : a9a テストデータ : a9a.t コード 毎