Word Mover's Distance(WMD)

Word Mover's Distance


2021/04/27
藤田昭人


僕は一度気が削がれると なかなか元の状態に戻れないヤツなのですが…
とある キッカケ を掴んでブログ執筆を再開することができました。

ここからの数回は Word Mover's Distance (WMD) について取り上げます。

BookBot の紹介をして以来、 Word2VecEarth Mover's Distance と対話機能の説明からドンドン離れて行くので 「迷走している」 と感じている方もいらっしゃるかもしれませんが、 この WMD の説明で「なるほど」と納得してもらえる…つもりです(笑)


WMD って何?

WMDは、類似文書検索(あるいは 概念検索 ともいう)、つまり 「文書検索で任意の文を与えると、 その文と意味的に近い文を検索する」 ためのアルゴリズムなんだそうです。

言い換えれば 「2つの文の意味的な距離を測る」 アルゴリズムなんですが…

  1. 文を単語単位に分解し、
  2. Word2Vec を使って、各々の単語毎に「単語の意味的な距離」を測り、
  3. EMD を使って、単語間の意味的距離を合算する

…のがWMD、つまり直感的には WMD = Word2Vec + EMD と説明すると分かり易いでしょう。

実は、コーパスに書籍を使うBookBotでは、応答する場合に 「質問文と意味的に近い文を書籍の中から探す」 必要があるため、このアルゴリズムに着目しました。


WMDに関する「論文」的な話

WMD は2015年に発表された論文 "From Word Embeddings To Document Distances" が初出なようで、ごく最近登場したアルゴリズムのようです。

この論文を読むには類似文書検索などの 統計的自然言語処理の基礎知識」 が必要で、特に「テキストを行列に変換する」 ベクトル空間モデル単語埋め込み、 単語分散表現など (これ全部同じことを意味する用語のようなんですが) が基礎になっています。

WMDをザッと理解したい場合には 前述の論文の日本語による概要説明が役に立ちます。

yubessy.hatenablog.com

この概要説明でも次の定番のオバマ元大統領に関する例文が登場します。

Sym Sentance
D0 'The President greets the press in Chicago.'
D1 'Obama speaks to the media in Illinois.'
D2 'The band gave a concert in Japan.'


この3つの例文の間の意味的距離の計算方法を図示したのが次の図です。

f:id:Akito_Fujita:20210423195546p:plain

この図を見ると Word2Vecで求めた単語どうしの意味的距離輸送問題の解法で集約して 文の間の意味的距離を計算していることが直感的に理解できます。


WMDをちょっと試してみる

WMD を手軽に試してみるには Python を使うのが一番楽です。
次のブログ記事では Python を対話的に使って WMD を計算する手順を説明しています。

hironsan.hatenablog.com

Python3 を使ってこの手順どおりにWMDを計算してみました。

$ python3
Python 3.9.1 (v3.9.1:1e5d33e9b9, Dec  7 2020, 12:10:52) 
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from gensim.models.keyedvectors import KeyedVectors
from gensim.models.keyedvectors import KeyedVectors
>>> model = KeyedVectors.load_word2vec_format('./GoogleNews-vectors-negative300.bin', binary=True)
model = KeyedVectors.load_word2vec_format('./GoogleNews-vectors-negative300.bin', binary=True)
>>> model.most_similar(positive=['japanese'])
model.most_similar(positive=['japanese'])
[('japan', 0.6607722043991089), ('chinese', 0.6502295732498169), ('Japanese', 0.6149078607559204), ('korean', 0.6051568984985352), ('german', 0.5999272465705872), ('american', 0.5906798243522644), ('asian', 0.5839767456054688), ('san', 0.5834755897521973), ('jap', 0.5764404535293579), ('swedish', 0.5720360279083252)]
>>> sent1 = 'But other sources close to the sale said Vivendi was keeping the door open to further bids and hoped to see bidders interested in individual assets team up.'.split()
sent1 = 'But other sources close to the sale said Vivendi was keeping the door open to further bids and hoped to see bidders interested in individual assets team up.'.split()
>>> sent2 = 'But other sources close to the sale said Vivendi was keeping the door open for further bids in the next day or two.'.split()
sent2 = 'But other sources close to the sale said Vivendi was keeping the door open for further bids in the next day or two.'.split()
>>> distance = model.wmdistance(sent1, sent2)
distance = model.wmdistance(sent1, sent2)
>>> print(distance)
print(distance)
0.8738126733213613
>>> d0 = 'The President greets the press in Chicago.'.split()
d0 = 'The President greets the press in Chicago.'.split()
>>> d1 = 'Obama speaks to the media in Illinois.'.split()
d1 = 'Obama speaks to the media in Illinois.'.split()
>>> d2 = 'The band gave a concert in Japan.'.split()
d2 = 'The band gave a concert in Japan.'.split()
>>> dist01 = model.wmdistance(d0, d1)
dist01 = model.wmdistance(d0, d1)
>>> dist02 = model.wmdistance(d0, d2)
dist02 = model.wmdistance(d0, d2)
>>> print(dist01)
print(dist01)
1.968269276774589
>>> print(dist02)
print(dist02)
2.2929445610887638
>>> quit()
quit()
$ 

ここではブログ記事と同じ手順で、 前述の3つの例文の意味的距離も計算しています。 D0-D1 間の距離が 1.968269276774589 に対し、 D0-D2 間の距離は 2.2929445610887638 となりました。 Word2Vecの学習済みデータが異なるので、 前述の図とは値が異なりますが、 D0-D1 間の距離の方が D0-D2 間の距離よりも近いことがわかります。


まとめ

本稿ではWMDについて大変ザックリと説明しました*1

やはり Python は Gensim などパッケージが充実しているので、 今どきの統計的自然言語処理のちょっとした実験には大変便利な言語です。 日本語による解説記事もたくさんありますしね。

でも、さまざまなパッケージが高度にインテグレートされているので、 アルゴリズムの中身を調べようとすると骨が折れると言うのが僕の印象です。 とにかく覚えなければならないことが多いので、正直ウザい(笑) そもそも "Simple is Beautiful" の世代の僕には、 C言語のような「必要最小限」アプローチがフィットしているようです。

以降の解説では敢えて Python を使わないアプローチで WMD に迫ってみたいと考えてます。

以上

*1:前回 語ったように「週3回更新」が可能か?試してみる気になりました。
10分〜15分で読み切れるように 1回の記事の分量を調整したつもりですが、 いかがだったでしょうか?

10万というマジックナンバー

100,000 as the magic number.


2021/04/20
藤田昭人


約1ヶ月ぶりのブログです。
実は締め切りの3日前にどうにか確定申告しまして、 その後はボーッと過ごしてました。
ブログを再開するにあたり、 マジックナンバーの話を書きたいと思います*1


顔芸ベーシスト、ぴんはげ氏の話

このところの僕のマイブームはベーシスト YouTuber の ぴんはげ 氏でして、ほぼ毎晩、寝る前に彼が制作した映像を見てます。 この方、ベースの腕前はもちろんのこと、 超絶技巧をふんだんに盛り込んだ課題曲を連発する作曲能力、 ルーパーやDTMツール(?)を駆使したカバー曲の演奏で見せるアレンジ能力、 それにハイトーン・ボーカル*2… 音楽的才能の塊のような人なのですが、 音楽的高いスキルと独特の顔芸とのギャップ感が人気の秘密なんでしょうねぇ。 やはり一芸で YouTube でブレークするには プロを凌駕する圧倒的なスキルが必要なんでしょうねぇ。

…なもんで、連日ぴんはげ氏の映像アーカイブを漁っているのですが、
いつもとはテイストの違う次の映像を見つけました。

www.youtube.com

この映像の 4:30 あたりからを観て欲しいのですが、
「本アカウントの登録者数が10万を超えたあたりから状況が変わり始めた」
とぴんはげ氏は仰っています*3


10万というマジックナンバー

情報屋にとってマジックナンバーとは 「理由はよくわかんないけど、 意味があるだろうとなんとなく確信してしまう 魔法の定数」なんですけども、 10万という数字には 幾つか身に覚えがあります。

僕の一番古い記憶では、 かつてパソコン通信が華やかだった頃の Nifty Serve で 「登録者数が10万を超えたあたりから状況が劇的に変化した」 との運営者のコメントを聞いたことがあります。 もっともその時は 「10万とは興行や広告・宣伝の業界人が媒体として注目する人為的な数値」 と理解したのですがね。レコードが10万枚売れるとか、 コンサートツアーで10万人動員とか… 90年代は1日で10万人を集めるコンサートが よく話題になりましたよね。


ソーシャルデータの分析での「10万」

ところが…

その後、この10万という数字には 別の意味がありそうなことに気づく機会がありました。

古くから僕を知っている方は 僕がIIJ時代に「Wikipedia ランキング」なるサービスを 運営していたことを覚えてらっしゃる方もいるかもしれません。 Wikipedia は各ページ毎の1時間単位のページビュー数をデータとして公開しているのですが、 毎時、このデータをソートしてランキングで表示するサービスを運営していたのでした。

その延長でWikipedia日本語版の民放のドラマページのページビュー数と視聴率との相関性を 調べ始めました。運の良いことに今世紀最高視聴率のドラマ『半沢直樹』が放送された直後だったので、 そのページビュー数と視聴率を調べて得た公式を使って、 その他の民放ドラマに適用していったのです*4。 確か、ドラマページの1週間の累積ページビュー数が10万を超えると 視聴率とのシンクロ率が急激に上がる知見を得ました。 が、全てのドラマページの累積ページビュー数が10万を超える訳ではなく… その当時の社長に「で、結局ドラマページのページビュー数から視聴率は予測できるのか?」 と聞かれた時に「うまくいく場合とそうでない場合があります」と答えたら、 「バカヤロー!!」と怒られましたが(笑)

ともあれ…

この経験から 「10万」という数字は 興行や広告・宣伝の業界人の直感だけではない なんらかの意味が内包されているマジックナンバーだ と僕は考えるようになりました。


対話システム開発における「10万」

その後、対話システムでも このマジックナンバーに遭遇しました。

LINEに在籍している頃は 用途が限定されたスマートスピーカーのスキル (スマートスピーカー用アプリ) の開発を手がけていました。 この用途に有効な対話コーパスは存在しなかったので、 昔ながらの ELIZA スタイルの応答生成エンジンを使っていたのですが、 スキルが自然な会話ができるよう 機械学習を使って一般的な対話コーパスを取り込む方法を 模索したことがあります。

対話コーパスとは質問文とそれに対する回答文のペアが たくさん記録された会話録のようなデータなのですが、 同様の研究をしている文献をしらみつぶしに探して観たところ、 どの論文をみても10万組の質問文と回答文のペアを学習すると 対話システムがもっともらしい応答をすることがわかりました。

もっとも、これには反例があります。 以前書いたブログ記事 で紹介しましたが、 チューリング・テストのコンテストであるロブナー賞の2000年の覇者でもある Artificial Linguistic Internet Computer Entity (通称: AliceBot)の開発者である Richard Wallace は AliceBot の開発において、オフィスの同僚に対話をしてもらい、 AliceBot が答えられなかった質問について AliceBot になったつもりで考えた応答文を随時ルールに追加していったそうです。 その知見によれば、概ね4万組の質問文・回答文ペアがルールに登録できれば、 ボットは人間のどんな質問にも答えられるようになると見積もっていたそうです。

この時のざっくりした調査では、 無作為な文例(例えばSNSなどのログデータから質問&応答ペアをピックアップする) では10万件以上、 作為的な文例(質問文に対する回答を人間が考える) では4万件以上の文例が必要と結論づけたのですが、 その時点で手元にある文例は数百のオーダーだったので 機械学習の導入は「もう少し文例が溜まってから…」と棚上げにしました。


ふたたび、ぴんはげ氏の話

このように僕は「10万」にまつわる様々な経験をしてきたことから、 ぴんはげ氏の口から「10万」という数字を聞いた時、 僕は「やっぱりねぇ…」と思ったのでした。

もちろん、この「10万」というマジックナンバージップの法則 などと同様のソーシャルな経験則に基づくルールなので 論理的な根拠を示すのが難しい代物です。 でも、いわゆるビッグデータを扱うときの目安値としては重宝します。

さてさて…冒頭のぴんはげ氏の話に戻ります。

冒頭の引っ越しビデオをよく聞いてると「10万を超えるための戦略」は 「去年(2019年)の12月から『週3本投稿します』と宣言して…」 ってことでした。ぴんはげ氏のどちらかというと陽気なビデオの内容とは 裏腹に過酷な生活を送ってるんだろうなぁ…と想像しているところ。

僕もいわゆる「ブログを書いている人」なので、 「アクセス数が10万を突破して状況が劇的に変化する」 には大変に関心があるのですが、 今の内容でブログ記事をアップするには2週間に1本が精一杯。 週3でアップするとなると月刊連載時に培った執筆スタイルを捨て、 ブログ向けシフトをしなくちゃなぁ…と思い悩んでいるところです。

以上

*1:って言うか、このネタを思いついた時 「これは書いておかなければと…」 と思ったのでした。これがなければ ブログを再開するキッカケを掴めなかったかも。

*2:僕が彼にハマったのは次の映像を見たからです。

www.youtube.com

これ、例の劇場版『鬼滅の刃』の主題曲なんだそうで…
作詞・作曲は Kalafina プロデューサーの梶浦由記で、 元々彼女の楽曲は僕のツボに刺さることが多いのですが、 この映像でのぴんはげアレンジは物凄くて 「ベース1本でこんなことができるのかぁ…」 と衝撃を受けた次第。

実はこの曲をフルコーラスで聞いたのはこの映像が初めてで 「オリジナルよりこっちの方が絶対良い」 と僕は信じて疑いません(笑)

*3:しかし、 楽器メーカーからシグネチャモデルの提供を受けるって、 プロでもなかなかないことなんじゃないかと…

*4:この試みはその時の僕のデータサイエンスの師匠との連名で特許も取得したんですがね。

Earth Mover's Distance(2)lpSolveを使ったC実装

Earth Mover's Distance (2)
EMD with lpSolve


2021/03/11
藤田昭人


だいぶん間が空いてしまいましたが…

実は Earth Mover's Distance の実装を巡って悪戦苦闘してました。 その顛末をダラダラを書き連ねた記事が予想外に長くなってしまったので、 要点のみをピックアップして再構成したものが本稿です。

今日 Earth Mover's Distance ついてはさまざまな実装が出回っていますが、 調べてみたところ Earth Mover's Distance を最初に提案した論文 "A Metric for Distributions with Applications to Image Databases" の著者 Yossi Rubner が作成した(と思われる) Code for the Earth Movers Distance (EMD) に掲載されているC実装がオリジナルのようです。 ですが、何分にも20年以上前の1998年に作成されたコードなので、 現在のCコンパイル環境では正しく動いてくれません。

やむなく、代わりとして使える リファレンス実装のコードを探すところから 本稿の作業を始めました。


Rによる EMD の実装

さまざまな条件でググってみたところ…

前述のオリジナルのC実装にも言及している 次のブログ記事を見つけました。

aidiary.hatenablog.com

この記事では EMD が (前回紹介した) 線形計画法の輸送問題を応用した指標であることを説明したのちに、 前述のオリジナル実装に付属するデモコード example1.c を例題として Rと Python の実装例を紹介しています。

記事によれば EMD は次の公式で表されますが…


{\rm EMD} (P, Q) = \frac{\displaystyle \sum_{i=1}^m \displaystyle \sum_{j=1}^n d_{ij} f_{ij}^*}{\displaystyle \sum_{i=1}^m \displaystyle \sum_{j=1}^n f_{ij}^*}

この式の分母部分の  \displaystyle \sum_{i=1}^m \displaystyle \sum_{j=1}^n f_{ij} が輸送される荷物の重さの総和、 分子部分の  \displaystyle \sum_{i=1}^m \displaystyle \sum_{j=1}^n d_{ij} f_{ij} が輸送問題の解なんだそうです。 つまり、この式は輸送問題を解いた後、 移動させる荷物の総重量で割って 単位重量あたりの作業量を計算していることになります。

f:id:Akito_Fujita:20210309195233p:plain

上記は記事から拝借してきた オリジナル実装の example1 の条件を示した図です。 この条件で輸送問題を解くと、 荷物は次のように移動するとコストは最小となります。

