はじめに 勾配ブースティング木の高速化はどうすればいいだろうと調べていたら、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

はじめに 最近よく見かける「t-SNE」という非線形次元圧縮手法を試してみた。 t-SNEとは t-Distributed Stochastic Neighbor Embedding SNEと呼ばれる次元圧縮手法の問題点を改善した手法 SNEは、「各点間の"ユークリッド距離"を、類似度に相当する"条件付き確率"に変換して低次元にマッピングする手法」のこと 各点について、高次元での確率分布と低次元での確率分布が一致するように低次元での点を探している 確率分布の違いは「カルバックライブラー情報量」で、これを損失関数にして勾配法で低次元の点を求める 低次元での分布に「自由度1のt-分布」を利用する さらに、高速化を行った「Barnes-Hut t-SNE」という手法ではO(n log n)で計算できる http://arxiv.org/abs/1301.3342 詳しい説明は、元論文や紹介記事が

はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subsequential Transducerとは Finite State Transducerの一種 Transducerにおいて、initial stateが一つで、同じ入力ラベルを共有する同じ状態からのの遷移が2つ以上なく、各最終状態での最終出力文字列が高々p個のとき、p-subsequentialで、pが整数ならfinitely subsequentialというらしい minimal(状態数が最少)、Acyclic(サイクルが無い)

はじめに プロフェッショナルな「深層学習」本で紹介されている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

はじめに 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の特性を持つように、パラメータの変化について直近のパラメータの変化から計算し

はじめに Feature Hashingについて気になったことがあったので試してみた。 Feature Hashingとは Hashing trick ハッシュ関数を使って、素性群をM次元ベクトルにする 一種の次元圧縮 Bag of wordsなどの素性をそのままハッシュ値にすることで、素性とIDのペアの辞書などが必要なくなる スパムフィルタでは、新語やミススペルでフィルタ回避されてしまうと対応すべき語が増え続ける(辞書が大きくなる)問題などに使える ベクトルの作り方 いくつか提案されているが、各素性のhash値を計算してmod Mをとったインデクスの所に入れるものとしては主に2つがあるようなので、メモしておく。 Shiらの方法 Shiら(2009) 値をunsigned sumする φ_i (x) = Σ_{ j:h(j)=i } x_j h : ハッシュ関数 Weinbergerらの方

はじめに 複数のアルゴリズムの結果の有意差検定に使用されていたので、メモ。 より詳細に紹介されているのは以下の論文。 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 (すべ

Interpolation Searchとは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索時間はO(log log n) 二分探索では、O(log n) データに依っては、二分探索の方が速くなる場合もあり得る 計算例 配列vが「1,2,3,5,6,10,12」として、 left = 0, v[left] = 1 right = 6, v[right] = 12 である時、 2分探索では、mid = floor( (left + right) / 2 ) = floor( (0+6) / 2 ) = 3のように決めたりするが、 Interpolation Searchでは、値も考慮し、value=6を探したい場合、 mid

DSIRNLP#6 10/11にデンソーアイティーラボラトリさんで行われたDSIRNLP#6勉強会で発表させていただきました 聴いていただいた方、ありがとうございました。 勉強会のページ http://partake.in/events/38e416b0-5e64-4bd4-8388-4e19acd0ef97 発表資料 一部、発表時の資料を修正しています 主だって参考にした論文は以下になります Zheng&Webb, Semi-naive Bayesian Classification, 2008 http://www.csse.monash.edu.au/~webb/Files/ZhengWebb08a.pdf No Bayes No Life -Naive Bayesは今でも進化しているようです。- from phyllo 補足(2014/10/12追記修正しました) 質問への回答で、

はじめに 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)

はじめに G. Tsoumakas, I. Katakis, I. Vlahavas., Mining Multi-label Data http://lpis.csd.auth.gr/paper_details.asp?publicationID=290 マルチラベル分類問題について、メモ。 マルチラベル分類問題 1つの事例が、複数のラベル(ラベルの集合)に同時に分類されうる分類問題 例：「ダビンチコード」の記事のカテゴリ→宗教、映画 マルチラベルの教師あり学習では、主に以下のタスクがある マルチラベルクラス分類(multi label classification) ラベルランキング(label ranking) また、マルチラベル学習の方法は、主に2つのグループに分けられる Problem Transformation Algorithm Adaptation シングルラベル問題へ変

