本エントリではPythonのJoblibがもつキャッシュ機能によって同じ計算を省略し、処理を高速化するための方法を説明する。このエントリを読むことで、関数をキャッシュ可能にする方法、numpyのarrayをメモリーマップを使って読み込む方法、参照を使ってデータにアクセスする方法がわかる。

Continue reading

自然言語処理において、ニューラルネットワークは文や単語を実数値の密ベクトル表現に変換し、 得られた表現に基づいて目的のタスクを解くというアプローチが多い。 自然言語処理のさまざまなタスクで高い精度を上げている一方で、 テキスト検索などの高速な処理速度を要求されるような場面では密ベクトルを処理するのは 速度が遅いなどの実用的な課題がある。 自然言語処理に関する国際会議ACL 2019で発表された論文 “Learning Compressed Sentence Representations for On-Device Text Processing” (pdf) が、類似文検索タスクにおいて、検索精度をほぼ落とさずに、高速な検索がおこなえるように、文の表現を実数値ではなく、 二値ベクトルで表現する方法を提案した。 本記事ではこの論文でどういった技術が提案されているのかをまとめる。

Continue reading

概要 この一週間休暇を取っていて、多少の暇な時間があったので前から気になっていたKaggleに手を付けてみた。 今回はチュートリアル的に公開されているtitanic号の生存予測タスクに参加した。 他の参加者がブログで公開されている素性を参考に素性を設計した。 予測モデルには以前C++で実装した平均化パーセプトロンを用いた。 Scoreが0.79426 (2017/7/29 16:00時点で1428位/7247位) となった。 Kaggleを続けると、機械学習に関するエンジニア能力が高まりそうで良い。 モデル 生存予測モデルおよび年齢予測モデルには以前C++で実装した平均化パーセプトロンを用いた。 平均化パーセプトロンを採用した積極的な理由があるわけではないのだが、今回はOSSに頼らずに、自分で実装した学習器を使いたかったので、消去法的に採用された。 実践的には広く知られたOSSのほうが、優秀なアルゴリズムが実装されていると思うし、バグの可能性も少ないと思うので、今回のようなアプローチはあまり得策ではないと思う。 おそらくランダムフォレストやSVMなどのモデルを利用する参加者が多い中で、パーセプトロンを利用した数少ない人間になるだろう。 後述するが、本タスクで扱うデータには欠損値が存在する。 そこで、欠損値を予測するためのモデルを別途作成し、値を補完するためのモデルを作成した (これもやはり、平均化パーセプトロン) 。 生存予測モデルへの入力 (素性) を予測するモデルを作成しているので、全体構成としてはいわゆるstackingになっている。 素性 メタデータ分析的に他の方がブログで公開されている素性を参考に設計している。 1-of-k表現 性別 年齢 (0~9, 10~19, 20~29, 30~39, 40~49, 50~というカテゴリに修正している) チケット番号 キャビン 乗車地 チケットのクラス 親の人数 兄弟の人数 肩書 (名前から抽出した次の情報: Mr., Ms., Miss., Master.) 運賃 (値の正規化はしていない) 組み合わせ素性 1.1および{1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8} 1.6および{1.4, 1.5, 1.7, 1.8} (1.2) このタスクで扱うデータでは、欠損値が存在する。例えば年齢は、生存者の予測に有効に働きそう (幼い子どもは優先的に救助されうる) なのだが、欠損値が少なからず存在する。 そこで、年齢が不明な事例に関しては、年齢を予測するためのモデルを事前に作成しておき、そのモデルによって年齢を予測し、補完した。 年齢予測モデルで利用した素性は1.

Continue reading

このゴールデンウィークはまとまった休日を取ることができた。 そこでこの休日 (の自分の自由時間) 中に自然言語処理界隈で有名な何かの実装に取り組んで、開発スキルの経験値をあげようと思いいたり、 今まで何度も実装してみようと思って挫折してきたダブル配列を実装することを課題にしてみた。 ダブル配列はTRIEを実装するためのデータ構造の一つとして有名であり、形態素解析器のMeCabなどで用いられている。 入力がキーの集合に含まれるかどうかを調べる時間は、保存したキーの集合のサイズではなく、入力の長さに依存する。 そのため、高速にキーを検索することができる。 開発成果はここにアップロードした。 基本的にはダブル配列法によるトライ検索の実現法を素直に実装している。 休日中に実装できたの機能は以下の通りで、Key-Value Storeとしてなら利用することが可能な実装になっている (共通接頭辞検索などの機能は現在はない): ダブル配列の動的な構築 キーの存在の確認 キーに対する値の取得 キーの削除 ダブル配列の保存・読み込み 動的な構築の高速化のための工夫は他の論文で提案されているらしいが、その実装は間に合わなかった。 またマルチバイト文字の対応はできていないため、日本語処理にはまだ使えない。 (まだ時間があったのでマルチバイトにも対応した。このあたりの文字の対応にはStatic Double Array Trie (DASTrie)を眺めて勉強させていただいた。 2017/05/07 17:43追記) 実装をするにあたり、他に参照した情報源を以下に挙げる: 日本語入力を支える技術 ~変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus) | 徳永 拓之 |本 | 通販 | Amazon ダブル配列の実装方法 Double Array 実装してみた - Mi manca qualche giovedi? 最近のDoubleArrayの性能 - 射撃しつつ前転 いままで実装しようと持って挫折してきたものが時間をかければ最低限作れるようになったという意味で進捗を感じた。 この休日では間に合わず、今後試してみたいと思っているのは以下の通り: マルチバイト文字の対応 (対応した 2017/05/07 17:43追記) (構築、検索のベンチマーク 2017/05/07 17:43追記) 分類器のオレオレ実装と組み合わせてメモリに載らない大きさの素性サイズのデータで文書分類の実験をしてみる