移動元 移動先 荷物量
 P_{1}  Q_{1} 0.4
 P_{2}  Q_{1} 0.1
 P_{2}  Q_{2} 0.2
 P_{3}  Q_{3} 0.2
 P_{4}  Q_{2} 0.1

この場合、移動する荷物量の総和は 1.0 となるので、 輸送問題の解である 160.542763 が EMD の解になります。


Rパッケージの lpSolve

Rでの EMD 実装に使われている輸送問題のソルバー lp.transport は lpSolve パッケージに収録されています。詳細は lpSolve.pdf を見ていただくとして、インターフェースのみを次に抜粋します。

名前 説明
lp lp_solve線形・整数計画法システムへのインターフェース
lp.assign 割当問題を解くために特化した lp_solve へのインタフェース
lp.transport 輸送問題を解くために特化した lp_solve へのインターフェース
make.q8 8クイーン問題のための疎な制約行列の生成
lp.object lpオブジェクトの構造
print.lp lpオブジェクトをプリントするメソッド

線形計画法のソルバーとしては 汎用の lp割当問題 に特化した lp.assign輸送問題 に特化した lp.transport の 3つのインターフェースが定義されています。 いずれのインターフェースも lp.object で パラメータの受け渡しをしていますが、 その内訳を次に示します。

メンバー 説明
direction 入力された最適化の方向
x.count 目的関数の変数数
objective 目的関数の係数のベクトル
const.count 入力された制約の数
constraints 制約|入力されたとおりの制約行列(lp.assignやlp.transportでは返されません)
int.count 整数変数の数
int.vec 整数変数のインデックスのベクトル
objval 最適時の目的関数の値
solution 最適な係数のベクトル
num.bin.solns 返された解の数を数値で表示します
status 数字のインジケータです。0 = 成功, 2 = 実現可能な解決策がない

このパッケージ、 実はオープンソース線形計画法ソルバーCライブラリである lpSolve そのものです。 ですが、このライブラリのAPIはエントリーが多くて少々煩雑なので、 複数のエントリーを集約した3つのRコードを パッケージのインターフェースとして定義されているようです。

ちなみにライブラリAPIをそのままインタフェース化した lpSolveAPI も存在します。詳細は lpSolveAPI.pdf を確認してください。両方のパッケージともCコードは同じです。


線形計画法ソルバーライブラリ lpSolve

Rのパッケージが元はCライブラリだとわかって 「それじゃ直接コールすればいいじゃん」 と考えるのは今どきのプログラマの流儀ではないのかもしれませんが(笑)

ソルバーライブラリを探してみたところ、 なんと sourceforge(懐かしい)で、 今もメンテナンスが続いているようです。 ドキュメントを次に示します。

lpsolve.sourceforge.net

で、ライブリラリのビルドの手順を 書こうかと考えたのですが、 素敵なことに下記の Qiita の記事に 手順が書いてあったので、 こちらを参考にしてください。

qiita.com

この記事は lpSolve を Python に 取り込む方法を紹介していますが、 本家の lpSolve API バインディングを 使用しているようです。 元のブログ記事では Rパッケージを Python から使う事例が 紹介されてたのは 輸送問題のAPIである lp.transport が 使いたかったからですかねぇ。 「それ、むっちゃ効率が悪くないか?」 と思うのは僕が老人だからでしょうかねぇ?


Cライブラリの lpSolve を使って輸送問題を解く

ライブラリもビルドできたところで、 輸送問題を解くCプログラムを物色し始めました。 「わりと一般的だろうなぁ…」と想像して lpSolve を呼び出すCコードのサンプルを ググりまくったのですが、 日本語はもちろんのこと、英語でも見つからない。 「今どきのプログラマはもうCは書かないのかな?」 などと思いつつ、 輸送問題の解説 と先程の図をつきわせて 「lpSolve を使って輸送問題を解く」 勉強をしました。 (大学の情報演習みたいだ)

そもそも lpSolve で輸送問題 (というか最適化問題)を解くためには 目的関数と制約条件を設定する必要があります。 輸送問題の目的関数と制約条件を簡単に説明します。

f:id:Akito_Fujita:20210309195233p:plain

前述の図を再掲します。この図を見ると どうしても分布Pと分布Qの 都合7つのマルに目がいってしまうのですが、 輸送問題で注目するのはマルを繋ぐ都合12本の矢印だったりします。

つまり、輸送前は分布Pには図に示すとおり荷物が積まれており、分布Qには荷物は全くない状態だと考えます。 そして、輸送後は分布Pには荷物は全くなく、分布Qには図に示すとおりに荷物が積まれている状態になります。 では、輸送中は?というと都合12本の矢印に荷物が乗っている、つまり荷物が輸送されている状態です。 この時にコストを最小にするためにはどの矢印に荷物をどれくらい載せるべきか?を考えるのが 前回 紹介した「ヒッチコックの輸送問題」なんだそうです。

ここでコストと呼んでるのは分布内の各所の間の距離が違うからです。 例えばP1ーQ1間の距離とP1ーQ2間の距離は異なりますが、 この距離というのはどんな場合にも一定なので定数として扱えます。 各矢印毎のコストは距離と運ぶ荷物量を掛けた値となり、 輸送全体のコストは全ての矢印毎のコストを足しあわせたものと考えます。 前述の EMD の公式の分子部分はこの計算していますが、 これが輸送問題の「目的関数」でもあり、 輸送全体のコストが最小になるように 各矢印の間での運ぶ荷物量の調整を行います。

次に輸送問題の「制約条件」をですが、 これは分布Pと分布Qの各所が扱える荷物量に着目します。 例えば、P1はQ1、Q2、Q3に荷物を発送できますが、 その3箇所に発送する荷物量の合計は 0.4 以下に制約されます。 同様にP2、P3、P4も保有する荷物量で制約されます。 一方、Q1に着目するとP1、P2、P3、P4から荷物を受け取れますが、 その合計が 0.5 以上でなければなりません。 同様にQ2、Q3も受け取る荷物量の下限が制約されます。 このように輸送問題では分布の構成要素の総数分、 この例題では7つの「制約条件」が設定されます。

以上のように「目的関数」と「制約条件」が決められれば、 あとは lpSolve がこの問題を解いてくれます。 例題にそって条件を設定して lpSolve を呼び出す サンプルプログラム を末尾に掲載します*1。 先程ビルドした lpSolve からライブラリとヘッダーをコピーすれば、 次の手順をコンパイルできます。

$ ls inc
lp_Hash.h   lp_lib.h    lp_mipbb.h  lp_utils.h
lp_SOS.h    lp_matrix.h lp_types.h
$ ls lib
liblpsolve55.a
$ c++ -I./inc -g -Wno-macro-redefined -Wno-format -Wno-c++11-compat-deprecated-writable-strings -c example.cpp
$ c++ -L./lib -llpsolve55 -o example example.o
$ ./example
obj_val: 160.542763
variables:
0.400000
0.000000
0.000000
0.100000
0.200000
0.000000
0.000000
0.000000
0.200000
0.000000
0.100000
0.000000
$ 

ようやく冒頭のブログ記事と同じ EMD の計算値 160.542763 が確認できました。 続く variables として表示されてる12の数値は各矢印毎の輸送する荷物量、 つまり分布Pから分布Qへ荷物を輸送する差配を示しています。

しかし、この解を見てると、なんだか人間の代わりに コストが最小になるように lpSolve が考えてくれたように僕には見えてしまいます。 ある意味では人工知能の正体を覗いている感覚になります。 やはり「人工知能」という言葉やそのイメージは、 こういった数学的な解法を巧みにカモフラージュしてしまう 側面が否めないなぁと感じてしまいます。


ここまでのまとめ

lpSolve は1990年代から存在する歴史あるCライブラリで、 さまざまなプログラミング言語へのバインディングを始め、 機能が充実しています。例えば example.cpp の85行目をコメントアウトしてもらうと、 次のように目的関数と制約条件を書いた lp フォーマットのファイルが生成されます。

/* Objective function */
min: +109.927248669 C1 +97.2830920561 C2 +352.90083593 C3 +211.955183942 C4 +195.971936766 C5 +348.09481467 C6
 +244.180261283 C7 +115.429632244 C8 +254.909787964 C9 +141.435497666 C10 +52 C11 +334.752147118 C12;

/* Constraints */
+C1 +C2 +C3 <= 0.4;
+C4 +C5 +C6 <= 0.3;
+C7 +C8 +C9 <= 0.2;
+C10 +C11 +C12 <= 0.1;
+C1 +C4 +C7 +C10 >= 0.5;
+C2 +C5 +C8 +C11 >= 0.3;
+C3 +C6 +C9 +C12 >= 0.2;

このファイルはライブラリに付属する lp_solve コマンドの入力として使えます。 なので JavaScript と接続するには、 この lp フォーマットのファイルを生成して、 子プロセスで lp_solve コマンドを呼び出す方法が 最もお手軽かな?などと考えています。

ともあれ…

Rによる EMD 実装をなぞることにより Earth Mover's Distance は「輸送問題の解を正規化した指標」である ことがわかったことは収穫でした。 もっとも、今どき「輸送問題」をCで解こうとするとある穴全部にハマる… まぁ僕個人の良い勉強になったということにしておきましょう。

しかし、今どきのプログラミング言語のトレンドである 過去に実装されたコードをブラックボックスのまま取り込む風潮には、 正直「これで良いのか?」などと考えていたら、 次の書籍があと数日で出版されることを知りました。

www.hanmoto.com

僕の心配は杞憂で、この3週間は「くたびれ儲け」だった というオチが付いたところで本稿を一旦締めます。

以上

付録: example.cpp

#include <stdio.h>
#include <stdlib.h>
#include "lp_lib.h"

double f1[4][3] = { { 100,  40,  22},
            { 211,  20,   2},
            {  32, 190, 150},
            {   2, 100, 100} };
double f2[3][3] = { {   0,   0,   0},
            {  50, 100,  80},
            { 255, 255, 255} };
double w1[4] = { 0.4, 0.3, 0.2, 0.1 };
double w2[3] = { 0.5, 0.3, 0.2 };

#include <math.h>

double dist(double *F1, double *F2)
{
  double dx = F1[0] - F2[0];
  double dy = F1[1] - F2[1];
  double dz = F1[2] - F2[2];
  return(sqrt(dx*dx + dy*dy + dz*dz));
}

double a[13];

double b[13] = { 0,  //  <= 0.4
         1,  1,  1,
         0,  0,  0,
         0,  0,  0,
         0,  0,  0 };
double c[13] = { 0,  //  <= 0.3
         0,  0,  0,
         1,  1,  1,
         0,  0,  0,
         0,  0,  0 };
double d[13] = { 0,  //  <= 0.2
         0,  0,  0,
         0,  0,  0,
         1,  1,  1,
         0,  0,  0 };
double e[13] = { 0,  //  <= 0.1
         0,  0,  0,
         0,  0,  0,
         0,  0,  0,
         1,  1,  1 };


double f[13] = { 0,  //  <= 0.5
         1,  0,  0,
         1,  0,  0,
         1,  0,  0,
         1,  0,  0 };
double g[13] = { 0,  //  <= 0.3
         0,  1,  0,
         0,  1,  0,
         0,  1,  0,
         0,  1,  0 };
double h[13] = { 0,  //  <= 0.2
         0,  0,  1,
         0,  0,  1,
         0,  0,  1,
         0,  0,  1 };

void
init()
{
  a[0] = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 3; j++) {
      int n = i*3 + j + 1;
      a[n] = dist(f1[i], f2[j]);
    }
  }
}

int
main()
{
  init();

  lprec *lp;
  int ret;

  lp = make_lp(0, 12);
  if (lp == NULL) exit(1);

  ret = set_obj_fn(lp, a);
  if (ret == 0) exit(1);

  add_constraint(lp, b, LE, 0.4);
  add_constraint(lp, c, LE, 0.3);
  add_constraint(lp, d, LE, 0.2);
  add_constraint(lp, e, LE, 0.1);
  add_constraint(lp, f, GE, 0.5);
  add_constraint(lp, g, GE, 0.3);
  add_constraint(lp, h, GE, 0.2);

  //write_lp(lp, "example.lp");

  set_verbose(lp, 1); // CRITICAL; NORMAL = 4; FULL = 6;
  ret = solve(lp);
  if (ret != 0) {
    printf("status: %d\n", ret);
    print_lp(lp);
    exit(1);
  }

  double obj_val = get_objective(lp);
  printf("obj_val: %f\n", obj_val);

  double var[100];
  get_variables(lp, var);
  printf("variables:\n");
  for (int i = 0; i < 12; i++) {
    printf("%f\n", var[i]);
  }

  delete_lp(lp);
  exit(0);
}

*1:.cpp となってますが、 これはコードの途中で変数宣言をしたかったからだけで、 頭から最後までCで記述しています。

Earth Mover's Distance(1)古くて新しいアルゴリズム

Earth Mover's Distance (1)
Old but New Algorithms


2021/02/08
藤田昭人


本稿では Earth Mover's Distance というアルゴリズムを紹介します。 このアルゴリズムWikipedia 日本語版にはページがないので英語版から引用しますと…

In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region D. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted as two different ways of piling up a certain amount of dirt over the region D, the EMD is the minimum cost of turning one pile into the other; where the cost is assumed to be amount of dirt moved times the distance by which it is moved.

統計学では、Earth mover's distance (EMD)は、領域D上の2つの確率分布間の距離の尺度である。 数学では、これはワッサーシュタイン計量法として知られている。 直感的に説明すると、分布が領域D上にある量の土を積み上げる2つの異なる方法であると解釈される場合、 EMDは、一方の土をもう一方の土に変えるための最小コストであり、 コストは土の移動量に移動距離をかけたものと仮定される。

確かに "Informally, " とは書いてありますが、数学がダメダメな僕の直感にはちっとも響かない。 こういう時は "History" の項目に目を移すのが僕の常套手段です。


「モンジュの問題」

元々は「1781年に ガスパール・モンジュGaspard Monge) が(数学の)輸送理論の文脈で初めて導入した」とのこと。 そこで「ガスパール・モンジュ」「 輸送理論」でググってみると 「モンジュの最適輸送問題をめぐる話題について」 というスライドがひっかかりました。そこから「モンジュの最適輸送問題」で調べまくったところ次の記事に行き当たりました。

fukuoka-u.repo.nii.ac.jp

この記事は福岡大学の桑江先生がお書きになった「研究雑談」なのですが、 何が素敵かというと「数学者が書いた文章なのに数式が全く出てこない」ってところです。

本項では、記事の中ほどにある「モンジュの問題」の説明を杖に以降の話を進めていきます。


元々は「砂山を移動させる」問題だった

桑江先生の説明では 「モンジュはラプラスフーリエと並んで ナポレオンに仕えた数学者の一人であり、 真面目で正義感の強い人物でしたが、 それが災いしてか、 ナポレオンに最後まで信奉したために 最後には悲惨な末路を迎えた逸話が残っています」 とのことなんですが、Wikipedia でのモンジュの経歴をみると数学に秀でた軍人だったように見えます。

ja.wikipedia.org

そのように理解すると、 当時ヨーロッパで最強の陸軍だった ナポレオンの軍団の上級将校だったとの想像から、 問題1「ある砂山をそれと同じ体積の穴に移したい。 砂粒の移動には移動距離に依存したコストがかかる時、最適な移動のさせ方は何か?」 という問いも非常にイメージしやすくなります。 陣地を構築するために大量の砂を 輸送する必要があったとか、 騎馬を進めるために行く手にある 大量の穴ぼこを全部埋める必要があるとか… と状況は腑に落ちます。

桑江先生によれば、 この問題「密に詰まった無限の各砂山から 密に詰まった無限の各穴に総コストが最小となるような 1対1上への写像を決める問題」と理解できるそうで 「たいへんな難問」なんだそうです。 この説明、僕にはピンと来ないのですが、 それでも、山と積み上っている砂粒を 一粒ずつ行き先を決める関数を書いてコンピュータで 実行するとしても、いつ計算が終わるかわからない 無謀なプログラムが出来上がることぐらいは 想像が付きます。

ともあれ…

この問題が今から200年以上前の ナポレオンの時代に提示されていたことに、 まずはビックリっと言ったところでしょう。


問題を「荷物の移動」に変更すると…

そこで、写像の問題(らしい)「モンジュの問題」を 解くために、問題の方を置き換えるそうです。 問題2「n 個の工場と n 個の店舗があり、 各工場から各店舗にそれそれ一個の製品のみを移動させ距離に応じてコストがかかるとき、 総コストを最小にする移動のさせ方はなにか?」