はじめに Rousseau et al., Graph-of-word and TW-IDF: New Approach to Ad Hoc IR http://www.lix.polytechnique.fr/~rousseau/papers/rousseau-cikm2013.pdf 文書dのグラフ的表現とそこから計算されるTW-IDFというTermの重み付けについて、メモ。 Graph of Word 文書を重みなし有向グラフで表現 頂点: 各(unique)term 辺: 固定幅(4ぐらい?)の窓内のtermとの共起 辺の向き: termの出現順序(前から後ろ方向のみ) 多重辺にはしない TW-IDF TW-IDF(t,d) = tw(t,d) / (1-b+b*|d|/avdl) * log( (N+1) / df(t) ) tw(t,d): 文書dのgraph of word表

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

はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 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

はじめに WSDM2014(WWW2013,YSS2013,SIGIR2013)のチュートリアルで「EntityLinking」といタスクが紹介されていたので、ちょっと調べてメモしておく。 次元圧縮！ Entity Linkingとは テキストに出てくるエンティティ(実体)を識別・決定するタスク 固有名詞抽出は「固有名詞を識別して取り出す」タスクなので、異なる 雑にいうと、KnowledgeBaseと呼ばれる(識別された)エンティティ集合からテキストにでてくるエンティティを決定すること KBにない新しい固有名詞を発見することも含まれたりする(「NIL」として取り扱う) 実際の例 テキスト「東京タワーに行った」 固有名詞抽出 「東京タワー」を取り出す Entity Linking 「東京タワー」が以下のreference(ここではWikipediaのページ)と対応することを決定する http

はじめに 悩み多き年頃なので、進捗ダメです。 KVS見てるときに出てきた、次元圧縮っぽさがあるBloom Filterを試してみる。 Bloom Filterとは 「ある要素が集合に含まれるか否か？」を扱えるデータ構造 要素をそのまま保存せず、ハッシュ値にしたものを配列に保存する アルゴリズム サイズがMの配列A[]を用意し、すべて値を0にしておく 要素の追加 K個の独立なランダムハッシュ関数(0〜M-1を返す)を使い、要素をK個のハッシュ値にする 配列Aでハッシュ値のindexのところを1にする(値がなんであっても) 要素の検索 追加時と同様にハッシュ値にし、すべて1になっていれば、要素が含まれると判断する 他の組み合わせでも1となってしまう組み合わせがあるために、「間違って要素がある、と判断してしまう可能性」がある＝偽陽性 MやKを調整する事で、記憶容量と偽陽性のトレードオフを実現でき

はじめに Deepな話で、簡単に試せそうだったStacked Denoising AutoEncoderを試しに遊んでみる。 あんまり詳しく調べていないので、お遊びレベルという感じで・・・ 注意:下記では「特徴抽出器」として利用する方法を試しています。通常は事前学習として行い、それを初期値に使い、普通にニューラルネットの学習を行うことを指すと思いますが、下記のような特徴抽出器的使い方もありみたいですね(ref.機械学習プロフェッショナルシリーズ「深層学習」pp.72-74)。 Stacked AutoEncoderとは BengioやVinsentによって提案や紹介 AutoEncoderを何層も重ねたもの 各層の学習は、一つ前の隠れ層を入力にAutoEncoderを学習し、出力部分を捨てて次の層を学習する Unsupervised layer-wise pre-training 層の最後

はじめに 次元削減せずにはいられない。 0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。 Matrix Factorizationとは Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法 行列Mを、2つの行列P,Qの掛け算で近似するもの 行列Mが与えられたとき、行列Pと行列Qをそれぞれ見つける ユーザー数m、アイテム数nとして、Mはm*n行列。Pはm*k行列。Qはn*k行列。 行列Mには欠損データが含まれている 行列PとQを求めるために次式を最小化する min Σ_{(u,i)∈κ} (M[u][i] - Q_vec[i]*P_vec[u])^2 + λ(|Q_vec[i]|^2 + |P_vec[u]|^2) κは、既知のM[u][i]が存在する(u,i)のペアの集合 SGDで解を探す場合は以下の反復式になる e_ui :