Comments
Description
Transcript
ADAの文字列
NLP2010 チュートリゕル 2010 3/8@東京大学本郷キャンパス 超高速テキスト処理のための ゕルゴリズムとデータ構造 東京大学情報理工学系研究科* 岡野原 大輔 [email protected] * 2010年4月から所属が （株）プリフゔードンフラストラクチャーになります。 内容 • 背景 – 自然言語処理と機械学習 • オンラン学習 – 教師有/無, 正則化 • 疎ベクトル々文字列データ構造 – 特徴情報の格納、全部分文字列情報 • 乱択化ゕルゴリズム – Hash Kernel, Randomized SVD 大規模自然言語処理と機械学習 背景 背景 • 利用可能な言語資源の急激な拡大 – ブログ, 掲示板, 商品情報, レビュー – Wikipedia, Google N-gram Corpus ～1010 語 – c.f. Penn TreeBank、京大コーパス ～106語 • ゕプリケーションの要求の高まり – 精度 + 高スループット + 低レテンシ – 例〆ブログ記事やニュースのリゕルタム解析 単語数 1E+12 コーパスサズ比較 （単語数） 百万倍 1E+09 1000000 1000 1 2000年以降 より多くのデータ⇒精度向上 • 大量のデータを利用することでシステムの精度を 大幅に向上することが可能 • 統計的機械翻訳 [T. Brants+, EMNLP 07] – 言語資源の量の対数に比例して翻訳精度は上昇 • 半教師有学習による系列ラベリング [J. Suzuki+ ACL 09] • 上位語/類似語の計算 [Yamada+ EMNLP 09][柴田+, NLP 09] • 半教師有係り受け解析 [T. Koo, ACL 08] – 単語の階層型クラスタリングの結果を利用 本チュートリゕルの効果 • より本質的な部分に時間々経費を割ける – 実験時間々経費々必要リソースを減らす ⇒もっと深く言語と向き合うことができる • 大量のデータを現リソースで処理可能に – 先程のコーパスは全て現在のPCで処理可能 • みんなの手に大規模自然言語処理を！ 定義 • x∈Rm : m次元の実数列ベクトル – xi : xのi番目の成分値. 例: x2= 2.0 • wTx = ∑iwixi : wとxの内積 • <w, x>と書く場合もある • argminx f(x) : f(x)を最小にする変数xを返す w 0.5 2.0 1.0 0.0 x -1.0 3.0 0.0 2.0 wT x 0.5 * -1.0 + 2.0 * 3.0 + 1.0 * 0.0 + w, x は４次元の実数列ベクトル 0.0 * 2.0 5.5 自然言語処理における機械学習 • 多くの問題は入力から出力への関数を学習 する問題として定式化できる 入力 出力 – スパム分類 – 評判分類 – 情報検索 – 構文解析 – 機械翻訳 文書 レビュー クエリ 文 日本語の文 スパムか？ 好意的か？ 関係する文書 構文木 英語の文 二値分類 順位学習 構造学習 特徴ベクトル （素性ベクトル Feature Vector) Φ(x,y)∈Rm • 入力xと出力yから得られる情報から決定 – 各次元が、一つの情報に対応する • よくある作り方 – 入力、出力それぞれのみに依存する特徴ベクトル Φ(x), Φ’(y) の直積を利用 0 0 0 0 0 0 1 0 1 1 0 2 0 Φ(x)= Φ‘(y)= Φ(x,y)= 0 2 0 2 0 4 3 12 R R R 2 特徴ベクトル例 (1/2) 文書分類 • 各次元が文書中に出現した単語に対応 – Bag of Words (BOW) 表現 – 文書中の単語の位置や順序は無視 入力 x 本郷には カレー屋が たくさん あります.. x中の各単語の出現頻度 本郷 … 1 … カレー … 1 … Φ(x)= (0…0,1,0…0,1,…) “本郷”’に対応する次元 11 “カレー”’に対応する次元 特徴ベクトル例 (2/2) 品詞推定 • 単語booksの品詞を推定する – 現在の単語〆books – 直前の単語 : two Φ(x)= (0…0,1,0…0,1,…) – 直後の単語 : . 「現在の単語が“book”’」 – 現在の単語の最後1文字 : s に対応する次元 I have two books . y y y y y 「直前の単語が“two”’」 に対応する次元 現在の文脈情報を全てΦ(x)に入れる 線形識別器 • 特徴と重みの内積で各出力のスコゕを決定 • 予測〆f(x) := argmaxy s(x,y) s(x,y) := wTΦ(x, y) 入力xに対する出力yのスコゕ – w∈Rm 重みベクトル – 高いスコゕを持つ出力yを予測結果とする • ナーブベズ法, サポートベクトルマシ ン, 最大エントロピー法など多くが属する 線形識別器例 文書分類 • 入力xは単語のBOW表現 • 出力yは1:スポーツ 2:グルメ 3:政治 1 0 Φ(x)= 1 0 カレーの出現回数 仕分けの出現回数 ラスの出現回数 野球の出現回数 s(x,1) = w1TΦ(x)= -2 s(x,2) = w2TΦ(x)= 3 s(x,3) = w3TΦ(x)= 0 w= -1 -1 -1 2 -1 1 -1 2 1 2 -1 -1 s(x,2)が一番大きいので、 予測結果は2:グルメ 学習〆重みベクトルwの推定 w* = argminw ∑iL(x(i),y(i), w) + CR(w) • 訓練例{(x(i),y(i))}を利用しwを推定する L(x, y, w) : 損失関数（次項） xをyと正しく推定した場合は0、してない場合は大きな 値をとるような関数 R(w)〆正則化項. wに対する事前知識 R(w) =∑wi2 L2 正則化（多くの特徴が関係） R(w) =∑|wi| L1 正則化（少数の特徴が関係） NOTE:この問題はL、Rがともに凸関数なら、 凸最適化問題であり、効率的に解ける 損失関数の例 二値分類の場合 I(ywTΦ(x) > 0) max(0, 1 – ywTΦ(x)) (SVM) log(1 + exp(-ywTΦ(x)) (ME) exp(-ywTΦ(x)) (Ada-Boost) 分類器が間違って いる ywTΦ(x)の値 各損失関数は0/1 損失の上限かつ、凸な関数 線形識別器による学習々推定 まとめ • 学習 – 訓練データ{(x(i),y(i))}を利用してwを求める – wを求めるには凸最適化問題を解く • 最小化するのは損失関数と正則化関数の和 • 推定 – f(x) = argmaxy s(x,y) = argmaxy wTΦ(x,y) – スコゕ（重みと特徴の内積）が最大となる 出力を推定結果とする 教師有々教師無学習の効率的手法 オンライン学習 バッチ学習 オンラン学習 (従来手法） • 全ての訓練例を見てか らパラメータを更新 • 各訓練例を観測し、 すぐパラメータを更新 • 収束が遅い • 収束が速い • 結果は正確 • 結果は正確ではない • 全訓練例をメモリに保 持する必要がある • 訓練例は一度見たら捨 てられる • 実装は複雑 • 実装は簡単 – 精度はバッチとほぼ同じ ⇒大規模なデータを扱うならオンラン学習 オンラン学習 • 各訓練例(x,y)に対し予測を行い、 結果に基づき、パラメータを即時更新 – 予測が間違っている または正解しても 確信度が低い場合は更新 • 特徴 – 学習例が冗長な場合、収束が速い – 訓練例を全部保存する必要はない – 最適解に到達する保証はない • 精度保証は可能 [Shwarz+07] [Hazan 09] オンラン学習の紹介 • 各種オンラン学習 – – – – Structured Perceptron Passive Aggressive Learning Confidence Weighted Learning AROW • 確率的勾配降下法 (SGD) • 正則化付オンラン学習 – FOBOS, L1累積更新 • オンランEM 多クラス分類問題を 扱う。二値分類はラ ベル数が2の場合 Structured Perceptron [Collins+ 02] 入力: 訓練例{(x(i), y(i))} (i=1...n) wT = (0 0 0 ... 0) // 重みベクトルを初期化 LOOP i ～ random(1, n) y* = argmaxy s(x(i),y) IF y* ≠ y(i) THEN w := w + ψi, y* ψi, y := Φ(x(i), y(i)) - Φ(x(i), y) END IF END LOOP 正解ラベルの特徴ベクトルと ラベルyの特徴ベクトルの差 更新の意味 • wnew := w + ψi, y* – s(x(i), y(i)) が s(x(i), y*) より大きくなるように更新 snew (x(i), y(i)) - snew(x(i), y*) = wnewTψi,y* = s (x(i), y(i)) - s(x(i), y*) + |ψi,y*|2 常に正 y*=3が更新対象 各クラス のスコゕ y=4が正解 1 2 3 4 5 6 1 2 3 4 5 6 構造学習における Structured Perceptron • argmaxy s(x(i),y)さえ効率的に求まれば 候補解の数によらず効率的に学習可能 – 出力が内部構造をもち,特徴ベクトルが各部分の 特徴ベクトルの和で表される場合Viterbiが使える • 条件付確率場(CRF), Max-Margin Markov Network – 最大二部グラフマッチングも解ける – MCMCやビームサーチでスコゕが最大に近いもの を探してy*とみなしてもよい • Sample Rank [Culotta+ 07] • ビームサーチ [Zhang+ 07] Averaged Perceptron [Collins+02] • Perceptronによる学習は不安定 – 最後の方に利用した訓練例に偏る ⇒全ステップでのwの平均値w*を 学習結果として用いる – w* = 1/N ∑i=1...N w(i) – w(i) はiステップ目の学習結果 • 全ステップのwを保持しなくても 平均は計算できる（次項） Averaged Perceptronの 効率的な計算 wT = waT = (0 0 0 ... 0), t = 1 // 初期化 LOOP y* = argmaxy s(x(i),y) w1 = 0 IF y* ≠ y(i) THEN w2 = w1 + u1 // u 更新幅 w := w + ψi, y* w3 = w2 + u2 wa := w + t ψi, y* w4 = w3 + u3 t := t + 1 END IF より (w1 + w2 + w3 + w4) / 4 END LOOP = (3u1 + 2u2 + u3) / 4 w* := w – wa/t i = w4 – (u1 + 2u2 + 3u3) / 4 = w4 – wa/ t Multi-class Passive Aggressive Algorithm (1/2) [Crammer, JMLR 06] 1 w i 1 arg min w w i 2 w s.t. 2 l ( x (i ) , y (i ) ; w) : max( 1 w T i , y* , 0) y * : arg max y s( x, y ) l ( x , y ; w) 0 (i ) (i ) • 各訓練例に対し上の問題を順に解く 1. 今の訓練例は正しく分類でき 2. これまでの重みベクトルに一番近い • この問題は次の閉じた解を持つ w t 1 w t t i , y* t l ( xi , yi ; w ) i , y* 2 Multi-class Passive Aggressive Algorithm (2/2) [Crammer, JMLR 06] • 制約を緩めたバージョン (c.f. soft-margin SVM) 1 2 w i 1 arg min w w i C s.t. l ( xi , yi ; w) 2 w 1 2 w i 1 arg min w w i C 2 s.t. l ( xi , yi ; w) 2 w 0 (PA-II) • これらも閉じた解を持つ w t 1 w t t i , y* l ( x , y ; w ) i i t min C , 2 i , y* (PA-I) l ( xi , yi ; w ) t 2 1 i , y* 2C (PA-I) (PA-II) Multi-Class Confidence Weighted Algorithm (CW) [K. Crammer, et. al, EMNLP 09] • 多くの言語処理の問題で最高精度を達成 • 重みベクトルを単一のパラメータではな くガウス分布上N(μ,Σ)で保持する 従来の更新例 単一のパラメータ に足し引きするだけ wi 1.7 0.6 CWの更新例 wi 平均 1.7 分散 0.5 平均0.6 分散 0.4 パラメータ自体が分布を 持っている （パラメータ間も） 従来のオンラン学習器と CWとの比較 • 従来〆ある特徴の更新回数が多くても少な くても、同じ更新幅 • CW〆ある特徴の更新回数が多いなら小さい 少ない更新幅、少ないなら大きい更新幅 – 更新回数が多いならその重みには自信がある ⇒低頻度の特徴でも効率良く学習可能 ⇒学習データを一回走査するのみで高精度 CWの学習更新式 前のパラメータにKLダバージェンス で一番ちかいパラメータ 今の訓練データをη(>0.5)の確率で 正しく分類可能 この操作のため、最適化問題が凸 ではなくなってしまう CWの学習更新式 (続) • 多クラスでは次の近似を用いる 1. 全てのr≠yi についてrよりyiの方がスコゕが高 くなる確率がηより高い 2. スコゕが高い上位k個のクラスだけ考慮 3. パラメータ更新は各クラス毎に順に 各クラス のスコゕ y=4が正解 1 2 3 4 5 6 3が更新対象 5が更新対象 1 2 3 4 5 6 1 2 3 4 5 6 • 各パラメータ更新は閉じた式で得られる [K. Crammer, et. al, EMNLP 09] 殆んどのタスクで既存のオン ラン学習のみでなく通常の 学習器より高精度 News Groupsのトピック Amazonレビューの上位７タプ Amazonレビューの上位タプ EnronのUser Aの上位10フォルダ EnronのUser Bの上位10フォルダ NewYork Times Adaptive Regularization of Weight Vectors (AROW) [NIPS 09] • CWは更新時に正則化が入っていない – 今の訓練例をとにかく分類できるようにする – 訓練例にノズがある場合、急激に悪くなる • 学習時に三つの条件を同時に考慮し最適化 1. 今の訓練例を正しく分類できる CWではこれが 常に最優先 2. 前のパラメータと近づける 3. 各特徴のConfidenceを更新毎に上げる • CWと同じように閉じた式で更新可能 AROWの実験結果 ノズ 0% ノズ 10% ノズ 30% • 左上にあるほどAROW > CW • ノズ大⇒AROWの精度>CWの精度 一般の損失関数の場合 • 問題毎に最適な損失関数は変わってくる – タスク固有の損失関数など • 任意の損失関数を利用した学習も オンラン化可能 ⇒確率的勾配降下法 確率的勾配降下法 (1/3) (SGD: Stochastic Gradient Descent) • 勾配降下法 – F(w)を最小化するwを探す場合、 勾配 ∂F(w)を求め w := w – τ ∂F(w) と更新 （τ〆ステップ幅） • 確率的勾配降下法 – ∂F(w)を一部のデータの勾配で近似 :v≒∂F(w) w := w – τv – τ = 1/λ(t+t0) (tはステップ数, λは適当な定数) ステップ幅は段々小さく（APと似ている） 確率的勾配降下法 (2/3) w = {0,0,…,0} // 初期化 loop i1 i2 ..～ [1,…,n] // 訓練例からランダムにサンプル {(xi1, yi1), (xi2, yi2)…}から勾配∂F(w)の近似vを求める // サンプルに対する勾配を求める τ = 1/λ(t+t0) w := w – τv t := t + 1 end 確率的勾配降下法（3/3） • 任意の損失関数をオンラン化可能 – 勾配を求める部分をさぼるだけ！ – パーセプトロンもSGDの一種 • 収束は非常に速い – 訓練例が冗長なため • パラメータλ, t0などは最初に訓練例の一部 からサンプリングし、求める場合が多い – 完全に自動化可能 確率的勾配法 例 log-loss (ME, ロジステゖック回帰） L( x, y, w ) log y ' exp( w y ' ) T ψy‘ := Φ(x, y) - Φ(x, y‘) L / w y ' I ( y ' y ) p( y ' | x; w ) ( x, y ' ) p(y1|x; w) = 0.3 p(y2|x; w) = 0.6 p(y3|x; w) = 0.1 正解がy1の時 w := w + τ( 0.7Φ(x, y1) – 0.6 Φ(x, y2) – 0.1 Φ(x, y3) ) 正解で、確率が低い 場合、大きく更新 不正解で確率が高い場合、 大きく更新 モデルのコンパクト化 • パラメータ数は数百万～億と非常に巨大 – 実際に利用する時に計算コストが高い – 例〆組み込み機器などで使いたい • 事前に特徴選択は難しい – 単純な打ち切りは精度に悪影響 – タスク毎に効く特徴が違う ⇒L1正則化を学習時に適用する – 学習時に特徴選択も同時に行う L1正則化 n F (w) l ( xi , yi ; w) w 1 i 1 w 1 | wi | i • 重みの絶対値の和をペナルテゖに利用 – Lasso正則化とも呼ばれる – c.f. L2 正則化|w|2= ∑i wi2 • これは凸関数 – wi =0 で微分不可能 – ちなみにL0（wi≠0の個数）の場合はNP完全問題 L1正則化による学習結果の特徴 • L1正則化の場合、多くの重みが0になる – 特徴選択が最適化の中で自然に実現できる – 学習結果が分かりやすく、推定が高速、メモ リも少なくて済む – NLPの実験ではL2と比べて特徴数は約1/20 だが精度はほぼ同じ – L2の場合、全ての重みが0にならない 直感的な理解 各重みは損失関数を 減らそうと0から離れようと するが、ペナルテゖがかかる |w|1 |w|2 w 0 ∂|w|1/∂w (0方向に押す力） w 0 ∂|w|2/∂w |w|2の場合,0に近づくと ペナルテゖは急速に 小さくなる 全ての重みは0の近くまで 行けば生き残る それに対し|w|1の場合は 勾配は常に一定なので 必要がない重みは 0に押しつぶされる L1正則化の意味付け • 重みの事前分布にLaplace分布を考えた場 合の事後確率最大推定（MAP推定） – 少数の大きい重みからなる – c.f. L2正則化の場合はGaussian分布 で、多数の小さい重みからなる • 重みの0方向への定数のdiscount – v* = p( w | , ) argminv |v-w|2 s.t.|w|1<C の解は vi = sign(wi)max(|wi |– θ, 0) 但し、 θはw, Cから決まる定数 [Duchi+ 1 | x | exp 2b b 08] 学習手法の比較実験 [Gao+ 07] • 5種類のパラメータ推定手法を様々なタス クに適用 • L1正則化が流行るきっかけ [Gao+ 07] の実験結果のまとめ • 5つの全く違うタスクをやったが結果は同じ – L2がわずかに勝っているが、L1、Averaged Perceptronも殆ど同じ性能 • L1はスパースな解 – L2-の1/10～1/100の有効な特徴数 • 性能がちょっとでも欲しい⇒ L2 • スパースな解を得たい ⇒ L1 • 実装が簡単 ⇒ Averaged Perceptron L1正則化付の最適化問題 • 凸最適化問題だが、微分が求められないため 一般の最適化法は使えない – wi = 0で微分不可能で、最適解はこの周り • バッチ学習はいろいろ提案されている – 差分表現による最適化 [Kazama+ 03, EMNLP] – OWL-QN [Andrew+ 07, ICML], 内点法 [Koh+ 07, JMLR] – Multiplicative Update [Sha+ 07, IDA] • 今回はオンラン学習を紹介 – FOBOS [Duchi+ 09] – L1正則化 + 累積更新 [Tsuruoka+ 09] FOBOS (1/4) (FOrward Backward Splitting) [Duchi+ 09] • f(w) + r(w)を最小にするwを求める – f(w)は微分可能 （例〆損失関数の和） – r(w)は微分不可能（例: |w|1) • 最初にf(w)のみを最小化し、その結果に近 いものでr(w)を最小化するwを求める f(w)のみでの勾配降下法 (gtf = ∂f(wt)) FOBOS (2/4) • 先ほどの二番目のステップは 単純な閉じた解が得られる場合が多い • 例1. r(w) = |w|1の場合 – wt+1/2 = (0.5, -1.0, 2.0, -0.7, 1.4)、λ=1 の時 wt+1 = ( 0, 0, 1.0, 0, 0.4) • 例2. r(w) = |w|22の場合 wt 1 wt 1 2 /(1 ) FOBOS (3/4) • 例3. Berhu正則化（0からγまでL1, γからL2) • 複雑な正則化も混ぜたり自由にできる – L1とL2とL∞を同時に与える FOBOS (4/4) • バッチ学習と殆ど同じ結果が得られる – 同時期に提案された似た手法も同様の結果 – 理論的にも近い結果が得られることが保障 • 実装は非常に簡単 – 既存のオンラン学習に１行加えるだけ – 「L1は引く、L2は割る」 FOBOS 擬似コード 問題〆f(w)+r(w)を最小化 w = {0,0,…,0} t=1 loop – w = w – μ∂F(w) – λ = λ0/(1+t) – for each i • wi := sign(wi) max(|wi|-λ, 0) // r(w)=|w|1 wi / (1+λ) // r(w)=|w|22 – end for – t := t + 1 • end loop • • • • L1正則化+SGDの累積更新 (1/2) [Tsuruoka+ ACL 09] • L1正則化付のSGDは毎回重みに対し0方向 に近づくようなペナルテゖを与える • この更新は不安定 – 重みを0に押し出す前に終了する可能性 • 更新時にL1更新の累積分をまとめて与える • 学習率に指数減衰を採用する – ηk = η0α-k/N – 収束する保証はないが、現実的には問題無い L1正則化の工夫 (2/2) [Tsuruoka+ ACL 09] w := 0, q = 0, u := 0, k := 1 loop i ～ random(1, n) 前回の更新時から、今回の更新までのL1 η := η0α-k 正則化に関するペナルテゖをまとめて u := u + ηC/N 与える for each t∈{t|Φt(x(i))≠0} （終わり頃に初めて出現した特徴に対しても 強いペナルテゖを！！） wt := wt – η∂F(w)/ ∂wt c.f. FOBOSは毎回同じペナルテゖ z := wt wt := sign(wt)(|wt|– (u + qt)) qt := qt + (wt – z) end for end loop [Tsuruoka+ ACL 09] バッチ学習と比べて高速であり、 収束は非常に速い 精度はバッチ学習と差が殆どない 教師無学習〆EMゕルゴリズム （期待値最大化法） • p(x, z; θ) – x〆 観測可能な変数 （例〆単語） – z〆観測できない変数 （例〆品詞） – θ〆 パラメータ （品詞から単語の確率等） • データの尤度L(X, θ)を最大化する – 副作用的に、Zを求める argmaxz p(x,z;θ | X,Z) • E-step – 今のθでのzの期待値q(z|x)を求める ⇒ペゕ(x,z)の出現回数を数えるだけ • M-step – 今のzでL(θ)を最大化するθを求める Online EM (1/2) [P. Liang, D. Klein, NAACL 09] • EMは収束が非常に遅い – 品詞推定でも繰り返しが百回強必要との報告 • オンラン学習と同じようにデータを観 測するたびにパラメータを即時更新する – パラメータは各隠れ変数の条件付確率など • 非常に速く収束 Online EM (2/2) • ca[t] : 条件aで事象t が起きた回数 – M-stepはca[t]から求められる統計量を使う – 例 p(t|a) = ca[t] / ∑sca[s] LOOP i ～ random(1, n) c‘a[t]を今のcaを利用して計算（E-step) μt = (t+1)-α ca[t] := ca[t] + 1/(1-μt) c’a[t] t := t+1 END LOOP オンランEM 結果例 観測可能 • 隠れマルコフモデル (HMM) – P(隠れタグ⇒隠れタグ) P(隠れタグ⇒出力） • ohmmを利用 • 日本語の単語推定 – 文数 10万 – 単語数 200万 – 単語種 7万 – 隠れクラス数 20 最初の変化は大きい単語の クラスが決まるだけで あまり意味ない 従来EMは約100回 程度で収束 オンラン学習 まとめ々補足 • オンラン学習はより汎用かつ強力に – 教師有、教師無、正則化付、劣モジュラ最適 化[Hazan+ NIPS 09] など多くの問題がオンラン化 が可能 • これまで解けなかった問題が解ける – arg maxys(x,y)かその近似が求められればよい – MCMC で近似解: Sample Rank [Culotta+ 07] 言語情報の効率的な保持、操作方法 疎ベクトルと文字列データ構造 疎ベクトル • 値の多くが0であるようなベクトル – 例〆Φ(x) = {0, 0, 0, 1,0, 0, 0, 2, 0, 0, 0, 1, 0, 0} – NLPの特徴ベクトルの多くは疎 • 大規模なデータを扱う場合、疎ベクトル を効率的に格納し、操作する必要がある • 疎ベクトルは値が0ではない添字集合と値 集合のペゕで表される – Φ’(x) = (4:1), (8:2), (12:1) 添字集合の格納 • 添字集合 = 昇順の整数列v1 v2 ... vm – 0 ≦ v1 < v2 ... < vm < nの時〃保存領域の下限は log2 nCm = 1.44 m + m log2 (n/m) bits • 例 n = 220 m = 216 – そのまま 〆216 *4B = 256KB 下限〆43KB • 目標〆サズが小さく復元速度が速い • 代表的な五種類の格納方法を紹介 – VarByte, Rice符号, S9, S16, PFOR 添字集合の格納 VarByte • 差分列 : di := vi – vi-1 -1 (d1=v1) – di は小さい値になっていると期待される • 各値を可変長バトで表現 – 小さい値を少ないバト数で表現 while x >= 128 putchar (x & 0x7F) x >>= 7 putchar (x + 128) 1110010101012 (1) 7 bitずつに 区切る 01010101 10010101 (2) 先頭に後続バトが あるなら0, ないなら1をつけて出力 添字集合の格納 Rice符号 • • • • b := log2 n / m 各 x∈ {di} (i=1...m) を次のように符号化 下位 b bit はそのままbinary符号で記録 残りの上位bit は unary符号で記録 – これは2m + m log2 n / m bits を達成 (下限は1.44m + ...) 1010101012 102= 001 11011110002 1102= 0000001 00101012 02= 1 0011010101 00000011111000 10010101 unary 符号〆整数 x を x個の0の後に1をつけた二進数で表す 添字集合の格納 S9, 16 • S9 (Simple 9) [V. Ahn+ J. 06] – 同じbit幅で可能な限り32bitに詰め込む – 上位4bit = 何番目の方法か – 下位 28bit = 実際の中身 – 9通り [x, y] = x bit が y個 [1,28][2,14][3,9][4,7][5,5][7,4][9,3][14,2][28,1] – 場合分けをハードコーデゖング • S16 [J. Zhang+ 08] – 16通りのビット幅パターン 添字集合の格納 New PFOR [H. Yan+ 09] • 128個の整数毎にそれらのうち90%が記録 できるbit幅をbとする • 下位b bitは128b bitを利用して記録 • b bit で記録できなかった整数については、 それらの間隔, 及び上位bitをSimple 16で記 録 • 全てのbit幅の復元をハードコーデゖング • 分岐がほぼ無い 結果 [H. Yan+ 09] 復元速度 (106 整数/ 秒) サズ (MB/term) VarByte Rice S9 S16 New PFOR 637 489 748 691 1055 4.7 2.5 3.0 2.8 3.1 • 速度: New PFOR > S9, S16, Var-Byte > Rice • サズ: Rice < Var-Byte, S16 , S9 < New PFOR • 秒間10億弱の整数を復元可能 疎ベクトルの操作 密ベクトルとの内積 • 疎ベクトルと密ベクトルの内積 – 例: wTΦ : wは密ベクトル Φは疎ベクトル • 疎ベクトルを順に復元し掛け合わせる ret := 0 while {v ,a}を復元 // vは添字番号 aは値 ret += w[v] * a 疎ベクトルの操作 疎ベクトル同士の内積 • 疎ベクトルと疎ベクトルの内積 – 例 : ΦtΦ : Kernelの計算など 1. マージソート 2. スキップベース 3. 転置フゔルを利用する 4. Hash-Based（次章） 疎ベクトル同士の内積 (1/3) ソート済み マージソート • 入力 : 添字集合 {x1 ... xm}, {y1 ... ym’} 値集合 {a1 ... am} , {b1 ... bm’} i=k=0 ret = 0 // 内積の値 while i < m && k < m’ if (xi < yk) i := i+1 else if (xi > yk) k := k+1 else { ret := ret + aibk; i := i+1; k := k+1 } end while 計算量はO(m + m’) 疎ベクトル同士の内積 (2/3) スキップベース ソート済み • 入力 : 添字集合 {x1 ... xm} , {y1 ... ym’} 値集合 {a1 ... am} , {b1 ... bm’} i=k=0 ret = 0 // 内積の値 yk ... ym’ 中のxi以上の最 初の値 while i < m && k < m’ k := lower_bound(y, xi , k) if (xi == yk) ret := ret + aibk ; i := i+1; end while 計算量はO(m log m’/ m) 疎ベクトル同士の内積 (3/3) 転置フゔル (1/2) • 添字番号の集合に対する転置フゔルを 作る 特徴番号 1 訓練 番号 2 1 1 2 1 3 4 3 4 5 7 1 8 1 1 2 1 1 3 5 6 6 1 {(1:1) (8:3)} {(6:1)} 1 2 従来の特徴ベクトル {(2:1) (5:1) (8:1)} {(2:1) (7:1)} {(3:2) (7:1)} 2 (4:1) (1:1) (3:2) (1:1) (5:1) (2:1) (1:1) (2:1) (6:1) (3:1) (4:3) (6:2) 転置フゔル (6:2) {(2, 2) (5,1) (7,2)} 疎ベクトル同士の内積 (3/3) 転置フゔル (2/2) • Φ(x)の発火した特徴が他で発火した場所を 効率的に求められる 特徴番号 1 訓練 番号 2 1 1 2 1 3 4 3 4 5 7 1 8 1 Φ(x2)と他の特徴ベクトル 全てとの内積を測る 3 Φ(x2)中の発火した特徴に 関する転置フゔルを 調べ、内積を計算 1 2 1 1 5 6 6 1 2 1 2 (4:1) (1:1) (3:2) (1:1) (5:1) (2:1) (1:1) (2:1) (6:1) (3:1) (4:3) (6:2) 転置フゔル (6:2) 内積1回あたりの 計算量はO(m) 文字列データ構造 • 大規模テキスト処理には〃効率的なデー タ構造の使用が不可欠 – 線形、またはそれに近いオーダーで 計算量々リソース量がスケールするように • 研究は2000年以降大きな進展 – ゲノム解析や大規模情報検索で研究が進む • 数百GBのテキストは通常のPCで処理可能 – 辞書情報も数億キーワードはメモリに載る 文字列データ構造 • 全文索引 – 接尾辞配列 – 接尾辞木 – 拡張接尾辞配列 – Burrows Wheeler 変換 • 簡潔木、簡潔Trie • ゕプリケーション例 – 全部分文字列を利用した文書分類 例題 • 文書集合中に出現する全ての部分文字列の頻 度を計算する – 長さや文字種での制約は一切しない • Wikipedia (約1GB,100万文書)が20分弱で処理可 能 – 京大コーパス、Penn-TreeBankなら1秒 – テキストがメモリに載る限り線形にスケール （全部分文字列種類数は文長Nの時N2だが、 それらはN個のグループにまとめあげられる） 定義 • • • • • T[1,n] : 長さnの文字列 Σ, σ = |Σ| : 文字の集合、文字種類数 T[i] : Tのi番目の文字 T[i,k] : Tのiからk文字目の部分文字列 Si := T[i,n] : Tのi番目の接尾辞 – i文字目より後ろの文字列 • 例〆T[1,11] = abracadabra$ T[2,5] = brac S5 = cadabra$ 接尾辞配列 • Tの全ての接尾辞を辞書式順序でソート • 接尾辞の添字を格納する O(n log n) bits S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 abracadabra$ bracadabra$ racadabra$ acadabra$ cadabra$ adabra$ dabra$ abra$ bra$ ra$ a$ $ S12 S11 S8 S1 S4 S6 S9 S2 S5 S7 S10 S3 $ a$ abra$ abracadabra$ acadabra$ adabra$ bra$ bracadabra$ cadabra$ dabra$ ra$ racadabra$ 12 11 8 1 4 6 9 2 5 7 10 3 接尾辞配列による探索 • 任意の部分文字列q[1...m]の出現場所を SA Suffix O(logN)で探索 12 $ クエリ qが出現している範囲は SA上の二分探索で求められる 11 a$ 8 abra$ 1 abracadabra$ sp = max {i | q ≦ T[SA[i], n]} ep = min {i | q ≧ T[SA[i], n]} 4 acadabra$ 6 adabra$ 9 bra$ SA[sp, ep]がqが出現している 場所の集合 2 bracadabra$ 5 cadabra$ 7 dabra$ 10 ra$ 3 racadabra$ クエリが q = abra の場合 文書集合に対する接尾辞配列 • 文書をつなげた文字列Tを考える – T = d1#d2#d3#....dN# – #iは文書中に現れない文字 – 各文書の開始位置をoffsets[1...N]に記録 • Tに対する接尾辞配列を構築 • 検索結果を文書集合に変換 – それぞれの位置をoffsetsを利用して、文書番 号と文書内の位置に変換 接尾辞配列の進展 • 高速、省スペースな構築 : SAIS [Nong+ 09] – O(N) 時間、N log2 N bitsで構築可能 • 文字種類数に依存しない • 最新PCで必要時間は 4MB / 秒 • UTF-8単位を入力文字として接尾辞配列を構築 した場合、サズは入力1byteあたり4/3byte（お得！） – 高品質のオープンソースが利用可能 • SAISで検索 • 文書の追加々削除 [Gonzalez+ 09] – 長さkの文書をO(k log n)時間で追加可能 接尾辞木 • 入力Tの全ての接尾辞からなるTrie – 但し、子が一つしかない節点は除く – 内部節点の数は高々 N-1個 • 非常に多くの文字列処理が効率的に解ける [Gusfield+ 07] • 現在では作業領域が大きい接尾辞木の代わり に拡張接尾辞配列が利用されることが多い – 接尾辞配列 + BWT + Height配列 入力 abracadabra$に対する接尾辞木 接尾辞木 i 12 $ 11 bra $ 8 c c a 4 d 6 bra $ c c d ra $ 9 2 5 7 $ c 10 3 1 SA 1 2 3 4 5 6 7 8 9 10 11 12 接尾辞 12 $ 11 a$ 8 1 4 6 9 2 5 7 10 3 abra$ abracadabra$ acadabra$ adabra$ bra$ bracadabra$ cadabra$ dabra$ ra$ racadabra$ 85 Burrows Wheeler 変換 (BWT) [Burrows+94] • T[1...n]をB[1...n]に次のように変換 – B[i] = T[SA[i]-1] (但し SA[i]=1の時 B[i] = T[n]) • 次のような特徴がある – BのみからTを復元可能 (可逆変換） – Bは非常に圧縮しやすい (c.f. bzip2) – 接尾辞配列と同じ情報を持つ (c.f. FM-index) • BWTの構築にはSAを経由せず直接構築す る手法が提案されている [Okanohara+ 09] Height 配列 • H[1...n] : 次のように定義される配列 – H[i] := T[SA[i]...] と T[SA[i+1]...]の一致長 – 辞書式順序で隣り合う接尾辞の一致長 • 接尾辞木中にSA[i...k]に深さdの節点が存在 ⇔ (1) H[t]≧d for all t∈[i...k-1] (2) H[i]<d, H[k] < d (3) H[t] = d for some t∈[i...k-1] • HはSAを利用してO(N)時間で構築可能 [Kasai+ 04] i SA H B suffix 1 12 0 a $ 12 2 3 4 11 1 8 4 1 1 r a$ d abra$ $ abracadabra$ 11 $ bra $ c c 5 4 1 Suffix Tree $ a r acadabra$ 6 6 0 c adabra$ 7 8 9 10 11 12 9 2 5 7 10 3 3 0 0 0 2 0 a a a a b b bra$ bracadabra$ cadabra$ dabra$ ra$ racadabra$ 8 1 4 d 6 bra $ c c d ra 9 2 5 7 $ c 10 3 88 全部分文字列の統計量計算 (1/3) • 文書集合中に出現する全ての部分文字列 の統計量を求める – tf(q) : 部分文字列qの頻度 – tf-d(d, q) : 文書d中の部分文字列qの頻度 – df(q) : qが出現する文書数 – df-k(q) : qがk回以上出現する文書数 全部分文字列の統計量計算 (2/3) [事実1] 接尾辞木中で同じ枝に対応する部分文字列の出 現位置は全て同じ [事実2] 接尾辞木中で、各位置の直前の文字(BWT)が全 て同じ（aとする）部分文字列Sは部分文字列aSと出 現位置は全て同じ ⇒位置が全て同じ部分文字列の中で最長の文字列を 極大部分文字列と呼ぶ 枝の数は高々n-2本なので、出現頻度（位置）が異なる 部分文字列、極大部分文字列の数は高々O(n) 全部分文字列の統計量計算 (3/3) 1. 文書集合の文字列データ構造を構築 – 線形時間で構築可能、元テキストの6～9倍 2. Hを利用して接尾辞木中の節点を列挙 – H[1], H[2]...を順に調べ、スタック Sを管理 (1) 大きくなる場合S.push, 節点の開始位置 (2) 小さくなる場合S.pop, 節点の終了位置 3. 各節点で直前の文字(B)が全て同じでなけ れば、それは極大部分文字列 abra abr ab bra br ra b r の出現位置は全て同じ(8,1) B a 12 r d $ 11 $ bra $ 1 r c bra a a a a b b c 4 d 6 $ c 9 2 c d 2 5 1 T=abracadabra$ T=abracadabra$ T=abracadabra$ T=abracadabra$ T=abracadabra$ T=abracadabra$ ≠ T=abracadabra$ (11,1,8,4,6) 7 ra 8 0 c a 4 $ $ 10 3 c 3 接尾辞木の同一枝中の 部分文字列の出現位置 は同じ 92 ゕプリケーション例 全部分文字列を利用した文書分類 [Okanohara+ 09] • 全ての部分文字列からなるBOW表現 – 部分文字列長や特殊文字などで制限はしない – 発火する特徴数は文書長の二乗に比例 • 線形識別器を利用して分類 – カーネルは使わず陽に特徴を表す – Φ(D) ∈R∞ 文書Dに対する特徴ベクトル – w∈R∞ 各素性に対する重み s(D, y) = wT Φ(D, y) 93 効率的な勾配の求め方（続） • 特徴種類数が多いため、全ての特徴について の勾配を列挙し最大値を求めるのは困難 • これを解決するのにさきほどの補題を利用 補題〆出現場所が異なる部分文字列の数は文 書長より少ない – 長さNの文書中に出現する文字列種類数は O(N2)だが、出現場所が同じものをまとめ ると、高々N個のグループにまとめられる – 勾配の統計量は位置に依存するため、勾配 も高々N個に関して求めればよい 94 補題の適用 • 訓練データ (xi,yi) (i=1…N)に対し入力をつ なげた文字列〃T=x1$1x2$2…xN$N を考える〄 – ただし$iは本文中には出現しない特殊文字 • このTに対し先程の補題を適用 ⇒各訓練例で特徴値（そして勾配）が異なる特 徴種類数は多くてもN-1個 95 実験結果 1 精度評価 BOW + L1正則化付LR GreedyにN-gram 特徴を追加 提案手法が全データセットで高い精度を達成 BOW+L1は表現力が非常に低い場合がある SLRはgreedyに部分文字列を選択するため、最適な 部分文字列を抽出できていない可能性 96 実験結果2 スケーラビリテゖ • テキストに対し〃勾配を計算するのに要した時間〄 • テキストサズに対し線形 97 簡潔木々簡潔Trie • 木構造はそのままではサズが大きい – 1ノードあたり〃数十バト • 簡潔木 – 操作時間は定数のまま、1ノードあたり2bit • 簡潔Trie = 簡潔木 + 枝情報 – 非常に大規模な辞書情報を効率的に格納 – Google IME での辞書管理 (txのクローン） – 言語モデルの管理 [....] Trie (prefix tree) • 木構造〄枝に文字がついている〄根から 葉へのパスが各キーに対応〄 – 共通接頭辞を持つキーをまとめて検索可能 t w i e a o n n e n キー : "to", "tea", "ten", "i", "in", "inn“, and “we”. LOUDS: Level-Ordered Unary Degree Sequence [Jacobson 89, O’Neil Delpratt 06] • 木をBFSで辿り〃k次のノードを行きがけ に k個の’1 ‘と1個の’0’で表す – 先頭にSuper Root S（番人）を追加 – n個の節点からなる順序木にはn個の1, n+1 個の0が出現する 1 3 2 4 5 6 7 S 8 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 LOUDS (続) • i番目の節点は1と0の2回表現されている – 親から子を指す時 i番目の1で表現 – 子の中では(i+1)番目の0で表現 • 今回はi番目の節点とi番目の1を対応させ る 1 3 2 4 5 6 7 S 8 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 5番目の1 (5+1)番目の0 LOUDS上での操作 • B[i]に対応するノードに対する各操作 – 最初の子 = select0(B, rank1(B,i)-1) + 1 – 最後の子 = select0(B, rank1(B,i)) - 1 –親 = select1(B, rank0(B,i)-1) – 次の兄弟 = i+1 1 3 2 1 S 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 4 5 6 7 8 2 実際確かめてみよう Trieの枝情報の表現 • E[i] = i+2番目の節点に向かう枝の文字 – Eは長さn-1の配列 • 枝にcが付いている子を探す場合 – for (int j = rank1(B,i)-2; B[i] != 0; i++, j++) if (e[j] == c) break; // found c 1 a b 4 2 c 5 S c 3 d a 6 7 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 b 8 E = [acbcdab] Q = “ad”を検索する例 • 初期状態 i = 2; // root – j = rank1(B, i)-2; // 0 E[0], E[1],..,を探す E[0]でaが見つかる – i = select0(B, rank1(B,i)-1) + 1 + 0; // 5 – j = rank1(B, i); // 2 E[2], E[3], …, を探す E[4]でdが見つかる 1 a b 4 2 c 5 S c 3 d a 6 7 b 8 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 E = [acbcdab] Trieの格納情報の表現 • T[i] = i+1番目のノードに情報を格納してい る場合は1, そうでない場合は0の配列 – 格納した情報は配列A[0..]に入れておき、 – i番目のノード情報へのゕクセスは A[rank1(B, i) – 2] と行える 1 a b 4 2 c 5 S c 3 d a 6 7 b 8 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 E = [acbcdab] T = [1011111] 実験 • 入力データ Web 1T 5-gram Version 1 – 1gramのリストから出現頻度を除いたもの – キーワード種類数: 13,588,391 – キーワードの総長: 112,349,445 bytes – trie中の葉も含めたノード数: 34,722,820 疎ベクトル々文字列データ構造 まとめ々補足 • 適切なデータ構造を利用することで、必要な 作業領域は元の1/10～1/100に – 高速な記憶領域上で解くことができ 非常に速く計算できる • 圧縮して格納したまま扱える – 毎回全部を復元する必要はない • 関連研究の進展は非常に著しい – キーワード〆“succinct data structure”, “compressed index” – fujimap : succinct な連想配列 複雑な操作々情報をシンプルかつスマートに扱う 乱択化アルゴリズム Hash Feature • 特徴関数の保存コストが問題になる – NLPにおいて特徴関数は文字列で表される 例〆”prev/This/cur/is” : This is というbi-gram – 特徴関数から重みへの対応表の管理が大変 – ラベル種類数が多い場合も問題 • 重みベクトルの長さは特徴種類数＊ラベル種類数 ⇒特徴関数をhash関数で実現する – 特徴から特徴番号[1...m]へ写像するハッシュ関数 – 衝突する可能性があるが少しの工夫でうまくいく Random Feature Mixing [Ganchev+ ACL workshop mobile NLP 06] • 文字列からハッシュ番号[1...m]を求め、そ のまま特徴番号として利用 実験データ: 20 news groups, Reuters, sentiment, spam ハッシュを利用しない場合の精度を1とした場合の精度 赤が各種法の精度、灰色が標準偏差 10-cross validation Hash Kernels (1/3) [Shi+ JMLR 09] • Mercer Kernel: K(xi, xk) := <Φ(xi), Φ(xk)> – 二要素間の近さを特徴ベクトルの内積で定義 • Kernel Trick – 特徴ベクトルの次元が非常に大きくても 効率的に解ける場合がある – 多項式カーネル, RBFカーネル • Hash Trick – 特徴ベクトルをハッシュ関数で低次元ベクトル に潰し、そこで内積を測る Hash Kernels (2/3) Hash Kernel • 入力: x Φi(x) := Σk:h(k)=iξ(k)xk <x,x’>Φ := Φ(x)TΦ(x’) – 各特徴は文字列で表されているとする • h : 特徴から[1,...,m]へのハッシュ関数 • ξ : 特徴から{-1,+1} へのハッシュ関数 – 注〆ξがないと、バゕスは0にならない Hash Kernel 例 BOW表現 単語 are books tf 1 3 ξ +1 -1 h 3 0 interesting expensive funny 1 1 2 -1 +1 -1 2 0 2 i Φi 0 1 2 -2 0 -3 3 1 h(“funny”) = 2 単語表、特徴関数などは持たずに、特徴をv∈[1...m]に写像する ハッシュ関数があればよい Hash Kernel (3/3) 性能保証 • HKによる推定はバナスが無く、分散は |x|2=|x’|2=1のときO(1/m) – バゕス : E Φ[<x,x’> Φ] – バゕスが無い : E Φ[<x,x’> Φ] = xTx’ – 分散 : σx,x’ = E Φ[<x,x’>2 Φ] - E Φ[<x,x’> Φ]2 • |<x,x’>Φ-<x,x’>|が大きくなる確率は非常に 低い – 誤差εより大きくなる確率はO(exp(-ε1/2)) SVD + 乱択化ゕルゴリズム (1/3) [G. Martinsson+ 09] • SVD (特異値分解） – 多くの自然言語処理の基礎タスク (LSI等) – SVDは行列演算における万能ツール PCA, Page Rank, 緩和K-means など • A = U Σ V* (特異値上位k個に対するSVD) m k k n A = n U k Σ m k V* U, Vの各列は正規直交基底 Σは特異値からなる対角行列 SVD + 乱択化ゕルゴリズム (2/3) 入力: n×m 行列 A 出力: Aのrank k近似 A ≒ UΣVT 1. 2. 3. 4. 5. 6. Aがノズを含む場合やA を一回しか操作しない versionもある [Martinsson+ 09] Ω∈m×k’ ランダム行列を生成 Y := AΩ ∈ n×k’ サンプリング行列を計算 Q∈n×k’ Yの列に対する正規直交基底を計算 B := QTA ∈k’×m 小さいので高速 T BのSVDを計算 B = U’ΣV U = QU’ (A = QQTA = QB = QU’ΣV) k’ := k+p (pはオーバーサンプリングで10程度） 従来 O(mn2) →O(n2k) SVD + 乱択化ゕルゴリズム (3/3) • SVDでrank-lで近似した場合のエラー 乱択化ゕルゴリズム まとめ々補足 • 乱択化によるメリット – 作業領域量を大幅に減らせる • 組み合わせ素性、部分文字列素性 • 本質的なパラメータ数が少ない場合は特に – 実装が非常に単純化される – （デメリット）デバッグは難しい • 多くのNLPデータは冗長 – もともとデータがノズに対してロバスト – 乱択化との相性は良い 高速化の基本方針 最後に 最後に (1/2) 高速化の原則 • 人的リソースがボトルネック ⇒楽にできるものから順に適用する 1. 利用しているラブラリの変更 – 例 libsvm -> liblinear, oll 2. 調査＆実装の改良 – callgrind, cachegrind, memusage等で性能調査 3. ゕルゴリズムの変更 4. リソースを増やす 最後に (2/2) 高速化の原則 • 上位のメモリで処理するのが最重要 – 現在主流のゕーキテクチャでは 記憶装置間の速度差が非常に大きい – 扱うデータをできるだけコンパクトに – CPUレジスタ > キャッシュ > Memory > HDD • キャッシュ予測が効くように実装 – 前/後から順番に小さいブロック毎にゕクセス • やりすぎない まとめ • これまで困難だった問題は最新の結果を 利用することで誰にでも解けるように – キーワード〆オンラン学習、データ構造、 文字列ゕルゴリズム、乱択化ゕルゴリズム – 実装は簡単かつ • 高速化は自然言語処理の重要なテーマ – 大規模化⇒精度向上 – 実用的なNLPゕプリのための重要フゔクター 出典 • • • • [Brants+, EMNLP 07] “Large Language Models in Machine Translation”, Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, Jeffrey Dean, EMNLP 2007 [Suzuki+. ACL 08] "Semi-Supervised Sequential Labeling and Segmentation using Giga-word Scale Unlabeled Data", Jun Suzuki, Hideki Isozaki, ACL-HLT 08 [柴田 NLP09] ”超大規模ウェブコーパスを用いた分布類似度計算”, 柴田 知秀, 黒橋禎夫, NLP 2009 [T. Koo+ ACL 08] “T. Koo, X. Carreras, and M. Collins. Simple Semi- supervised Dependency Parsing. ACL, 2008. • [I. Yamada+ EMNLP 09] I. Yamada, K. Torisawa, J. Kazama, K. Kuroda, M. Murata, S. D. Saeger, F. Bond, A. Sumida, EMNLP 2009 • • • • • • • • • [S. S.-Shwartz 07] “Online Learning: Theory, Algorithms, and Applications”, Shai Shalev-Shwartz, The Hebrew University of Jerusalem Ph. D thesis 2007 [Hazan 09] “The convex optimization approach to regret minimization”, E. Hazan, 2009 [Collins 02] “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. EMNLP 2002, [Crammer, JMLR 06] “Online Passive-Aggressive Algorithms”, Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, Yoram Singer, Journal of Machine Learning, 2006 [Dredze+ 08] “Confidence-Weighted Linear Classification”, Mark Dredze, Koby Crammer and Fernando Pereira , ICML 2008 [Crammer+ 08] “Exact Convex Confidence-Weighted Learning”, Koby Crammer, Mark Dredze and Fernando Pereira, NIPS 2008 [Duchi + 08] “Efficient Projections onto the L1-Ball for Learning in High Dimensions,” John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra, International Conference on Machine Learning (ICML 2008) [Gao+ 07] “A comparative study of parameter estimation methods for statistical natural language processing”, ACL 2007 [Duchi+ 09] “Online and Batch Learning using Forward Looking Subgradients “, John Duchi¤ Yoram Singer [K. Crammer+ NIPS 09] “Adaptive Regularization of Weight Vectors”, K. Crammer, A. Kulesza, M. Dredze [Weinberger+ ICML 09] Feature Hashing for Large Scale Multitask Learning, K. Weinberger, A. Dasguputa, J. Attenberg, J. Langford, A. Smola, ICML 09 [Shi+ JMLR 09] Hash Kernels for Structured Data, Q. Shi, J. Petterson, G. Dror, J. Langford, A. Smola, S.V.N. Vishwanathan, JMLR 09 [Duchi+ 09] “Online and Batch Learning using Forward Backward Splitting”, John Duchi and Yoram Singer, NIPS 2009, JMLR [Mann+ 09] “Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models”, NIPS 09 [Hazan+ NIPS 09] “Beyond Convexity: Online Submodular Minimization”, E. Hazan, S. Kale, NIPS 2009, JMLR [Culotta+ 07] “LEARNING AND INFERENCE IN WEIGHTED LOGIC WITH APPLICATION TO NATURAL LANGUAGE PROCESSING”, A. Culotta, Ph.D Thesis, 07 [Zhang+ 07] “JointWord Segmentation and POS Tagging using a Single Perceptron”, Y. Zhang and S. Clark, ACL-HLT 08 • [Gusfield 07] Gusfield, “Algorithms on Strings, Trees and Sequences:” , 1997 • [Navarro+ 07] G. Navarro, V. Makinen, “Compressed full-text indexes”, ACM Computing Surveys (CSUR), Volume 39 , Issue 1 2007 [D. Okanohara+], D. Okanohara, K. Sadakane, “A Linear-Time Burrows-Wheeler Transform using Induced Sorting”, SPIRE 2009 [J. Siren+09] Jouni Sirén, “Compressed Suffix Arrays for Massive Data”, SPIRE 2009 [Hon+ 09] W.K.Hon, R. Shah, S. V. Thankachan, and J. S. Vitter “On EntropyCompressed Text Indexing in External Memory”, SPIRE 2009 [G. Martinsson+ 09] “Randomization: Making Very Large-Scale Linear Algebraic Computations Possible”, NIPS 2009 Tutorial • • • • 補足資料 データ取得先 • Wikipediaデータの取得先 • 日本語Wikipedia – http://download.wikimedia.org/jawiki/latest/jawi ki-latest-pages-articles.xml.bz2 • 英語Wikipedia – http://download.wikimedia.org/enwiki/20100130/ enwiki-20100130-pages-articles.xml.bz2