これで「工場の散らばり(確率分布)と 店舗の散らばり(確率分布)が与えられているときに 移動の総コストが最小となるような 工場と店舗の配置の結合分布を求めよ」と 置き換えられたそうで、 確かに工場や店舗に収まっている荷物は 砂粒よりは(物理的に)ずっと大きいので 現実的なプログラムが書けそうです。

本稿の冒頭にある「領域D上の2つの確率分布」とは こういうことかぁ…と思った次第。 つまり Earth mover's distance (EMD) とは 「モンジュ・カントロヴィッチ問題(MK問題)」 を解くアルゴリズムという訳ですね。 ちなみにカントロヴィッチはこの方です。

ja.wikipedia.org

でもね、この問題2は「ヒッチコック型輸送問題」って言いませんでしたっけ? このヒッチコックって誰?カントロヴィッチとはどういう関係?


ヒッチコック型輸送問題」とは?

普通、ヒッチコックといえば映画監督の アルフレッド・ヒッチコック を思い浮かべる方が多いと思うのですが、 ここで登場するヒッチコックはこの方です。

en.wikipedia.org

どうやらMITの先生でいらっしゃったようですね。 彼自身がモンジュ由来の輸送問題に言及したのは、1941年の論文 "The Distribution of a Product from Several Sources to Numerous Localities(複数の供給元から複数の地域への製品の流通)" です。この論文が問題2が紹介された初めてのケースだったようです。 また「ヒッチコック型輸送問題」は "HITCHCOCK TRANPORTATION PROBLEM" という報告書でも紹介されています。

The transportation problem was first formulated by F. L. Hitchcock in 1941; he also gave a computational procedure, much akin to general simplex method, for solving the problem. Independently, during World War II, T. C. Koopmans arrived at the same problem in connection with his work as a member of the Joint Shipping Board. The Problem is thus frequently referred to as the Hitchcock-Koopmans problem.

輸送問題は1941年に F. L. Hitchcock によって最初に定式化され、問題を解くための一般的なシンプレックス法に近い計算手順を与えた。 それとは独立して、第二次世界大戦中、T. C. Koopmans は英米共同海運委員会のメンバーとしての仕事に関連して、同じ問題に到達した。 このような経緯から、この問題はヒッチコック・クープマンズ問題と呼ばれることが多い。

新たに登場したクープマンズとはこちら方です。

ja.wikipedia.org

ザッと経歴をみてみると… 1940年にオランダからアメリカへ移民した人、 名前から察するにユダヤ系のようなので ナチス・ドイツの迫害を逃れてきたようですね。 オランダでは理論物理学者として 研究をしていたようですが、 移民を契機に統計学に転向し、 その後、経済学者として活躍した人のようです。

しかし、次から次へと新たな人物が登場するのは、 数学に関わるトピックだからでしょうか? ちょっとキリがない気がしてきました。 ここで探索のアプローチを変えて、 最後の報告書に着目します。 というのも、この文書が保管されていたサイトが手がかりになりそうだから。

このサイトはアメリカの国防総省が管轄した過去の委託研究の報告書のアーカイバーです。主にARPA (国防高等研究計画局) の委託研究、例えばインターネットの技術基盤となった ARPANETの開発時の研究報告などが収蔵されているわけなのですが、 ARPAが設立されたのが1958年ですので、 この報告書はそれ以前のものです。

つまり「ヒッチコック型輸送問題」とは 国防総省が関心を持つような研究だったことになります。


3人の接点

そこでカントロヴィッチ、ヒッチコック、 クープマンズの3人に何かしらの接点がないかと探したところ、Wikipedia線形計画法 の英語版 Linear programming のページで次の記述を見つけました。

In 1939 a linear programming formulation of a problem that is equivalent to the general linear programming problem was given by the Soviet mathematician and economist Leonid Kantorovich, who also proposed a method for solving it. It is a way he developed, during World War II, to plan expenditures and returns in order to reduce costs of the army and to increase losses imposed on the enemy. Kantorovich's work was initially neglected in the USSR. About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 Nobel prize in economics. In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method. Hitchcock had died in 1957 and the Nobel prize is not awarded posthumously.

1939年、ソ連の数学者で経済学者のレオニード・カントロヴィッチが 一般的な線形計画問題に相当する問題を線形計画法で定式化し、 彼もその解法を提案した。 それは、第二次世界大戦中に、軍隊のコストを削減し、敵に課せられる損失を増やすために、 支出とリターンを計画するために彼が開発した方法である。 カントロヴィッチの研究は、当初ソ連では軽視されていた。 カントロヴィッチとほぼ同時期に、 オランダ系アメリカ人の経済学者T.C.クープマンスが、古典的な経済問題を線形プログラムとして定式化した。 カントロヴィッチとクープマンスは、後に1975年のノーベル経済学賞を共同受賞した。 1941年には、フランク・ローレン・ヒッチコックもまた、交通問題を線形プログラムとして定式化し、 後のシンプレックス法と非常によく似た解を与えました。 ヒッチコックは1957年に死去しており、ノーベル賞は死後に授与されていない。

どうやらカントロヴィッチ、ヒッチコック、 クープマンズの3人は互いに独立して、 後に線形計画法と呼ばれる研究に 先鞭をつけていたようですね。

線形計画法といえば ジョージ・ダンツィーグGeorge Dantzig) の シンプレックス法 を思い出します。 ダンツィーグがこの技法を発表したのは1947年のことですが、 カントロヴィッチ、ヒッチコック、クープマンズの3人の取り組みは、 概ねその10年近く前の第2次世界大戦が勃発した前後のことだったようです。

つまり、今日オペレーションズ・リサーチ(OR)と呼ばれる研究分野を 切り開いたのはこの3人ということになるわけですね。 なかでも、1939年に「線形計画法」を体系的に語った ”The Mathematical Method of Production Planning and Organization(生産計画と組織の数理的方法)" を発表したカントロヴィチは、 今では「線形計画法」の創始者として 広く認知されてようです。

いや、しかし、 ORがロシア起源だったとは知らなかったなぁ…


オペレーションズ・リサーチの歴史

オペレーションズ・リサーチOperations Research) は「数学的・統計的モデル、 アルゴリズムの利用などによって、 さまざまな計画に際して 最も効率的になるよう決定する科学的技法」 と定義されています。 僕は第2次世界大戦後に アメリカで生まれた学問だと 思い込んでいたのですが、 その歴史 を辿ってみると第2次世界大戦中の 「軍事作戦のための兵站計画の立案」 を起源としていたようです。 そもそも「モンジュの問題」自体も この兵站計画の範疇に収まりますからねぇ。

第2次世界大戦後、 この技法は「線形計画法」という名前を冠し、 オペレーションズ・リサーチの技法のひとつとして 非軍事的な用途へも急速に拡大していった訳です。 でも、そこは何分にも冷戦真っ只中の時代のことですから、 技法の由来や起源については 各者が都合よく解釈した…それが、 数学、統計学、経済学の間で史観が微妙に異なり、 同じ問題に(関わったとされる)さまざまな人物の名前が 付けられることになった理由なんじゃないかと 僕は想像しています。

桑江先生も紹介しておられるように、 カントロヴィチは1975年にノーベル賞を受賞しています。 が、それはクープマンズと共同でノーベル経済学賞の受賞でした。

www.nobelprize.org

その受賞理由は次のとおり…

The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 1975 was awarded jointly to Leonid Vitaliyevich Kantorovich and Tjalling C. Koopmans "for their contributions to the theory of optimum allocation of resources."

1975年のアルフレッド・ノーベルを記念したスヴェリヒス・リクスバンク経済学賞は、 「資源の最適配分理論への貢献に対して」 レオニード・ヴィタリェヴィチ・カントロヴィッチとティヤリング・クープマンズに共同で授与されました。

一般にノーベル賞は「表彰されるまで待たされる」賞であることで有名ですが、 1975年は冷戦にくたびれていた米ソ両陣営が デタント に向かっていた時期でもあり、 両陣営を代表する学者が共同受賞することで米ソ融和をアピールする狙いがあったのかも? それが彼らが35年間も待たされた 理由かもしれません。


「Earth Mover's Distance」という新しい器

ここまで長々と説明して来た 「モンジュ・カントロヴィッチ問題」
ある意味では前世紀に決着済みのはずのこの問題には、 実はその後があります。 そもそも「砂山を運ぶためのコスト」を計算するために 考え出されたはずのこのアルゴリズムですが、 全く別の思いもよらない使い方があったのでした。

その新しい使い方を紹介しているのが論文 "The Earth Mover’s Distance as a Metric for Image Retrieval " (画像検索のための指標としてのEarth Mover’s Distance ) です。2000年に発表されたこの論文では、 なんと類似画像検索での類似度判定にEMDを使うこと提案してます。

そもそも画像検索には「2つの画像がどれくらい似ているかを判定する」アルゴリズムが必要になりますが、 この「画像が似ている」を判定するのは難しいですよね? 画像の形に着目するのか?色に着目するのか? はたまた「画像の一部分だけがそっくり」といった例もあるでしょう。 人間が「似ている」と感じることを判定するという意味ではAI的ですし、 近年では機械学習が大きな成果を上げている研究分野でもあります。

論文の要約は次のとおりです。

We investigate the properties of a metric between two distributions, the Earth Mover’s Distance (EMD), for content-based image retrieval. The EMD is based on the minimal cost that must be paid to transform one distribution into the other, in a precise sense, and was first proposed for certain vision problems by Peleg, Werman, and Rom. For image retrieval, we combine this idea with a representation scheme for distributions that is based on vector quantization. This combination leads to an image comparison framework that often accounts for perceptual similarity better than other previously proposed methods. The EMD is based on a solution to the transportation problem from linear optimization, for which efficient algorithms are available, and also allows naturally for partial matching. It is more robust than histogram matching techniques, in that it can operate on variable-length representations of the distributions that avoid quantization and other binning problems typical of histograms. When used to compare distributions with the same overall mass, the EMD is a true metric. In this paper we focus on applications to color and texture, and we compare the retrieval performance of the EMD with that of other distances.

本研究では、コンテンツベースの画像検索における2つの分布間のメトリックであるEarth Mover's Distance (EMD)の特性を調べる。 EMDは、正確な意味で、一方の分布を他方の分布に変換するために支払わなければならない最小コストに基づいており、 Peleg, Werman, Romによって、ある種の視覚問題に対して最初に提案された。 画像検索のために、我々はこの考えを、ベクトル量子化に基づいた分布の表現スキームと組み合わせる。 この組み合わせにより、以前に提案された他の手法よりも知覚的類似度をよく考慮した画像比較のフレームワークが得られる。 EMDは、効率的なアルゴリズムが利用可能な線形最適化からの輸送問題の解に基づいており、 部分的なマッチングも自然に行うことができる。 EMDはヒストグラムマッチング手法よりもロバストであり, ヒストグラムに典型的な量子化やその他のビニングの問題を回避した分布の可変長表現で動作することができる。 同じ全体の質量を持つ分布を比較するために使用される場合、EMDは真のメトリックである。 この論文では、色とテクスチャへの応用に焦点を当て、EMDの検索性能を他の距離と比較する。

どうやら、この提案は比較する2つの画像の各々から特徴を抽出した後、 画像がどれくらい似ているかを数値として表現するためにEMDを使うようです。 さらに詳しい説明は論文を読んでもらうとして…

ちなみに、この論文では Earth Mover’s Distance という名前の由来も紹介されています。

We give the name of Earth Mover’s Distance (EMD), suggested by Stolfi (1994), to this metric in this new context. The transportation problem is to find the minimal cost that must be paid to transform one distribution into the other. The EMD is based on a solution to the transportation problem for which efficient algorithms are available, and it has many desirable properties for image retrieval, as we will see.

Stolfi (1994)によって提案された Earth Mover's Distance (EMD)という名前を、この新しいコンテキストにおけるこのメトリックに与える。 輸送問題は、ある分布を他の分布に変換するために支払わなければならない最小コストを見つけることである。 EMDは、効率的なアルゴリズムが利用可能な輸送問題の解決策に基づいており、画像検索に多くの望ましい特性を持っている。

「Stolfi (1994)によって提案された」とありますが、参考文献には ”Stolfi*1 , J. 1994. Personal communication. ” とあるので、 コンピュータ・ビジョンの専門家の間での 仲間うちでのトークで登場した呼び名なのでしょうか?

しかし、モンジュの問題を踏まえた洒落た名前ですよねぇ。


とりあえず中締めを…

本稿では、ガスパール・モンジュが提起した「モンジュの問題」から "Earth Mover’s Distance" までを (本職の数学者やコンピュータ・ビジョンの専門家に突っ込まれないよう気をつけて) 紹介して来ました。高校数学も怪しい僕にはこのあたりが限界なのですが、 同じテーマで数学者が書いた書籍も出ているようです。

www.springer.com

それから EMD といえばコンピュータ・ビジョンの専門家にはよく知られているアルゴリズムだそうですが、 画像認識に関わる基礎技術でもあるので機械学習でも頻繁に登場するようです。

とはいえ、これ以上数式は勘弁して欲しい僕としては、 以下のC言語のコードでアプローチしたい思ってます。

users.cs.duke.edu

以上

*1:Stofi とはこの人です。

en.wikipedia.org

アフィン演算 の考案者として有名なんだとか…

Word2Vec(2)distance.js

JavaScript implementation of Word2Vec


2021/01/27
藤田昭人


本稿は 前回 の続編です。

Googleのオリジナル実装を使うと比較的お手軽に Word2Vec が使えることがわかりました。が、 BookBotJavaScript 専用 PaaS である Glitch で動いているので(コーパスの学習は word2vec コマンドを使うとしても)word2vec の ご利益を得るには、 学習済みデータへアクセスする JavaScript のコードが必要になります。

で、最近では JavaScript にも慣れてきたので 「サクッと作れるだろう…」と 当初は甘くみていたのですが、さにあらず。 UNIXプログラミングでは 使い慣れてたはずのストリームの扱いに ハマるハマる。 本稿ではそのドタバタの結果を 紹介したいと思います。


学習済みデータが取り込めない

まずは nodejs の常套句のような次の2行で、前回紹介した 東北大学の日本語 word2vec 学習済みデータ を取り込もうとしたのですが…

const fs = require('fs');
var buf = fs.readFileSync('entity_vector/entity_vector.model.txt', 'utf8');

これを nodejs で実行すると…

$ node a.js
buffer.js:608
    slice: (buf, start, end) => buf.utf8Slice(start, end),
                                    ^

Error: Cannot create a string longer than 0x1fffffe8 characters
    at Object.slice (buffer.js:608:37)
    at Buffer.toString (buffer.js:805:14)
    at Object.readFileSync (fs.js:421:41)
    at Object.<anonymous> (/Users/fujita/xtr/BookBot/WikiEntVec/a.js:2:14)
    at Module._compile (internal/modules/cjs/loader.js:1063:30)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1092:10)
    at Module.load (internal/modules/cjs/loader.js:928:32)
    at Function.Module._load (internal/modules/cjs/loader.js:769:14)
    at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main.js:72:12)
    at internal/main/run_main_module.js:17:47 {
  code: 'ERR_STRING_TOO_LONG'
}
$ 

…ズッコケます。

使ったことのある方はご存知でしょうが、 nodejs では fs.readFileSync の第2引数に文字コードを指定しておくと、 ファイルから取り込んだデータを指定した文字コードの文字列に変換してくれるのです。 その変換途中でどうやらズッコケているようです。

そこで読み込んでいるテキストファイルのサイズを確認すると…

$ ls -l entity_vector/
total 5475416
-rw-r--r--@ 1 fujita  staff   830354941  2 17  2017 entity_vector.model.bin
-rw-r--r--@ 1 fujita  staff  1951880197  2 17  2017 entity_vector.model.txt

…2GB弱の巨大なテキストファイルでした。 (Wikipedia日本語版の全文だがら当然か)

ちなみに nodejs の場合 readFileSync など インメモリに取り込むファイルのサイズの上限は2GBです。 このファイルの場合は2GBを超えてはないので、 文字コードを指定しなければ(readFileSyncを第1引数だけで呼ぶ)エラーは出ませんが、 その後文字コードの変換ができないので「万事休す」ことに変わりはありません。


nodejs でのストリーム操作