Continue reading

SWIGを使ってPythonラッパーを生成する このエントリではSWIGを使ったPythonラッパーの生成をautomakeでおこなう方法を紹介する。 例えば自然言語処理でよく使われているMeCabやCRFsuiteなどのC++実装にはPythonラッパーが付属していることがある。C++実装を呼び出せるPythonラッパーがあれば、計算量が多くなりやすい機械学習部分だけC++で実装して、他の処理部分はPythonで手軽に書いて運用する、であるとかC++には不慣れであってもPythonなら使ったことがある、というユーザにも利用してもらう、といったことができるようになる。C++ではSWIGを用いて他の言語へのラッパーを生成することができ、MeCabやCRFsuiteなども、SWIGを使ってPythonラッパーを生成している。 またSWIGによるラッパーの生成の手続きは設定が面倒であったりするため、MeCabやCRFsuiteがおこなっているような、automakeで出来るだけ簡略化する作業も調べてまとめる。 (このエントリはSWIG、C++、automakeの経験が浅い著者が情報をまとめたものであり、誤りを含む可能性があるのでご注意ください。) 利用するツールおよび環境 このエントリでは以下のツールを利用する: SWIG (3.0.8) gcc-c++ (4.4.7) autoconf (2.63) automake (1.11.1) libtool (2.2.6b) Python (3.5.0) またOSはCentOS release 6.8 (さくらのVPS) を利用する。 概要 C++の実装を作成する SWIGのインターフェースファイルを作成する setup.pyを用意する Makefile.amを作成する インストールする C++の実装を作成する このエントリはC++の実装そのものではなく、C++実装をPythonから使えるようにするための手順に焦点を当てているので、実装はなんでも良いのだけど、ここでは 平均化パーセプトロンの実装を用いる。 SWIGのインターフェースファイルを作成する インターフェースファイルはSWIGへの入力になる。 インターフェースファイル (例: onlineml.swigcxx) を以下のようにする: %module onlineml %include "std_pair.i" %include "std_string.i" %include "std_map.i" %include "std_vector.i" %{ #define SWIG_FILE_WITH_INIT #include <onlineml/learner/learner.hpp> #include <onlineml/learner/perceptron.hpp> #include <onlineml/common/classifier.hpp> #include <onlineml/learner/averaged_perceptron.hpp> %} %template() std::pair<std::string, float>; %template(PairVector) std::vector<std::pair<std::string, float> >; %template(PairVectors) std::vector< std::vector<std::pair<std::string, float> > >; %template(StringVectors) std::vector<std::string>; %include <onlineml/learner/learner.

Continue reading

(Structured Perceptron with Inexact Search, NAACL 2012) を読んだ。 構造化パーセプトロンは構造を持つ出力を予測するパーセプトロンであり、自然言語処理では品詞タグ付けなどに用いられる。出力を予測する際には効率的に出力を探索するために、ビームサーチが用いられることが多いが、一般的な構造化パーセプトロンに対してビームサーチを適用すると、パーセプトロンの収束性が保証されない。 構造化パーセプトロンを効率的に学習する手法として、early updateというヒューリスティクスな手法が提案されている。early updateは出力を予測する途中で正解でないとわかった段階で場合に重みを更新するヒューリスティクスな手法である。しかしながら、early updateはラベル列を最後まで見ずに重みを更新するのにも関わらず、violation fixingという枠組みで収束が保証される。 violation violationは構造化パーセプトロンの収束を考えるために必要な定義である。 violationを定義するために、インスタンス$x$と正解のラベル列$y$と、正解以外のラベル列$z$の組を考える。 モデルによって計算される正解のスコア$\mathbf{w}\cdot\mathbf{\phi(x,y)}$が不正解のスコア$\mathbf{w}\cdot\mathbf{\phi(x,z)}$よりも高い 組をviolationという。 言い換えると、重みベクトル$\mathbf{w}$に対して、$\mathbf{w}\cdot\Delta\mathbf{\phi}(x,y,z)\leq 0$ のとき、$(x,y,z)$はvilolationであるという。ただし、$\Delta \phi(x,y,z)=\phi(x,y)-\phi(x,z)$とする。 構造化パーセプトロン ここでは構造化パーセプトロンの収束がviolationによって決まることを追う。 さらに、近似的な探索ではviolationでなくなる可能性が出てしまい、収束性の保証が無くなることを追う。 概要 構造化パーセプトロンはラベルを出力するために、インスタンスに対してスコアが最大となるパス$z$をありうるラベル列の集合$\mathcal{Y}(x)$の中から探索する: $$ z = \arg \max_{s \in \mathcal{Y}(x)} \mathbf{w} \phi(x,s). $$ $z$は正解を含めて、ありうる候補の中で最大のスコア、つまり$\forall z’ \in \mathcal{Y}(x), \mathbf{w}\phi(x,z’)\leq \mathbf{w}\phi(x,z)$である。 更新時は$z \neq y$であるため、構造化パーセプトロンが重みの更新に利用する$(x,y,z)$はすべてviolationである。 収束性 学習データ中で最大となる正解のスコアと不正解のスコアの差を$R$とする: $$ R=\max_{(x,y,z)\in C}|\Delta \mathbf{\phi}(x,y,z)|, $$ $|\mathbf{u}|=1$であるような重みベクトル$\mathbf{u}$が存在し、$\forall (x,y,z)\in C, \mathbf{u}\cdot \Delta \mathbf{\phi}(x,y,z)\geq \delta$ であるとき、学習データは線形分離可能であるという。$\delta$は次のように定義される: $$ \delta = \max_{\mathbf{u}=1} \min_{(x,y,z)\in C} \mathbf{u} \cdot \Delta \mathbf{\phi}(x,y,z), $$

Continue reading

AdaBoostはKaggleなどのコンペで良い成績を出しているアンサンブル学習手法の一つである。このエントリはまずAdaBoostの概要および、なぜAdaBoostが高い汎化能力を示しやすいのかをまとめる。汎化能力が出やすい理由を調査することで、Large Margin Distribution Machineへと発展していった、という経緯を俯瞰することを目的とする。 具体的にはZhi-Hua Zhou先生のスライド (From AdaBoost to LDM) を眺めて、自分の理解のためにメモとして残したものになっている。 AdaBoost 学習時は、学習データに対して重要度の分布を考慮する。反復的に重要度を使って弱学習器を学習し、T個の学習器を作成する (弱学習器はランダムよりは良い性能であるような分類器)。サンプルに対して現在のラウンドの弱学習器が間違えたサンプルほど重要度が高くなるように分布を更新して、次のラウンドの学習に用いる。まとめると、AdaBoostの学習は次のような流れになる: Initialize: 分布D_0をセットする 以下の処理をT回繰り返す: 1. 分布D_tを用いて弱学習器h_tを学習する 2. h_tの信頼度a_tを計算する 3. 次のラウンドの分布D_{t+1}を計算する 予測時は、T個の弱学習器を信頼度aで重み付けした弱学習器$h_t$の線形結合によってサンプル$x$ ($\mathbf{x} \in \mathcal{R}^d$) のラベル$y$ ($y \in {-1, +1}$) を予測する: $$ y = sign(\sum_{t=1}^{T}(a_t h_t(\mathbf{x}))). $$ なぜAdaBoostは良いのか 実装が簡単な割に高い予測性能である事が多い 亜種が色々提案されている (分類、回帰、ランキングなど色々なタスクに適用できる) 経験誤差がブースティングの反復回数に対して指数的に減少することが理論的に保証される 汎化誤差 汎化誤差は、ブースティングの反復回数に応じて増加することが証明されている (Freund & Schapire, 97) 。つまり、ブースティングの反復回数を増やすと、過学習を起こしやすいということである。 しかしながら、実験的には過学習はあまり起きない。なぜ過学習が起きにくいのか、これは重要な疑問である。 AdaBoostの主な研究 ここでは主に研究のフォーカスが当てられている二つトピックを挙げる: Statistical view Margin theory Statistical view 弱学習器の重み付き足し算$H(x)=\sum a_t h_t(x)$に対してロジスティック関数を考えて、確率$p(f(\mathbf{x})=1|x)= \exp(H(x))/( \exp(H(\mathbf{x})) + \exp(-H(\mathbf{x})))$を推定することを考えると、負の対数尤度を最大化する最適化問題として捉えることが出来る ($f(\mathbf{x}) \in {-1, 1})$)。

Continue reading

Author's picture

Takuya Makino

自然言語処理の研究開発者。自然言語処理に関する研究から製品化に向けた開発までに興味を持っています。

自然言語処理の研究開発に従事

Kanagawa, Japan