大容量ファイルへの対処方法は「ストリームによる処理」が定石と言われてます。 もちろん javascript もストリーム処理をサポートしており「nodejs ストリーム」で ググるとそのための情報をたくさん集められます。 例えば、次のページは Stream API を網羅的に紹介してくれているので便利…

qiita.com

…なんですが、javascript の Stream API は非同期で実行されるハンドラを 引き渡す仕様になっていて、そのハンドラの書き方の解説を見つけるの ひと苦労します。

そこでハンドラを書いてみました。 次のソースは2GB以上のファイルを1行ずつリードしてコンソールに表示する、 UNIXの cat コマンドみたいな javascript コードです。

const fs = require('fs');
const readline = require('readline');

var file = 'entity_vector/entity_vector.model.txt';

const reader = async function(rl) {
  for await (const chunk of rl) {
    console.log(chunk);
  }
}

async function main() {
  const rs = fs.createReadStream(file, 'utf8');
  const rl = readline.createInterface(rs, {});
  await reader(rl);
}

main();

このプログラムでは関数 reader が非同期実行できるハンドラなんですが、 関数 main では reader が全てのストリームを受け取って処理し終えるまで 待ってくれます。javascript の非同期実行といえば 昔からある promise/then を使ったコードをよく見かけますが、 このプログラムでは async/await を使ってます。

それからストリームから1行ずつデータを取り出す readline も使ってます。 関数 reader の for await of ループは UNIX の gets を使ったループと等価で console.log(chunk); で1行ごとコンソールに出力してます。 この部分を任意に書き換えて UNIX の フィルター系コマンドと 等価なコードを書くことができます。


コサイン類似度

さて、オリジナル実装に含まれている distance コマンド。 このコマンドは任意の単語を指定すると、 その単語と意味的に距離が近い単語を距離の近い順にソートして、上位40個表示してくれます。 この「意味的な距離が近い」計算とはコサイン類似度の計算で、 実は「2つの単語ベクトル間の角度」を求めています。 計算結果は1〜−1の範囲の値をとり、 1なら角度ゼロ(完全一致)、 0なら角度は90°(意味的には無関係) −1なら角度は180°(意味的には正反対?) を意味します。

Wikipedia日本語版をチェックしてみたのですが、 「コサイン類似度」というページはない( 「ベクトルのなす角」 というページ転送されます)ので、 代わりに次のページを参考にしてください。

mathtrain.jp

ちなみに、Wikipedia英語版では "Cosine similarity” というページで 「情報検索やテキストマイニングでは2つの文書がその主題に関してどれだけ類似しているかを示す有用な尺度となる」 と紹介されています。

さて、肝心のコサイン類似度の計算方法。 当初は「オリジナル実装のコードを見れば」 と考えていたのですが……… とても読解できない「古き悪しき実装」でした。 やむなく上記のページの公式を見ながら 次のコードを書きました。

function Absolute(m) {
  var ret = 0;
  for (var i = 0; i < m.length; i++) {
    ret += m[i] * m[i];
  }
  return(Math.sqrt(ret));
}

function DotProduct(m1, m2) {
  var ret = 0;
  for (var i = 0; i < m1.length; i++) {
    ret += m1[i] * m2[i];
  }
  return(ret);
}

function CosineSimilarity(dot, nrm1, nrm2) {
  return(dot/(nrm1*nrm2));
}

コサイン類似度は2つのベクトルの 内積ドット積) を各ベクトルの 絶対値 で割ることで求めます。この絶対値は各々のベクトルの長さを表し ノルム と呼ばれることもあります。 ベクトルの絶対値、内積、コサイン類似度に対応する AbsoluteDotProductCosineSimilarity を定義しました。


JavaScript 版 distance

以上のコードを組み合わせてJavaScript版 distance.js を作成しました。
ソースコードは末尾に添付しておきます。

オリジナル実装との違いは 次のようにターゲットとなる単語を引数で指定するところです。

$ ./distance.js entity_vector/entity_vector.model.txt '[アラン・チューリング]'

Word: [アラン・チューリング]
1015474 times
                                                Word       Cosine distance
--------------------------------------------------------------------------
[ジョン・フォン・ノイマン]                                      0.8238200737420581
[クロード・シャノン]                                          0.7706864375586782
[ジョン・マッカーシー]                                        0.7634118658850984
チューリング                                               0.7550014937957042
[クルト・ゲーデル]                                          0.7505430963870695
[ハーバート・サイモン]                                       0.7503034618503429
[ダフィット・ヒルベルト]                                       0.7381630672368353
[アルベルト・アインシュタイン]                                  0.7370111227611059
[スタニスワフ・ウラム]                                        0.7355724275046345
[ヴォルフガング・パウリ]                                       0.7320032112916035
[エンリコ・フェルミ]                                           0.729639429509676
[マックス・ボルン]                                          0.7238478243360493
[アロンゾ・チャーチ]                                        0.7203194651116861
[ロバート・オッペンハイマー]                                   0.7152767971441714
[ポール・ディラック]                                         0.7129907170231481
[エミー・ネーター]                                          0.7093252080731395
[ヘルマン・ワイル]                                          0.708357522309429
[エルヴィン・シュレーディンガー]                                 0.707707742898606
[ノーバート・ウィーナー]                                       0.7072144624267143
[バートランド・ラッセル]                                       0.7030623602860854
[ロジャー・ペンローズ]                                        0.7027514788704126
[ゴッドフレイ・ハロルド・ハーディ]                                0.7015682037971648
[レフ・ランダウ]                                             0.6995820039570446
アインシュタイン                                            0.6988088557431229
[アンドレ・ヴェイユ]                                         0.6978330851832386
[ヴェルナー・ハイゼンベルク]                                   0.6968193353952211
[ライナス・ポーリング]                                        0.696506621225639
数学者                                                   0.6874893585915669
[マービン・ミンスキー]                                        0.6872785430574049
[フリーマン・ダイソン]                                        0.6863152690167025
[アンリ・ポアンカレ]                                           0.6851716370245848
[ユージン・ウィグナー]                                        0.6812997448505773
[アレン・ニューウェル]                                        0.6774566693465804
[ハンス・ベーテ]                                             0.6767724362750837
[アルバート・アインシュタイン]                                    0.6750565951905274
[フリッツ・ロンドン]                                           0.6739032952575766
[リチャード・P・ファインマン]                                      0.6737536291870052
[ニールス・ボーア]                                          0.6737340516366506
[朝永振一郎]                                               0.6729520531327631
[ゴットロープ・フレーゲ]                                         0.6717680358048904
$ 

コンソール表示を見る限り オリジナル実装と遜色ない結果がでるのですが… とにかく遅い。これは教育済みデータを (ターゲットとなる 単語ベクトルを見つけるために1回、 ターゲットの単語とその他の単語との コサイン類似度を計算するためにもう1回の) 都合2回走査しているためです。


まとめ

JavaScriptスクリプト言語のなかでも高速な部類なんですが、 そのパワーを持ってしてもビッグデータを扱うことが難しいことを実感しました。 これが JavaScript機械学習系のコード実装が少ない理由なのかもしれません。

東北大学の日本語 word2vec 学習済みデータは十分にビッグデータで、 何か工夫をして扱うデータのサイズを削減しないと、 JavaScript本来のスピードで処理できないと言わざる得ません。

新しい技術的課題を見つけちゃったなぁ…

以上

PS 前回と今回のソースコードGithub にアップしました。

github.com



付録1.distance.js

#!/usr/bin/env node

var file = process.argv[2];
var keyword = process.argv[3];

const fs = require('fs');
const readline = require('readline');

function Absolute(m) {
  var ret = 0;
  for (var i = 0; i < m.length; i++) {
    ret += m[i] * m[i];
  }
  return(Math.sqrt(ret));
}

function DotProduct(m1, m2) {
  var ret = 0;
  for (var i = 0; i < m1.length; i++) {
    ret += m1[i] * m2[i];
  }
  return(ret);
}

function CosineSimilarity(dot, nrm1, nrm2) {
  return(dot/(nrm1*nrm2));
}

var n1 = 0;
var a = {};

const reader1 = async function(rs1) {
  for await (const chunk of rs1) {
    var elm = chunk.split(' ');
    if (elm[0] == keyword) {
      a = {};
      a.key = elm[0];
      a.mtx = [];
      for (var i = 1; i < elm.length; i++) {
        a.mtx.push(parseFloat(elm[i]));
      }
      a.nrm = Absolute(a.mtx);
      break;
    }
    n1++;
  }
};

var n2 = 0;
var distance = [];
const reader2 = async function(rs2) {
  for await (const chunk of rs2) {
    var elm = chunk.split(' ');
    if (elm.length > 2 && elm[0] != keyword) {
      var b = {};
      b.key = elm[0];
      b.mtx = [];
      for (var i = 1; i < elm.length; i++) {
        b.mtx.push(parseFloat(elm[i]));
      }
      b.nrm = Absolute(b.mtx);
      dot = DotProduct(a.mtx, b.mtx);
      sim = CosineSimilarity(dot, a.nrm, b.nrm);
      distance.push({ 'key': b.key, 'sim': sim });
    }
    process.stderr.write(n2+" times\r");
    n2++;
  }
};

const N = 40; // number of closest words that will be shown

function Compare(a, b) {
  return(b.sim - a.sim);
}

async function main() {
  const rs1 = fs.createReadStream(file, { encoding: 'utf8' });
  const rl1 = readline.createInterface(rs1, {});
  await reader1(rl1);
  if (!a.key) {
    console.log("Out of dictionary word!");
    return;
  }
  console.log("\nWord: %s", a.key);
  const rs2 = fs.createReadStream(file, { encoding: 'utf8' });
  const rl2 = readline.createInterface(rs2, {});
  await reader2(rl2);
  distance.sort(Compare);
  console.log("\n                                                Word       Cosine distance\n--------------------------------------------------------------------------");
  for (var i = 0; i < N; i++) {
    var pad = '                                                  ';
    var str = (distance[i].key+pad).slice(0, 50);
    console.log("%s\t%f", str, distance[i].sim);
  }
}

main();

Word2Vec(1)オリジナルの実装

Original implementation of Word2Vec


2021/01/20
藤田昭人


BookBotの対話機能には欠かせない word2vecに取り組んでます。

この不思議なアルゴリズムの解説は ブログ等で多数見つけられるのですが、 実装を紹介する記事に関しては Python ライブライブラリの gensim ほぼ一択で困惑してました。 さらに僕が探した範囲では JavaScript の word2vec のパッケージは、 いずれもオリジナルのCプログラムの ラッパーしか見当たりませんでした。

そこでオリジナルの実装を調べてみたのですが…
オリジナルの実装は 案外おじさんにも優しい古き良きプログラムでした。
本稿ではそのあたりを紹介します。


開発者のトマス・ミコロフと彼の論文について

回りくどくならないようにサクッと…

word2vec の開発者のトマス・ミコロフはWikipediaのページで紹介されています。

en.wikipedia.org

冒頭部分を抜粋すると…

Tomáš Mikolov is a Czech computer scientist working in the field of machine learning. He is currently a Research Scientist at Czech Institute of Informatics, Robotics and Cybernetics.

Mikolov has made several contributions to the field of deep learning and natural language processing. He is mostly known as the inventor of the famous Word2vec method of word embedding.

トマス・ミコロフは、機械学習の分野で活躍するチェコのコンピュータ科学者である。 現在、チェコ情報・ロボット・サイバネティクス研究所の研究員を務めています。

ミコロフは、ディープラーニング自然言語処理の分野でいくつかの貢献をしてきました。 彼は、有名な単語埋め込みのWord2Vecの発明者として知られています。

オリジナルの Word2Vec は ミコロフが Google 在籍時(?)に発表されましたが、 現在ではミコロフは Google を離れているようです*1

彼の Word2Vec の論文に関しては 次のような紹介記事があります。

hytae.hatenablog.com

この技術も 単語の埋め込みWord embedding) と呼ばれる「自然言語処理における一連の言語モデリングおよび特徴学習手法」に分類されるそうですが、 ここでいう「埋め込み」とは 数学的な埋め込み のことらしい。 気にしていると先に進めないのでひとまずは棚上げってことで進めます。


オリジナルの実装について

ミコロフが Google から離れたこともあってか、 現在オリジナルのword2vecの実装は Google Code Archive に追いやられています。またミコロフ自身も Githubソースコード を公開しています。

その他、npm にも オリジナルコードを含むパッケージが 多数存在してるので2〜3試してみたのですが、 一番クセが無いのは Googleアーカイブコードでした。 ソースをざっと見てみましたが… 意外にも古き良き (そして悪しき) Cプログラムでした。 macOS Big Sur/Xcode 12.3でコンパイルするための diffを末尾に掲載します。 (make を実行した時に妙なメッセージが出なくなるおまじない程度の修正ですが…)

この word2vecのソースコードには マニュアルが見当たりません。 (man page ぐらい書いてくれよ) が、Googleアーカイブには Word2Vec の実装に関する メモ があり、収録されている コマンドやデモ・スクリプトについて 簡単に説明されています。 オリジナル実装の貴重な情報源です。 翻訳 を用意しましたので参考にしてください。


学習のためのコマンド:word2vec

word2vecのソースコードには 都合5つのコマンドが収録されていますが、 一番重要なのは word2vec コマンドです。 オプションは次のとおり。

$ ./word2vec
ワードベクトル推定ツールキット v 0.1c

オプション: 
トレーニングのためのパラメータ: 
-train <file>
    モデルを訓練するために <file> のテキストデータを使用する
-output <file>
    結果の単語ベクトル/単語クラスタを保存するに <file> を使用する
-size <int>
    単語ベクトルのサイズを設定する。デフォルトは100。
-window <int>
    単語間の最大スキップ長を設定する。デフォルトは100。
-sample <float>
    単語の出現のしきい値を設定する。
    学習データ中に出現頻度の高い単語はランダムにダウンサンプリングされる。
    デフォルトは1e-3, 有効範囲は(0, 1e-5)
-hs <int>
    階層型ソフトマックスを使用する。デフォルトは0(使用しない)
-negative <int>
    ネガティブサンプリング値。
    デフォルトは5、一般的な値は 3 - 10です。(0 = 使用しない)
-threads <int>
    スレッドを使用する(デフォルトは12)
-iter <int>
   トレーニングのイテレーションを増やす。(デフォルトは5)
-min-count <int>
    指定された回数よりも少ない単語を破棄する。(デフォルトは5)
-alpha <float>
    学習率の初期値を設定する。
    デフォルトはスキップグラムの場合は0.025、CBOWの場合は0.05。
-classes <int>
    ワードベクトルではなく、ワードクラスを出力する。
    デフォルトのクラス数は 0 (ベクトルが書き込まれる)
-debug <int>
    デバッグモードを設定する。 
    デフォルトは 2。(トレーニング中の詳細情報を表示)
-binary <int>
    結果として得られるベクトルをバイナリモードで保存する。デフォルトは0(オフ)。
-save-vocab <file>
    ボキャブラリを <file> に保存する。
-read-vocab <file>
    ボキャブラリを <file> から読み込む。
    学習データから構築されない。
-cbow <int>
    連続 bag of words モデルを使用する。
    デフォルトは 1 (0 はskip-gram モデル)。

Examples:
./word2vec -train data.txt -output vec.txt -size 200 -window 5 -sample 1e-4 -negative 5 -hs 0 -binary 0 -cbow 1 -iter 3

$ 

word2vec コマンドは 入力のコーパスを学習して 単語毎のベクトルを生成します*2。 ここで言うコーパスとは普通の文章なのですが、このコマンドは わかち書き されていることを仮定しているので、 日本語文の場合は形態素解析機などを使って わかち書きした上でコマンドの入力とします*3


その他のコマンド

word2phrase コマンドは word2vec コマンドのプリプロセッサです。 単語ベクトルを生成する際に単語よりフレーズとして扱った方が良い場合、 例えば 'san francisco' を表現するためのベクトルは単語2つではなく、 'san_francisco' といった1つフレーズとして扱うために使用されます*4

distanceコマンドは 単語ベクトルの間の意味的距離を図るコマンドです。 下記のように "Enter word or sentence" のプロンプトで単語を入力すると その他の単語ベクトルとのコサイン距離を求め降順(意味的に近い順)に40個表示されます。

$ ./distance vectors.bin
Enter word or sentence (EXIT to break): france

Word: france  Position in vocabulary: 303

                                              Word       Cosine distance
------------------------------------------------------------------------
                                             spain      0.648269
                                             italy      0.621321
                                            french      0.614999
                                           germany      0.577397
                                          provence      0.565016
                                          ・・・
                                          philippe      0.486715
                                          brittany      0.484123
                                           austria      0.481296
                                           etienne      0.481071
                                          baudouin      0.480878
Enter word or sentence (EXIT to break): EXIT
$ 

コサイン類似度は2つのベクトルの角度を表す指標で 1から−1までの値を取ります。 ベクトルの角度がない(単語が一致する)場合は1、 ベクトルの角度が直角の場合は0になります。

word-analogyコマンドは 単語ベクトルの演算により意味的な類数をするコマンドです。 例えば vector(‘paris’) - vector('french’) + vector('berlin’) の演算は 次のような結果になります。

$ ./word-analogy vectors.bin
Enter three words (EXIT to break): paris france berlin

Word: paris  Position in vocabulary: 1055

Word: france  Position in vocabulary: 303

Word: berlin  Position in vocabulary: 1360

                                              Word              Distance
------------------------------------------------------------------------
                                           germany      0.705529
                                         reunified      0.579637
                                               gdr      0.552582
                                            russia      0.491140
                                         germanies      0.487093
                                          ・・・
                                           denmark      0.403809
                                   gleichschaltung      0.403377
                                               kpd      0.401438
                                       mecklenburg      0.399376
                                       sudetenland      0.399369
Enter three words (EXIT to break): EXIT
$ 

このコマンドは word2vec の紹介でよく語られる ベクトル演算による単語の類推をデモなのですが、 元のコーパスが十分に大きくないと期待通りの結果は出てくれないようです。 オリジナル実装に収録されているスクリプトを使うと論文で紹介されている vector(‘king’) - vector('man’) + vector('woman’) の演算結果はvector('queen’)にはなりません(vector('girl’)になります。

compute-accuracyコマンドは 単語ベクトルの品質を測るためのコマンドなんだそうですが、 この単語ベクトルの品質評価は様々な方法が提案されているそうなので、 本稿では割愛します*5

ちなみにオリジナル実装には コーパスの取得を含めたコマンドの実行環境を整えるデモ・スクリプトが付属しています。 各コマンドとスクリプトの対応は次のとおりです。

コマンド スクリプト
distance demo-word.sh, demo-phrases.sh
word-analogy demo-analogy.sh
compute-accuracy demo-word-accuracy.sh, demo-phrase-accuracy.sh
(クラスタリング) demo-classes.sh

ちなみに(クラスタリング)はword2vecコマンドを 単語のクラスタリングに使用しています。詳細はスクリプトメモ の「Word clustering(単語クラスタリング)」の項を参考にしてください。


学習済み日本語 word2vec データ

オリジナル実装に付属するデモスクリプトを使って、 英語文でのデモンストレーションばかりを見ても word2vec の効用は今ひとつピンと来ません。 ここは日本語文でも word2vec を試してみたいところですが、日本語コーパスわかち書き は悩ましいところ。そこで学習済み日本語 word2vec データを活用させてもらいます。

東北大学 乾・岡崎研究室ではWikipedia日本語版の全文を学習した日本語 word2vec データを公開しています。

www.cl.ecei.tohoku.ac.jp

20170201.tar.bz2 (2017年2月1日版, 1.3GB, 解凍後 2.6GB)をダウンロード・解凍してみたところ 以下のとおりバイナリとテキストの2種類のモデルデータが納められてました。

$ ls -l entity_vector/
total 5475416
-rw-r--r--@ 1 fujita  staff   830354941  2 17  2017 entity_vector.model.bin
-rw-r--r--@ 1 fujita  staff  1951880197  2 17  2017 entity_vector.model.txt
$ 

ミコロフの論文でも「学習精度を確保するためには億単位の単語数が必要」と書いてありましたが、 このデータはバイナリ・テキストともにGB単位の非常に大きなデータです。 オリジナル実装でもこのまま利用することができます。

$ ./distance entity_vector/entity_vector.model.bin
Enter word or sentence (EXIT to break): [アラン・チューリング]
・・・
Enter word or sentence (EXIT to break): EXIT
$ 

なお、Wikipediaの各ページのタイトルに関しては '[' と ']' で囲まれ、 空白は '_' に置き換えられていますので、ご注意ください。

大河ドラマ真田丸」を調べる

では word2vec がどんな単語が「類似性あり」と判断するか調べてみましょう。 元データが 20170201 のバックアップですので、 2016年の大河ドラマの「真田丸」に関連するキーワードについて、固有表現 (固有表現抽出を参照) に着目してリストアップしてみました。

まずドラマページ [真田丸_(NHK大河ドラマ)] ではドラマタイトル、 特に他の大河ドラマのタイトルが類似性が高いとされています。 また、大坂城の出城であった[真田丸]は、城郭と認識されたのか [熊本城]、[小谷城]、[姫路城]が類似性が高いとされています。

人物の方では、主役の[真田信繁]、兄の[真田信之]、さらに父の[真田昌幸] いずれも戦国時代の武将の名前がリストアップされていますが、 注意深く見ると[真田信繁]は豊臣方の、[真田信之]は徳川方の武将が多いように見えます。 また[真田昌幸]では織田信長家中の武将…と各々が活躍した時代が反映されているように感じますね。 次に役者の方をみると、 [真田信繁]役の[堺雅人]の場合は[佐藤隆太]と[藤原竜也]といった「基本は2枚目だがコメディもできる俳優」に見えます。 反対に[真田信之]役の[大泉洋]の場合は[ユースケ・サンタマリア]や[山口智充]といった 「基本はコメディだがシリアスもやる俳優」といったところでしょうか? [真田昌幸]役の[草刈正雄]は[京本政樹]、[多岐川裕美]、[田中麗奈]、[勝野洋] 、[阿部寛]と パッと見イメージしにくいのですが、無理矢理こじつけると「モデル上がりの俳優」ってことなのでしょうかね?

キーワードが人物である時に着目するべきことは、人物しかリストアップされないことと、 それから役名の中に俳優の名前が現れない、例えば[真田信繁]のリストに[堺雅人]は現れないことです。 この性質は脚本の[三谷幸喜]のリストを見れば一目瞭然で、 [宮藤官九郎]、[倉本聰]、[橋田壽賀子]、[北川悦吏子]、[ジェームス三木]、 [山田太一_(脚本家)]、[堤幸彦]、[菊田一夫]、[押井守]、[佐々木守]と 歴代の人気脚本家がリストアップされています。

次に真田一族の居城があった[上田市]を調べてみると、 [佐久市]、[伊那市]、[小諸市]、[千曲市]、[東御市]と 長野県下の近隣の市がリストアップされます。 居城の[上田城]で調べてみると、 [鳥取城]、[岐阜城]、[三木城]、[高遠城]、[浜松城]と 戦国史によく登場するお城がリストアップされます。 でも[大坂城]とか[江戸城]が登場しないのは何故なんでしょうか?

[真田丸_(NHK大河ドラマ)] では、 前半の見せ場だった[上田合戦]を調べると合戦のリストになり、 有名な[大坂冬の陣]、[賤ヶ岳の戦い]、[大坂夏の陣]、[山崎の戦い]を抑えて [小豆坂の戦い]、[姉川の戦い]、[月山富田城の戦い]といった地味な合戦が上位に来ています。

最後に分かりづらい年号ですが、 本能寺の変が起きた[1582年]に一番近いのは武田氏が滅亡した[1567年]です。 関ヶ原の戦いが起きた[1600年]に一番近いのは小田原征伐が起きた[1590年]です。 さらに大坂冬の陣が起きた[1614年]と大坂夏の陣が起きた[1615年]は 相互にもっとも類似していると出ています。(ちょっとこじつけ過ぎか?)

もちろん word2vec コマンドは各キーワードが出現するパターンを調べているだけで、 各キーワードが持つ意味を理解している訳ではないですが、 このような「ついついキーワード間の関係の意味づけ」を追いかけてしまうような特性、 これがミコロフの言う「単語ベクトルの面白い性質」ということなのでしょう。

以上


付録1.macOS Big Sur/Xcode 12.3でコンパイルするためのdiff
diff -ru word2vec/trunk/compute-accuracy.c word2vec-mac/compute-accuracy.c
--- word2vec/trunk/compute-accuracy.c 2016-03-18 13:03:48.000000000 +0900
+++ word2vec-mac/compute-accuracy.c   2021-01-11 10:43:11.000000000 +0900
@@ -16,7 +16,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
-#include <malloc.h>
+#include <stdlib.h>
 #include <ctype.h>
 
 const long long max_size = 2000;         // max length of strings
@@ -26,7 +26,7 @@
 int main(int argc, char **argv)
 {
   FILE *f;
-  char st1[max_size], st2[max_size], st3[max_size], st4[max_size], bestw[N][max_size], file_name[max_size], ch;
+  char st1[max_size], st2[max_size], st3[max_size], st4[max_size], bestw[N][max_size], file_name[max_size]; //, ch;
   float dist, len, bestd[N], vec[max_size];
   long long words, size, a, b, c, d, b1, b2, b3, threshold = 0;
   float *M;
diff -ru word2vec/trunk/distance.c word2vec-mac/distance.c
--- word2vec/trunk/distance.c 2016-03-18 13:03:48.000000000 +0900
+++ word2vec-mac/distance.c   2021-01-11 10:41:43.000000000 +0900
@@ -15,7 +15,7 @@
 #include <stdio.h>
 #include <string.h>
 #include <math.h>
-#include <malloc.h>
+#include <stdlib.h>
 
 const long long max_size = 2000;         // max length of strings
 const long long N = 40;                  // number of closest words that will be shown
@@ -28,7 +28,7 @@
   char file_name[max_size], st[100][max_size];
   float dist, len, bestd[N], vec[max_size];
   long long words, size, a, b, c, d, cn, bi[100];
-  char ch;
+  //char ch;
   float *M;
   char *vocab;
   if (argc < 2) {
diff -ru word2vec/trunk/word-analogy.c word2vec-mac/word-analogy.c
--- word2vec/trunk/word-analogy.c 2016-03-18 13:03:48.000000000 +0900
+++ word2vec-mac/word-analogy.c   2021-01-11 10:42:03.000000000 +0900
@@ -15,7 +15,7 @@
 #include <stdio.h>
 #include <string.h>
 #include <math.h>
-#include <malloc.h>
+#include <stdlib.h>
 
 const long long max_size = 2000;         // max length of strings
 const long long N = 40;                  // number of closest words that will be shown
@@ -28,7 +28,7 @@
   char file_name[max_size], st[100][max_size];
   float dist, len, bestd[N], vec[max_size];
   long long words, size, a, b, c, d, cn, bi[100];
-  char ch;
+  //char ch;
   float *M;
   char *vocab;
   if (argc < 2) {


付録2.大河ドラマ「真田丸」関連キーワードのdistance
$ ./distance entity_vector/entity_vector.model.bin
Enter word or sentence (EXIT to break): [真田丸_(NHK大河ドラマ)]

Word: [真田丸_(NHK大河ドラマ)]  Position in vocabulary: 208717

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [八重の桜]      0.850641
                                 [軍師官兵衛]      0.827400
                  [平清盛_(NHK大河ドラマ)]      0.825276
                                       [花燃ゆ]      0.819338
               [風林火山_(NHK大河ドラマ)]      0.791861
                  [天地人_(NHK大河ドラマ)]      0.780095
                                       [龍馬伝]      0.768709
                                    [マッサン]      0.767875
               [功名が辻_(NHK大河ドラマ)]      0.739119
                                 [あさが来た]      0.729785
         [フルスイング_(テレビドラマ)]      0.722142
                                 [花子とアン]      0.720576
                                    [鈴木先生]      0.717524
               [おひさま_(テレビドラマ)]      0.714102
      [カーネーション_(テレビドラマ)]      0.708059
                     [篤姫_(NHK大河ドラマ)]      0.705406
            [動物戦隊ジュウオウジャー]      0.700339
                     [Mother_(テレビドラマ)]      0.697521
                                      [新選組!]      0.696299
        [つばさ_(2009年のテレビドラマ)]     0.694637
                                    [てっぱん]      0.693992
                                 [最高の離婚]      0.686887
                                 [TOUCH/タッチ]      0.683295
[ドラえもん_新・のび太と鉄人兵団_�Jiří     0.682352
                                 [ナカイの窓]      0.681161
                        [NHK連続テレビ小説]      0.679608
        [水野真紀の魔法のレストランR]      0.679500
                              [NHK大河ドラマ]      0.678539
               [逃げるは恥だが役に立つ]      0.677009
     [ドラえもん_のび太の宇宙英雄記]      0.676890
                        [にほんごであそぼ]      0.676332
                              [お台場新大陸]      0.675701
                              [梅ちゃん先生]      0.675567
[花ざかりの君たちへ_(テレビドラマ)][ピルトダウン人]     0.675254
                     [爆報!_THE_フライデー]        0.674606
  [ドラえもん_新・のび太の日本誕生]      0.674550
                      [67回NHK紅白歌合戦]     0.674473
                                   テレビ大阪      0.674378
            [坂の上の雲_(テレビドラマ)]      0.673822
Enter word or sentence (EXIT to break): [真田丸]

Word: [真田丸]  Position in vocabulary: 130833

                                              Word       Cosine distance
------------------------------------------------------------------------
                                            出城      0.740320
                                       [熊本城]      0.728834
                                       [小谷城]      0.724149
                                       [姫路城]      0.714244
                                         二ノ丸      0.714124
                                       [松本城]      0.708700
                                       [彦根城]      0.708108
                           [Category:豊臣秀吉]      0.707795
                                    [岸和田城]      0.706999
                           [福山城_(備後国)]      0.705762
                                       [二の丸]      0.701598
                                            出丸      0.700790
                                    [勝竜寺城]      0.700491
                                       [金沢城]      0.700444
                                       [玉縄城]      0.700341
                                       [滝山城]      0.697077
                                            本丸      0.696883
                                         三の丸      0.694887
                                         平山城      0.691086
                                    [名古屋城]      0.688279
                                       [川越城]      0.685610
                                          [淀城]      0.685132
                                         古戦場      0.685010
                                            山砦      0.683218
                                       [丸根砦]      0.682380
                                       [福岡城]      0.682332
                                       [鷲津砦]      0.681645
                                       [府内城]      0.681402
                                       [茨木城]      0.680548
                                       [仙台城]      0.677954
                           [高松城_(讃岐国)]      0.675755
                                         二の丸      0.675349
                                       [安土城]      0.675332
                                          [忍城]      0.675065
                                         天守閣      0.674914
                                       [岐阜城]      0.673553
                                          [本丸]      0.673221
                                            清洲      0.673103
                                       [掛川城]      0.671609
                                          [水城]      0.671606
Enter word or sentence (EXIT to break): [真田信繁]

Word: [真田信繁]  Position in vocabulary: 53057

                                              Word       Cosine distance
------------------------------------------------------------------------
                                            幸村      0.862280
                                            信繁      0.853500
                                    [黒田孝高]      0.851998
                                    [前田利家]      0.845007
                                    [後藤基次]      0.841422
                                    [大谷吉継]      0.833924
                                 [宇喜多秀家]      0.831085
                                    [真田昌幸]      0.830969
                                    [本多忠勝]      0.830236
                                    [浅井長政]      0.829288
                                    [竹中重治]      0.827986
                                    [丹羽長秀]      0.827290
                                       [堀秀政]      0.824391
                                    [石田三成]      0.824265
                                    [井伊直政]      0.823248
                                    [明智光秀]      0.821230
                                 [佐久間信盛]      0.820919
                                    [馬場信春]      0.820386
                                    [池田恒興]      0.819985
                                    [鳥居元忠]      0.817749
                                    [藤堂高虎]      0.816229
                                    [木村重成]      0.813626
                                    [直江兼続]      0.812626
                                 [小早川秀秋]      0.812217
                                    [長束正家]      0.811567
                                    [浅野長政]      0.810507
                                    [酒井忠次]      0.809801
                                    [細川幽斎]      0.809242
                                    [山県昌景]      0.807876
                              [長宗我部盛親]      0.806687
                                 [佐久間盛政]      0.806065
                                    [立花宗茂]      0.802603
                                    [織田信忠]      0.802597
                                    [黒田長政]      0.802305
                                       [森可成]      0.800703
                                    [織田信孝]      0.799144
                                    [柴田勝家]      0.798669
                                    [立花道雪]      0.798262
                                    [毛利勝永]      0.796287
                                    [水野勝成]      0.795799
Enter word or sentence (EXIT to break): [堺雅人]

Word: [堺雅人]  Position in vocabulary: 168294

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [佐藤隆太]      0.829818
                                    [藤原竜也]      0.823819
                              [佐藤健_(俳優)]      0.817278
                                       [向井理]      0.810610
                                    [萩原聖人]      0.808793
                                       [石黒賢]      0.804831
                                    [山田孝之]      0.803835
                                    [田中麗奈]      0.801961
                                    [市原隼人]      0.799150
                                    [栗山千明]      0.798809
                                 [松嶋菜々子]      0.794591
                                    [中谷美紀]      0.794233
                                 [石原さとみ]      0.790625
                                    [仲里依紗]      0.789875
                                    [本木雅弘]      0.789623
                                    [堀北真希]      0.789125
                                    [岡田将生]      0.786672
                                    [陣内孝則]      0.786410
                                    [唐沢寿明]      0.786037
                                       [山崎努]      0.785783
                                 [石田ゆり子]      0.785428
                                    [岡田准一]      0.784751
                                    [織田裕二]      0.784626
                                    [高橋克典]      0.784127
                                    [杏_(女優)]      0.783930
                                    [前田亜季]      0.783606
                                 [かたせ梨乃]      0.783165
                                    [谷村美月]      0.783153
                                       [橋爪功]      0.782846
                                    [小林稔侍]      0.782647
                                    [北川景子]      0.782442
                                    [溝端淳平]      0.781518
                                 [稲森いずみ]      0.781370
                                 [加藤ローサ]      0.780886
                                    [塚本高史]      0.780642
                                    [上野樹里]      0.780136
                          [中村獅童_(2代目)]     0.779944
                                    [真矢みき]      0.779365
                                    [生瀬勝久]      0.778443
                                    [成海璃子]      0.778381
Enter word or sentence (EXIT to break): [真田信之]

Word: [真田信之]  Position in vocabulary: 71834

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [結城秀康]      0.864722
                                    [細川忠興]      0.854418
                                    [松平忠直]      0.853225
                                    [前田利長]      0.849034
                                    [真田昌幸]      0.846276
                                    [松平信康]      0.843927
                                    [豊臣秀長]      0.839133
                                    [松平忠輝]      0.838586
                                    [浅野長政]      0.838264
                                    [徳川忠長]      0.836924
                                 [小笠原秀政]      0.836570
                                    [本多忠政]      0.836416
                                            忠政      0.835936
                                       [堀秀政]      0.834228
                                    [立花宗茂]      0.831016
                                    [北条氏照]      0.830443
                                    [松平広忠]      0.829907
                                    [黒田長政]      0.829375
                                    [吉川広家]      0.827719
                                    [池田輝政]      0.827295
                                    [前田利家]      0.826828
                                    [京極高次]      0.826813
                                            隆景      0.826811
                                    [羽柴秀勝]      0.823404
                                            輝元      0.822894
                                            信政      0.822387
                                    [織田信孝]      0.821835
                                    [織田信雄]      0.820363
                                            秀康      0.819313
                                    [本多正信]      0.818753
                                            信繁      0.818476
                                    [伊達輝宗]      0.818328
                                            藤孝      0.818125
                                    [毛利隆元]      0.817783
                                    [平岩親吉]      0.817510
                                    [浅野幸長]      0.817215
                                       [堀秀治]      0.817149
                                    [松平忠昌]      0.815690
                                    [黒田職隆]      0.814530
                                    [蒲生氏郷]      0.814355
Enter word or sentence (EXIT to break): [大泉洋]

Word: [大泉洋]  Position in vocabulary: 95697

                                              Word       Cosine distance
------------------------------------------------------------------------
               [ユースケ・サンタマリア]      0.847172
                                    [山口智充]      0.842746
                                 [佐藤江梨子]      0.839287
                                    [西田敏行]      0.828026
                                       [小栗旬]      0.822958
                                       [藤井隆]      0.822931
                                 [長澤まさみ]      0.822114
                                    [伊東四朗]      0.821836
                              [ラサール石井]      0.821569
                                    [内村光良]      0.817735
                                    [高田純次]      0.817491
                                    [広末涼子]      0.816757
                                    [久本雅美]      0.814944
                                       [安田顕]      0.812524
                                    [陣内智則]      0.811957
                                    [中村玉緒]      0.811861
                                    [香取慎吾]      0.811576
                                    [木村拓哉]      0.810266
                                    [板尾創路]      0.809218
                                    [石坂浩二]      0.809071
                                 [バカリズム]      0.806382
                                    [小池栄子]      0.805978
                                    [山田邦子]      0.805532
                                    [武田鉄矢]      0.805505
                                    [江口洋介]      0.805399
                                    [小倉優子]      0.805051
                                    [坂上二郎]      0.804709
                                 [松嶋菜々子]      0.804488
                                       [坂上忍]      0.803884
                                 [片岡鶴太郎]      0.802868
                                       [堺正章]      0.802248
                                    [織田裕二]      0.802003
                                          [優香]      0.801509
                                    [松村邦洋]      0.801336
                                       [関根勤]      0.801172
                                 [劇団ひとり]      0.800607
                                    [陣内孝則]      0.800257
                              [せんだみつお]      0.799715
                                    [舘ひろし]      0.799632
                     [宮川大輔_(タレント)]      0.799621
Enter word or sentence (EXIT to break): [真田昌幸]

Word: [真田昌幸]  Position in vocabulary: 52729

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [浅井長政]      0.889628
                                       [森長可]      0.888692
                                    [柴田勝家]      0.887071
                                    [吉川元春]      0.885952
                                    [北条氏邦]      0.885003
                                    [丹羽長秀]      0.880816
                                    [滝川一益]      0.880605
                  [佐竹義重_(十八代当主)]      0.878321
                                       [堀秀政]      0.877057
                                    [北条氏照]      0.875241
                                 [佐久間信盛]      0.874229
                                 [宇喜多秀家]      0.871974
                                    [立花宗茂]      0.869287
                                    [佐々成政]      0.868931
                                    [織田信孝]      0.868109
                                    [池田恒興]      0.867718
                                    [吉川広家]      0.866312
                                       [森可成]      0.865885
                                    [浅野長政]      0.865563
                                    [朝倉義景]      0.864799
                              [長宗我部盛親]      0.864381
                                    [織田信雄]      0.863931
                                    [今川義元]      0.863850
                                    [立花道雪]      0.863241
                                    [長束正家]      0.862811
                                    [前田利家]      0.862411
                                    [北条氏康]      0.861690
                                    [十河存保]      0.861266
                                    [伊達輝宗]      0.860470
                                    [北条高広]      0.860067
                                 [小早川秀秋]      0.859652
                                    [北条氏直]      0.859366
                                    [里見義堯]      0.858346
                                    [本庄繁長]      0.856125
                                 [小早川隆景]      0.855965
                                    [結城晴朝]      0.855387
                                    [筒井順慶]      0.854689
                                    [山県昌景]      0.854278
                                    [上杉景勝]      0.853994
                                    [北条氏綱]      0.853868
Enter word or sentence (EXIT to break): [草刈正雄]

Word: [草刈正雄]  Position in vocabulary: 194460

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [京本政樹]      0.809349
                                 [多岐川裕美]      0.806034
                                    [田中麗奈]      0.804275
                                       [勝野洋]      0.795097
                                       [阿部寛]      0.792035
                                    [田中邦衛]      0.791783
                                    [渡辺裕之]      0.789512
                                    [高橋克典]      0.786939
                                 [由美かおる]      0.786617
                                    [松坂慶子]      0.786271
                                 [かたせ梨乃]      0.785857
                                 [和久井映見]      0.785291
                                    [渡瀬恒彦]      0.784532
                                       [加藤剛]      0.783957
                                    [川谷拓三]      0.783735
                                    [宇津井健]      0.783284
                                    [大原麗子]      0.782354
                                       [宍戸錠]      0.782185
                                    [唐沢寿明]      0.781887
                                    [佐藤隆太]      0.781781
                                    [北村一輝]      0.781706
                                       [竜雷太]      0.781700
                                       [水谷豊]      0.780734
                                    [内藤剛志]      0.780645
                                          [瑛太]      0.780475
                                    [佐藤浩市]      0.780325
                              [佐藤健_(俳優)]      0.777771
                                    [池内淳子]      0.777584
                                    [菅原文太]      0.777021
                                    [小林稔侍]      0.776970
                                    [沢口靖子]      0.776846
                                    [柳葉敏郎]      0.776495
                                    [津川雅彦]      0.775650
                                    [高嶋政伸]      0.775082
                                    [石立鉄男]      0.774510
                                       [石黒賢]      0.773385
                                    [香川照之]      0.773220
                                       [山崎努]      0.773158
                                 [中条きよし]      0.772763
                                 [三田村邦彦]      0.772160
Enter word or sentence (EXIT to break): [三谷幸喜]

Word: [三谷幸喜]  Position in vocabulary: 62278

                                              Word       Cosine distance
------------------------------------------------------------------------
                                 [宮藤官九郎]      0.847801
                                       [倉本聰]      0.828014
                                 [橋田壽賀子]      0.813948
                                 [北川悦吏子]      0.804359
                           [ジェームス三木]      0.782101
                        [山田太一_(脚本家)]      0.779650
                                       [堤幸彦]      0.774029
                                    [菊田一夫]      0.772732
                                       [押井守]      0.769006
                                    [佐々木守]      0.765393
                                    [井上敏樹]      0.756454
                                       [早坂暁]      0.755188
                                    [岩井俊二]      0.748714
                                       [宮崎駿]      0.744259
                                 [井上ひさし]      0.743560
                                    [鴻上尚史]      0.742345
                                    [上原正三]      0.739719
                                    [向田邦子]      0.738351
                                    [蜷川幸雄]      0.736478
                                    [君塚良一]      0.731993
                                    [伊藤和典]      0.731116
                                    [野島伸司]      0.730984
                                    [大和屋竺]      0.729276
                                    [井筒和幸]      0.727722
                                       [細田守]      0.727141
                                 [石井ふく子]      0.726934
                                    [伊丹十三]      0.726323
                                    [市川森一]      0.725571
                                    [清水邦夫]      0.725172
                                       [橋本忍]      0.721844
                                    [金子修介]      0.720818
                                    [大林宣彦]      0.720543
                                       [花登筺]      0.719697
                                   アニメ監督      0.716220
                                       [北野武]      0.716118
                     [リリー・フランキー]      0.715990
                                    [竹中直人]      0.714659
                                    [樋口真嗣]      0.714394
                                    [久世光彦]      0.712585
                                       [伊上勝]      0.712067
Enter word or sentence (EXIT to break): [上田市]

Word: [上田市]  Position in vocabulary: 21341

                                              Word       Cosine distance
------------------------------------------------------------------------
                                       [佐久市]      0.873024
                                       [伊那市]      0.851494
                                       [小諸市]      0.851373
                                       [千曲市]      0.850226
                                       [東御市]      0.842370
                                       [青木村]      0.840791
                                       [飯田市]      0.837979
                                       [塩尻市]      0.828366
                                       [丸子町]      0.827832
                                       [辰野町]      0.825878
                                    [上伊那郡]      0.824890
                                       [小県郡]      0.823911
                                       [諏訪市]      0.820981
                                       [中野市]      0.818131
                                       [飯山市]      0.816464
                                       [長野市]      0.814474
                                       [岡谷市]      0.814004
                                    [上水内郡]      0.813308
                                       [松本市]      0.813192
                                    [東筑摩郡]      0.811427
                                    [下伊那郡]      0.808146
                                       [大町市]      0.803682
                                       [坂城町]      0.799765
                                       [木曽町]      0.799210
                                       [茅野市]      0.798991
                                    [駒ヶ根市]      0.796395
                                       [須坂市]      0.792879
                                    [安曇野市]      0.789478
                                       [信濃町]      0.789210
                                    [南安曇郡]      0.789018
                                       [高遠町]      0.788462
                                       [長和町]      0.785993
                           [高山村_(長野県)]      0.783720
                                       [木曽郡]      0.783370
                                    [上高井郡]      0.781338
                                       [飯綱町]      0.780839
                                       [真田町]      0.777769
                                    [北佐久郡]      0.771381
                                       [小谷村]      0.771205
                                    [小布施町]      0.770121
Enter word or sentence (EXIT to break): [上田城]

Word: [上田城]  Position in vocabulary: 79257

                                              Word       Cosine distance
------------------------------------------------------------------------
                                       [鳥取城]      0.852216
                                       [岐阜城]      0.849356
                                       [三木城]      0.849105
                                       [高遠城]      0.845153
                                       [浜松城]      0.843289
                                          [忍城]      0.839791
                           [高松城_(備中国)]      0.839502
                                       [岩村城]      0.837147
                                    [真田昌幸]      0.836247
                                    [佐和山城]      0.836211
                                       [大垣城]      0.835653
                                       [二俣城]      0.835134
                                       [伊丹城]      0.831016
                                       [小松城]      0.827549
                                       [大津城]      0.826306
                                       [高槻城]      0.826240
                                       [長篠城]      0.822233
                                    [二本松城]      0.821886
                                       [掛川城]      0.819836
                                       [上月城]      0.819801
                                    [島津家久]      0.817774
                                       [沼田城]      0.814995
                                    [小田原城]      0.813866
                                 [月山富田城]      0.811999
                                    [立花山城]      0.811840
                                    [勝竜寺城]      0.811324
                                       [清洲城]      0.810574
                                    [松井田城]      0.809341
                                       [七尾城]      0.809190
                                    [佐々成政]      0.808459
                                    [滝川一益]      0.808450
                                 [佐久間信盛]      0.805699
                                       [有岡城]      0.804309
                                       [小谷城]      0.803942
                                       [森長可]      0.803854
                                       [飫肥城]      0.803733
                                       [箕輪城]      0.803318
                                       [桑名城]      0.802203
                           [田辺城_(丹後国)]      0.799411
                                    [高天神城]      0.798767
Enter word or sentence (EXIT to break): [上田合戦]

Word: [上田合戦]  Position in vocabulary: 142642

                                              Word       Cosine distance
------------------------------------------------------------------------
                              [小豆坂の戦い]      0.830107
                                 [姉川の戦い]      0.820177
                        [月山富田城の戦い]      0.810359
                                 [大坂冬の陣]      0.808880
                              [賤ヶ岳の戦い]      0.802219
                                 [大坂夏の陣]      0.801875
                                 [山崎の戦い]      0.799450
                                    [大坂の役]      0.796623
                                    [会津戦争]      0.796386
                           [三方ヶ原の戦い]      0.796324
                              [戸次川の戦い]      0.795473
                              [伏見城の戦い]      0.794881
                     [小牧・長久手の戦い]      0.793958
                     [天王寺・岡山の戦い]      0.793225
                                    [大坂の陣]      0.792602
                              [石垣原の戦い]      0.791799
                                   大坂夏の陣      0.790713
                                 [蟹江城合戦]      0.782472
                                    [奥州合戦]      0.782259
                              [教興寺の戦い]      0.780309
                  [野田城・福島城の戦い]      0.779296
                                    [四国攻め]      0.778365
                              [慶長出羽合戦]      0.778106
                                 [厳島の戦い]      0.777675
                              [上月城の戦い]      0.776749
                                    [北越戦争]      0.775847
                                 [長篠の戦い]      0.773696
                        [加治田・兼山合戦]      0.773451
                           [甲州勝沼の戦い]      0.772457
                              [桶狭間の戦い]      0.765290
                              [白河口の戦い]      0.765117
                                 [国府台合戦]      0.764990
                              [道明寺の戦い]      0.764268
                                 [船岡山合戦]      0.762874
                              [田辺城の戦い]      0.762374
                                    [紀州征伐]      0.761690
                                 [耳川の戦い]      0.760473
                                    [会津征伐]      0.760299
                              [三増峠の戦い]      0.760033
                                 [天狗党の乱]      0.759361
Enter word or sentence (EXIT to break): [1582]

Word: [1582]  Position in vocabulary: 13930

                                              Word       Cosine distance
------------------------------------------------------------------------
                                         [1567]     0.871124
                                         [1584]     0.869043
                                         [1581]     0.856171
                                         [1587]     0.855367
                                         [1575]     0.851390
                                         [1578]     0.846633
                                         [1585]     0.844765
                                         [1572]     0.844028
                                         [1541]     0.842195
                                           15820.841818
                                         [1577]     0.840910
                                         [1579]     0.839901
                                         [1560]     0.839451
                                         [1583]     0.838247
                                         [1576]     0.837940
                                         [1551]     0.835917
                                         [1586]     0.834452
                                         [1569]     0.834166
                                         [1574]     0.832817
                                         [1568]     0.831446
                                         [1589]     0.830784
                                         [1562]     0.824858
                                         [1571]     0.823303
                                         [1548]     0.820335
                                         [1561]     0.817914
                                         [1573]     0.816230
                                         [1570]     0.816178
                                         [1564]     0.815748
                                         [1546]     0.814555
                                         [1554]     0.813623
                                         [1593]     0.813225
                                         [1563]     0.812475
                                         [1565]     0.811689
                                         [1591]     0.808009
                                         [1588]     0.804201
                                         [1555]     0.803827
                                         [1566]     0.803808
                                         [1598]     0.802000
                                         [1552]     0.799705
                                         [1549]     0.798940
Enter word or sentence (EXIT to break): [1600]

Word: [1600]  Position in vocabulary: 11381

                                              Word       Cosine distance
------------------------------------------------------------------------
                                         [1590]     0.840695
                                         [1615]     0.822067
                                         [1583]     0.819413
                                         [1584]     0.818799
                                         [1595]     0.813488
                                         [1587]     0.808977
                                         [1602]     0.804080
                                         [1592]     0.801207
                                         [1585]     0.800537
                                         [1599]     0.800520
                                         [1598]     0.800442
                                         [1601]     0.795140
                                         [1588]     0.793869
                                         [1570]     0.792645
                                         [1582]     0.792580
                                         [1586]     0.789530
                                         [1560]     0.787423
                                         [1581]     0.787366
                                         [1596]     0.787313
                                         [1614]     0.787291
                                         [1593]     0.786871
                                         [1562]     0.785282
                                         [1589]     0.784301
                                         [1597]     0.780177
                                         [1575]     0.779594
                                         [1591]     0.779534
                                         [1580]     0.778075
                                         [1577]     0.777516
                                         [1561]     0.774325
                                         [1578]     0.773667
                                         [1594]     0.770959
                                         [1605]     0.770836
                                         [1572]     0.768102
                                         [1608]     0.766482
                                         [1604]     0.766143
                                         [1568]     0.763673
                                         [1540]     0.761703
                                         [1603]     0.759373
                                         [1632]     0.759193
                                         [1573]     0.757969
Enter word or sentence (EXIT to break): [関ケ原町]

Word: [関ケ原町]  Position in vocabulary: 76997

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [南越前町]      0.708150
                                       [大野市]      0.705391
                                       [足柄峠]      0.698684
                                            墨俣      0.695876
                                       [不破郡]      0.693560
                                       [伊那谷]      0.685688
                           [和田峠_(長野県)]      0.678445
                                 [倶利伽羅峠]      0.676838
                                       [垂井町]      0.675981
                                       [小仏峠]      0.670487
                                       [敦賀市]      0.667752
                                    [上野原市]      0.663754
                                          [中濃]      0.662866
                                    [生駒山地]      0.662561
                                       [只見町]      0.661956
                                    [揖斐川町]      0.661821
                                    [長野盆地]      0.660612
                                       [美濃市]      0.660384
                                 [会津美里町]      0.659184
                                    [国道156]     0.657741
                                         中津川      0.656688
                                          [屋島]      0.656632
                                       [塩尻市]      0.656036
                                       [恵那市]      0.655065
                                       [籠坂峠]      0.654692
                                       [天川村]      0.654580
                              [上村_(長野県)]      0.653949
                                    [木ノ芽峠]      0.653118
                                       [親不知]      0.651887
                                       [笠松町]      0.650014
                                    [木曽地域]      0.649544
                                       [本宮市]      0.647530
                                    [諏訪盆地]      0.647047
                                       [禅定道]      0.646896
                                       [笹子峠]      0.646397
                           [大野郡_(福井県)]      0.645612
                                    [丹波山村]      0.644715
                                       [坂井市]      0.643866
                                       [羽咋市]      0.643366
                                       [加茂郡]      0.643256
Enter word or sentence (EXIT to break): [関ヶ原の戦い]

Word: [関ヶ原の戦い]  Position in vocabulary: 8836

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [大坂の陣]      0.881696
                     [小牧・長久手の戦い]      0.851104
                                    [大坂の役]      0.850898
                                 [小田原征伐]      0.841286
                                 [大坂夏の陣]      0.830540
                              [賤ヶ岳の戦い]      0.810479
                              [桶狭間の戦い]      0.809550
                                 [大坂冬の陣]      0.805582
                                         関ヶ原      0.798661
                                 [山崎の戦い]      0.782722
                                    [九州征伐]      0.772222
                                関ヶ原の戦い      0.767118
                                    [承久の乱]      0.761580
                                    [奥州合戦]      0.759930
                              [戸次川の戦い]      0.759800
                           [文禄・慶長の役]      0.759067
                                 [長篠の戦い]      0.758771
                           [三方ヶ原の戦い]      0.756944
                                 [厳島の戦い]      0.756609
                                    [九州平定]      0.754406
                                 [本能寺の変]      0.751754
                                   大坂夏の陣      0.746492
                              [伏見城の戦い]      0.745927
                              [九戸政実の乱]      0.745615
                                    [戊辰戦争]      0.744409
                                    [上田合戦]      0.734638
                              [慶長出羽合戦]      0.733284
                                 [姉川の戦い]      0.732787
                                    [文禄の役]      0.726051
                                            西軍      0.725281
                              [一ノ谷の戦い]      0.725120
                                       [徳川氏]      0.724901
                                    [島原の乱]      0.724819
                                    [上杉景勝]      0.723127
                              [沖田畷の戦い]      0.722916
                        [加治田・兼山合戦]      0.719709
                                    [石山合戦]      0.717034
                                 [観応の擾乱]      0.715840
                                    [四国攻め]      0.715689
                        [鳥羽・伏見の戦い]      0.715559
Enter word or sentence (EXIT to break): [1614]

Word: [1614]  Position in vocabulary: 20257

                                              Word       Cosine distance
------------------------------------------------------------------------
                                         [1615]     0.865162
                                         [1591]     0.860337
                                         [1611]     0.859098
                                         [1613]     0.858774
                                         [1623]     0.858637
                                         [1612]     0.858610
                                         [1610]     0.849760
                                         [1602]     0.848271
                                         [1586]     0.848025
                                         [1588]     0.846918
                                         [1589]     0.844200
                                         [1608]     0.843631
                                         [1609]     0.842249
                                         [1604]     0.840114
                                         [1603]     0.839589
                                         [1597]     0.838903
                                         [1637]     0.838608
                                         [1621]     0.837954
                                         [1672]     0.837648
                                         [1587]     0.835050
                                         [1598]     0.833399
                                         [1634]     0.832883
                                         [1590]     0.832396
                                         [1605]     0.830919
                                         [1601]     0.830424
                                         [1584]     0.829095
                                         [1592]     0.828330
                                         [1622]     0.828188
                                         [1632]     0.828161
                                         [1635]     0.827146
                                         [1585]     0.827070
                                         [1617]     0.826413
                                         [1619]     0.826360
                                         [1639]     0.825553
                                         [1638]     0.824017
                                         [1583]     0.823912
                                         [1606]     0.822882
                                         [1599]     0.820057
                                         [1641]     0.819394
                                         [1643]     0.819274
Enter word or sentence (EXIT to break): [1615]

Word: [1615]  Position in vocabulary: 18770

                                              Word       Cosine distance
------------------------------------------------------------------------
                                         [1614]     0.865162
                                         [1596]     0.864532
                                         [1602]     0.863315
                                         [1592]     0.860134
                                         [1591]     0.855674
                                         [1616]     0.852244
                                         [1597]     0.850820
                                         [1612]     0.848244
                                         [1598]     0.847103
                                         [1601]     0.844938
                                         [1611]     0.842920
                                         [1587]     0.837137
                                         [1593]     0.836945
                                         [1603]     0.836894
                                         [1610]     0.836832
                                         [1588]     0.836775
                                         [1613]     0.836743
                                         [1594]     0.836655
                                         [1589]     0.836058
                                         [1583]     0.835774
                                         [1605]     0.835619
                                         [1599]     0.835035
                                         [1623]     0.833858
                                         [1643]     0.832430
                                         [1638]     0.829741
                                         [1617]     0.827716
                                         [1585]     0.827511
                                         [1586]     0.827284
                                         [1604]     0.825798
                                         [1590]     0.825550
                                         [1595]     0.825356
                                         [1633]     0.824429
                                         [1573]     0.824042
                                         [1624]     0.823928
                                         [1606]     0.822988
                                         [1609]     0.822239
                                         [1600]     0.822067
                                         [1584]     0.820829
                                         [1608]     0.820579
                                         [1619]     0.819566
Enter word or sentence (EXIT to break): [大坂城]

Word: [大坂城]  Position in vocabulary: 17705

                                              Word       Cosine distance
------------------------------------------------------------------------
                                       [伏見城]      0.866872
                                       [江戸城]      0.866639
                                       [駿府城]      0.853587
                                         大坂城      0.849981
                                       [二条城]      0.816748
                                    [小田原城]      0.811317
                                       [岐阜城]      0.807676
                                    [佐和山城]      0.784947
                                       [大垣城]      0.772539
                                       [鳥取城]      0.766673
                                         江戸城      0.763479
                                       [浜松城]      0.763274
                                       [伊丹城]      0.758546
                                    [宇都宮城]      0.758494
                                         西の丸      0.757409
                                       [富山城]      0.757330
                                    [多聞山城]      0.756187
                                       [若松城]      0.750989
                                       [川越城]      0.749303
                                       [三木城]      0.746179
                                       [広島城]      0.743387
                                       [安土城]      0.741307
                                            本丸      0.741182
                                            陣所      0.739956
                                       [岡山城]      0.739198
                                       [高槻城]      0.738477
                                       [水戸城]      0.737631
                                       [山形城]      0.736139
                                    [二本松城]      0.734716
                                       [尼崎城]      0.732571
                                       [古河城]      0.731697
                                 [石山本願寺]      0.731335
                                       [清洲城]      0.731308
                                       [長岡城]      0.731267
                                    [春日山城]      0.731238
                                       [岩槻城]      0.730846
                                         二の丸      0.730584
                                       [岡崎城]      0.730406
                                    [岸和田城]      0.727810
                                       [小諸城]      0.724366
Enter word or sentence (EXIT to break): [大坂の陣]

Word: [大坂の陣]  Position in vocabulary: 20364

                                              Word       Cosine distance
------------------------------------------------------------------------
                                    [大坂の役]      0.929648
                                 [大坂夏の陣]      0.905435
                     [小牧・長久手の戦い]      0.887993
                              [関ヶ原の戦い]      0.881696
                                 [大坂冬の陣]      0.880892
                                 [小田原征伐]      0.842685
                              [賤ヶ岳の戦い]      0.827607
                           [文禄・慶長の役]      0.826194
                                   大坂夏の陣      0.809155
                                 [長篠の戦い]      0.808281
                                    [九州平定]      0.805219
                                    [文禄の役]      0.802838
                                 [姉川の戦い]      0.800240
                           [三方ヶ原の戦い]      0.793948
                                         関ヶ原      0.793667
                                    [上田合戦]      0.792602
                                    [九州征伐]      0.790378
                              [戸次川の戦い]      0.787284
                              [桶狭間の戦い]      0.785158
                                 [山崎の戦い]      0.783573
                              [伏見城の戦い]      0.776076
                                    [奥州合戦]      0.773755
                                    [島原の乱]      0.771204
                              [沖田畷の戦い]      0.769704
                              [一ノ谷の戦い]      0.768712
                                 [厳島の戦い]      0.764277
                        [月山富田城の戦い]      0.763847
                     [天王寺・岡山の戦い]      0.762107
                                    [三木合戦]      0.758249
                        [鳥羽・伏見の戦い]      0.755719
                              [九戸政実の乱]      0.755190
                                    [会津戦争]      0.750164
                                    [石山合戦]      0.749404
                              [慶長出羽合戦]      0.746751
                                    [戊辰戦争]      0.745568
                                    [上杉景勝]      0.745289
                                    [紀州征伐]      0.744768
                                    [四国攻め]      0.744572
                                    [慶長の役]      0.742148
                                    [会津征伐]      0.740837
Enter word or sentence (EXIT to break): [真田丸の戦い]

Word: [真田丸の戦い]  Position in vocabulary: 454193

                                              Word       Cosine distance
------------------------------------------------------------------------
                              [一言坂の戦い]      0.688066
                              [七尾城の戦い]      0.687602
                              [手取川の戦い]      0.675760
                                 [粟津の戦い]      0.672440
                        [野田・福島の戦い]      0.661199
                           [信貴山城の戦い]      0.659862
                              [ドゥナの戦い]      0.655745
                                 [須々万沼城]      0.653602
                              [野良田の戦い]      0.652459
                              [南原城の戦い]      0.652226
                    [天王寺の戦い_(1576年)]     0.650776
                              [岩村城の戦い]      0.650516
                  [喜連川五月女坂の戦い]      0.648556
                                 [稲生の戦い]      0.647997
                     [ラールソートの戦い]      0.646685
                              [末森城の戦い]      0.646324
                           [伊集院頼久の乱]      0.645752
                                    [大崎合戦]      0.645676
                                    [堅田合戦]      0.645293
                                 [赤塚の戦い]      0.645071
                              [村木砦の戦い]      0.643145
                              [布部山の戦い]      0.642102
                           [稲葉山城の戦い]      0.640575
                                 [上京の戦い]      0.640390
                                 [六羽川合戦]      0.639293
                                    [上村合戦]      0.638805
                                    [横田高松]      0.637634
                              [太平寺の戦い]      0.637571
                              [中尾城の戦い]      0.636992
                              [尻垂坂の戦い]      0.635935
                                 [三船山合戦]      0.635824
                                 [蟹江城合戦]      0.634581
                                 [忍城の戦い]      0.633908
                              [立河原の戦い]      0.633376
                        [有田中井手の戦い]      0.633342
                        [八尾・若江の戦い]      0.632827
                              [高屋城の戦い]      0.631499
                  [野田城・福島城の戦い]      0.631484
                              [魚津城の戦い]      0.631203
           [スモレンスクの戦い_(1941年)]     0.629926
Enter word or sentence (EXIT to break):EXIT
$ 

*1:彼の名前でググったところ、Quora で次のような質問を見つけました。

www.quora.com

で、返答を読んでいると、ミコロフと面識のある人から次のようなコメントが出ていました。

I had the chance to talk to him once, and he spoke a bit about Google. One thing he criticized what that Google was too shy to use his models in production. For example Mikolov thought that word embeddings could be used in Google translate to propose other translations. But Google was worried about proposing wrong translation.

私は一度彼と話す機会があり、彼はGoogleについて少し話しました。 彼が批判していたことの一つは、Googleが彼のモデルを本番で使うのを恥ずかしがっていることでした。 例えば、ミコロフはGoogle翻訳で単語のエンベッディングを使えば、他の翻訳を提案できると考えていました。 しかし、Googleは間違った翻訳を提案することを心配していました。

つまり、Word2Vec がアルゴリズムとしてはあまりに単純すぎるし、 このアルゴリズムが「何故そのような(好ましい)結果を出すのか?」 ミコロフ自身にも説明できなかったことを Google は重くみていたようですね。

*2:このベクトル生成には機械学習が使われているそうです。 word2vecではどのような学習が行われているのか解説する記事は多数ありますが、 次の記事が参考文献としてよく登場するように思います。

Word2Vec のニューラルネットワーク学習過程を理解する

word2vecのソースを読んでみた

絵で理解するWord2vecの仕組み

オプションにも登場する「ネガティブサンプリング」と 「階層型ソフトマックス」は機械学習の際の最適化手法なんだそうです。 これも深入りすると二度と再浮上できそうにないので本項では割愛します(笑)

それから機械学習なのに GPGPUなんぞを使わなくとも それなりの時間で計算できるのが word2vec の特徴のひとつなんだそうです。詳細は 「word2vec の各種実装の速度比較」 をご覧ください。

*3:日本語文の場合、 この「わかち書き」によって word2vec の精度が変わってくるそうです。 詳細は 「学習済み日本語word2vecとその評価について」 で解説されています。気になる方はご一読を。

*4:同様のニーズは日本語文でも発生します。

例えば固有表現の事例としてよく掲げられる「福島第一原子力発電所」を形態素解析すると 「[福島][第][一][原子][力][発電][所]」という7つの単語に分割されてしまいます。

これを1つの固有名詞として扱う需要はあると思うのですが、 そのような word2phrase の利用事例は今のところ見つけられていません。 論文「日本語単語ベクトルの構築とその評価」 において…

単語の分割単位の問題は、word2vec とともに公開されている word2phrase というツールを活用する方法や、 分割された単語の品詞に着目して一定のルールで単語を再結合する方法が考えられる。

と言う記述を発見しただけです。他にもっと一般的な解決策があるのかな?

*5:詳細は 「学習済み日本語word2vecとその評価について」 をご覧ください。

メモ:Word2Vec

下記は Google Code にアーカイブされているword2vecの オリジナル実装のドキュメント の全文および翻訳です。 ドキュメントというよりはメモといった性格の文書なんですが、 C言語で実装されたword2vecの基本コマンドと 付属するデモスクリプトについて簡単に解説しています。

僕がみる限り、 プログラム自体は古き良き(そして悪しき)UNIX C プログラムですね。 解説は別記事に書く予定。 しかし、いやぁ、もう、man page を書いてよ、本当に。


Tool for computing continuous distributed representations of words.

単語の連続的な分散表現を計算するためのツール。

Introduction(イントロダクション)

This tool provides an efficient implementation of the continuous bag-of-words and skip-gram architectures for computing vector representations of words. These representations can be subsequently used in many natural language processing applications and for further research.

このツールは、単語のベクトル表現を計算するための連続バッグオブワードおよびスキップグラムアーキテクチャの効率的な実装を提供します。これらの表現は、その後、多くの自然言語処理アプリケーションやさらなる研究に使用することができます。

Quick start(クイックスタート)

Download the code: svn checkout http://word2vec.googlecode.com/svn/trunk/ Run 'make' to compile word2vec tool Run the demo scripts: ./demo-word.sh and ./demo-phrases.sh For questions about the toolkit, see http://groups.google.com/group/word2vec-toolkit

  • コードをダウンロードする
  • 'make' を実行して word2vec ツールをコンパイルする
  • デモ スクリプトを実行する: ./demo-word.sh と ./demo-phrases.sh

ツールキットについての質問は http://groups.google.com/group/word2vec-toolkit を参照してください。

How does it work(どのように動作するのか)

The word2vec tool takes a text corpus as input and produces the word vectors as output. It first constructs a vocabulary from the training text data and then learns vector representation of words. The resulting word vector file can be used as features in many natural language processing and machine learning applications.

word2vecツールはテキストコーパスを入力とし、出力として単語ベクトルを生成します。まず、学習テキストデータから語彙を構築し、単語のベクトル表現を学習します。生成された単語ベクトルファイルは、多くの自然言語処理機械学習アプリケーションで特徴量として使用することができます。

A simple way to investigate the learned representations is to find the closest words for a user-specified word. The distance tool serves that purpose. For example, if you enter 'france', distance will display the most similar words and their distances to 'france', which should look like:

学習された表現を調べる簡単な方法は、ユーザが指定した単語に最も近い単語を見つけることです。distanceツールがその目的を果たします。例えば、'france'と入力すると、distanceは最も類似した単語と'france'までの距離を表示します。

Word Cosine distance

            spain          0.678515
          belgium          0.665923
      netherlands          0.652428
            italy          0.633130
      switzerland          0.622323
       luxembourg          0.610033
         portugal          0.577154
           russia          0.571507
          germany          0.563291
        catalonia          0.534176

There are two main learning algorithms in word2vec : continuous bag-of-words and continuous skip-gram. The switch -cbow allows the user to pick one of these learning algorithms. Both algorithms learn the representation of a word that is useful for prediction of other words in the sentence. These algorithms are described in detail in [1,2].

word2vecには主に2つの学習アルゴリズムがあります:連続的なbag-of-wordsと連続的なskip-gramです。スイッチ -cbow を使うと、これらの学習アルゴリズムのいずれかを選択することができます。どちらのアルゴリズムも、文中の他の単語を予測するのに有用な単語の表現を学習します。これらのアルゴリズムについては、[1,2]で詳しく説明されています。

Interesting properties of the word vectors(言葉のベクトルの面白い性質)

It was recently shown that the word vectors capture many linguistic regularities, for example vector operations vector('Paris') - vector('France') + vector('Italy') results in a vector that is very close to vector('Rome'), and vector('king') - vector('man') + vector('woman') is close to vector('queen') [3, 1]. You can try out a simple demo by running demo-analogy.sh.

例えば、ベクトル操作 vector('Paris') - vector('France') + vector('Italy') の結果は vector('Rome') に非常に近く、 vector('king') - vector('man') + vector('woman') は vector('Queen') に近いことが最近明らかになりました [3, 1]。demo-analogy.shを実行すると簡単なデモを試すことができます。

To observe strong regularities in the word vector space, it is needed to train the models on large data set, with sufficient vector dimensionality as shown in [1]. Using the word2vec tool, it is possible to train models on huge data sets (up to hundreds of billions of words).

単語ベクトル空間の強い規則性を観測するためには,[1]に示すように,十分なベクトル次元を持つ大規模なデータセットでモデルを学習する必要があります。word2vecツールを用いることで,数千億語にも及ぶ膨大なデータセットに対してモデルを学習することが可能となります。

From words to phrases and beyond(言葉からフレーズへ、そしてその先へ)

In certain applications, it is useful to have vector representation of larger pieces of text. For example, it is desirable to have only one vector for representing 'san francisco'. This can be achieved by pre-processing the training data set to form the phrases using the word2phrase tool, as is shown in the example script ./demo-phrases.sh. The example output with the closest tokens to 'san_francisco' looks like:

特定のアプリケーションでは、より大きなテキストの断片をベクトルで表現することが有用です。例えば、'san francisco'を表現するためのベクトルは1つだけであることが望ましいでしょう。これは、例のスクリプト./demo-phrases.shに示されているように、word2phraseツールを使用してフレーズを形成するために学習データセットを前処理することによって達成することができます。'san_francisco'に最も近いトークンを用いた出力例は以下のようになります。

Word Cosine distance 

      los_angeles          0.666175
      golden_gate          0.571522
          oakland          0.557521
       california          0.554623
        san_diego          0.534939
         pasadena          0.519115
          seattle          0.512098
            taiko          0.507570
          houston          0.499762
 chicago_illinois          0.491598

The linearity of the vector operations seems to weakly hold also for the addition of several vectors, so it is possible to add several word or phrase vectors to form representation of short sentences [2].

ベクトル演算の直線性は、複数のベクトルを追加した場合にも弱く保たれるようであり、複数の単語やフレーズのベクトルを追加して短文を表現することが可能です[2]。

How to measure quality of the word vectors(単語ベクトルの品質を測る方法)

Several factors influence the quality of the word vectors: * amount and quality of the training data * size of the vectors * training algorithm

学習データの量と質、ベクトルのサイズ、学習アルゴリズムなど、いくつかの要因が単語ベクトルの品質に影響を与えます。

The quality of the vectors is crucial for any application. However, exploration of different hyper-parameter settings for complex tasks might be too time demanding. Thus, we designed simple test sets that can be used to quickly evaluate the word vector quality.

ベクトルの品質はどのようなアプリケーションにとっても非常に重要です。しかし、複雑なタスクのために異なるハイパーパラメータ設定を探索するのは時間がかかりすぎるかもしれません。そこで、我々は、単語ベクトルの品質を迅速に評価するために使用できる簡単なテストセットを設計しました。

For the word relation test set described in [1], see ./demo-word-accuracy.sh, for the phrase relation test set described in [2], see ./demo-phrase-accuracy.sh. Note that the accuracy depends heavily on the amount of the training data; our best results for both test sets are above 70% accuracy with coverage close to 100%.

[1]で記述された単語関係のテストセットについては、./demo-word-accuracy.shを、[2]で記述されたフレーズ関係のテストセットについては、./demo-phase-accuracy.shを参照してください。精度は学習データの量に大きく依存することに注意してください。両方のテストセットでの最良の結果は、カバレッジが100%に近い70%以上の精度です。

Word clustering(単語クラスタリング

The word vectors can be also used for deriving word classes from huge data sets. This is achieved by performing K-means clustering on top of the word vectors. The script that demonstrates this is ./demo-classes.sh. The output is a vocabulary file with words and their corresponding class IDs, such as:

単語ベクトルは、巨大なデータセットから単語クラスを導出するためにも使用することができます。これは、単語ベクトルの上でK-meansクラスタリングを実行することで達成されます。これを実演するスクリプトは ./demo-classes.sh です。出力されるのは、単語とそれに対応するクラスIDを持つボキャブラリーファイルです。

carnivores 234 
carnivorous 234 
cetaceans 234 
cormorant 234 
coyotes 234 
crocodile 234 
crocodiles 234 
crustaceans 234 
cultivated 234 
danios 234 
. . . 
acceptance 412 
argue 412 
argues 412 
arguing 412 
argument 412 
arguments 412 
belief 412 
believe 412 
challenge 412 
claim 412

Performance(パフォーマンス)

The training speed can be significantly improved by using parallel training on multiple-CPU machine (use the switch '-threads N'). The hyper-parameter choice is crucial for performance (both speed and accuracy), however varies for different applications. The main choices to make are:

学習速度は,複数のCPUで並列学習を行うことで大幅に向上します(スイッチ'-threads N'を使用).ハイパーパラメータの選択は性能(速度と精度の両方)に重要ですが、アプリケーションによって異なります。主な選択は以下の通りです。

  • architecture: skip-gram (slower, better for infrequent words) vs CBOW (fast)
  • the training algorithm: hierarchical softmax (better for infrequent words) vs negative sampling (better for frequent words, better with low dimensional vectors)
  • sub-sampling of frequent words: can improve both accuracy and speed for large data sets (useful values are in range 1e-3 to 1e-5)
  • dimensionality of the word vectors: usually more is better, but not always
  • context (window) size: for skip-gram usually around 10, for CBOW around 5

  • アーキテクチャ: スキップグラム (遅い、頻度の低い単語に適している) vs CBOW (速い)

  • 学習アルゴリズム:階層的ソフトマックス(頻度の低い単語に対してより良い) vs ネガティブサンプリング(頻度の高い単語に対してより良い,低次元ベクトルに対してより良い).
  • 頻出語のサブサンプリング: 大規模データセットの精度と速度を向上させることができます(有用な値は1e-3から1e-5の範囲です)
  • 単語ベクトルの次元性: 通常は多ければ多いほど良いが、必ずしもそうとは限らない
  • コンテキスト (ウィンドウ) サイズ: スキップグラムでは通常約10、CBOWでは約5

Where to obtain the training data(トレーニングデータの入手先)

The quality of the word vectors increases significantly with amount of the training data. For research purposes, you can consider using data sets that are available on-line:

単語ベクトルの品質は、学習データの量によって著しく向上します。研究目的のために、オンラインで利用可能なデータセットの利用を検討することができます。

Pre-trained word and phrase vectors(予め学習された単語とフレーズのベクトル)

We are publishing pre-trained vectors trained on part of Google News dataset (about 100 billion words). The model contains 300-dimensional vectors for 3 million words and phrases. The phrases were obtained using a simple data-driven approach described in [2]. The archive is available here: GoogleNews-vectors-negative300.bin.gz.

Google Newsのデータセット(約1,000億語)の一部で訓練された事前訓練済みのベクトルを公開しています。モデルには300万語の単語とフレーズの300次元ベクトルが含まれています。フレーズは、[2]で説明したシンプルなデータ駆動型のアプローチを用いて取得しました。アーカイブはこちらからご覧いただけます。GoogleNews-vectors-negative300.bin.gz

An example output of ./distance GoogleNews-vectors-negative300.bin:

./distance GoogleNews-vectors-negative300.binの出力例。

Enter word or sentence (EXIT to break): Chinese river

Word Cosine distance 

   Yangtze_River            0.667376
         Yangtze            0.644091
  Qiantang_River            0.632979
Yangtze_tributary           0.623527 
Xiangjiang_River            0.615482 
Huangpu_River               0.604726 
Hanjiang_River              0.598110 
Yangtze_river               0.597621 
Hongze_Lake                 0.594108 
Yangtse                     0.593442 

The above example will average vectors for words 'Chinese' and 'river' and will return the closest neighbors to the resulting vector. More examples that demonstrate results of vector addition are presented in [2]. Note that more precise and disambiguated entity vectors can be found in the following dataset that uses Freebase naming.

上記の例では、単語'Chinese'と単語'river'のベクトルを平均化し、結果として得られたベクトルに最も近い隣人を返す。ベクトル加算の結果を示すより多くの例は、[2]で紹介されています。より正確で曖昧性のない実体ベクトルは、Freebaseネーミングを使用している以下のデータセットにあることに注意してください。

Pre-trained entity vectors with Freebase naming(Freebaseネーミングを用いた事前学習済みのエンティティベクター

We are also offering more than 1.4M pre-trained entity vectors with naming from Freebase. This is especially helpful for projects related to knowledge mining.

また、Freebaseからネーミング付きの事前学習済みエンティティベクターを140万個以上提供しています。特にナレッジマイニング関連のプロジェクトに役立ちます。

Entity vectors trained on 100B words from various news articles: freebase-vectors-skipgram1000.bin.gz Entity vectors trained on 100B words from various news articles, using the deprecated /en/ naming (more easily readable); the vectors are sorted by frequency: freebase-vectors-skipgram1000-en.bin.gz Here is an example output of ./distance freebase-vectors-skipgram1000-en.bin:

様々なニュース記事から得られた 100B 単語を用いて学習されたエンティティベクタ: freebase-vectors-skipgram1000.bin.gz 様々なニュース記事から得られた 100B の単語に対して,非推奨の /en/ ネーミング(より読みやすい)を用いて学習されたエンティティベクタ: 頻度でソートされています: freebase-vectors-skipgram1000-en.bin.gz 以下は,./distance freebase-vectors-skipgram1000-en.bin の出力例です.

Enter word or sentence (EXIT to break): /en/geoffrey_hinton

Word Cosine distance 

/en/marvin_minsky           0.457204
/en/paul_corkum             0.443342
/en/william_richard_peltier 0.432396 
/en/brenda_milner           0.430886 
/en/john_charles_polanyi    0.419538 
/en/leslie_valiant          0.416399 
/en/hava_siegelmann         0.411895 
/en/hans_moravec            0.406726 
/en/david_rumelhart         0.405275 
/en/godel_prize             0.405176 

Final words(最後の言葉)

Thank you for trying out this toolkit, and do not forget to let us know when you obtain some amazing results! We hope that the distributed representations will significantly improve the state of the art in NLP.

このツールキットを試していただきありがとうございます。私たちは、分散表現がNLPの技術を大幅に向上させることを期待しています。

References(参考文献)

[1] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.
Efficient Estimation of Word Representations in Vector Space.
In Proceedings of Workshop at ICLR, 2013.

[2] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean.
Distributed Representations of Words and Phrases and their Compositionality.
In Proceedings of NIPS, 2013.

[3] Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.
Linguistic Regularities in Continuous Space Word Representations.
In Proceedings of NAACL HLT, 2013.

Other useful links(その他の有用なリンク)

Feel free to send us a link to your project or research paper related to word2vec that you think will be useful or interesting for the others.

word2vecに関連したプロジェクトや研究論文など、他の方の参考になると思われるものがありましたら、ご自由にリンクを送ってください。

Tomas Mikolov, Quoc V. Le and Ilya Sutskever.
Exploiting Similarities among Languages for Machine Translation.
We show how the word vectors can be applied to machine translation. Code for improved version from Georgiana Dinu here.

Word2vec in Python
by Radim Rehurek in gensim (plus tutorial and demo that uses the above model trained on Google News).

Word2vec in Java as part of the deeplearning4j project.
Another Java version from Medallia here.

Word2vec implementation in Spark MLlib.

Comparison with traditional count-based vectors and cbow model trained on a different corpus by CIMEC UNITN.

Link to slides about word vectors from NIPS 2013 Deep Learning Workshop: NNforText.pdf

Disclaimer(免責事項)

This open source project is NOT a Google product, and is released for research purposes only.

このオープンソースプロジェクトはGoogleの製品ではなく、研究目的でのみ公開されています。