Microsoft Bingのランキングエンジンをxgboostでシミュレート
Microsoft Bingのランキングエンジンをシミュレートし、ランキングを学習します
目的
inspector(検査官、監査人、検閲官、視学、警視正、警部補)
ランキングアルゴリズムは日々進化しています。Googleのサーチエンジンは200以上の特徴量を用いたり色々しています。
これらはGoogleでないと手に入らない特徴量も多数存在しており、容易に、ユーザが最適化できるものではなかったりします
わかりやすいものでは、ドメイン以内にコンテンツが十分に存在し、それがある程度参照されるものであれば、以前あったようにWelqさんのようにコンテンツの内容の是非によらず、ランクアップしてしまうような問題もございました。
意図しない作用をもたらすから、狙ってはいけないなどということはなく、SEOはビジネスにおいて極めて重要な課題です。
SEOでどの要素（サイト規模？テキスト数？キーワードの作り？コンテンツの内容？）などどれにどの程度注力すればいいのか判明したら大変なビジネスインパクトがあります。
ここでは、クリエイティブのキーワード（title, meta, body）で何がどの程度重要か、BingさんやGoogleさんなどを教師データとしたときに、機械学習のアルゴリズムでサイトを、どの程度有益なのか定量化してみようと思います。
お題
Rankingエンジンのランクの傾向を、検索クエリ結果から、ランキンされたサイトの自然言語的特徴から、獲得しようという意図です。
これを行うにあたって１つの制約があります。
1. ランキングエンジンのリバースエンジニアリングのような行為は認められるのか
- に関して述べると、この行為は、例えばGoogleやBingなどのサーチエンジンの競合を作るという意図がない、広域に解釈すれば、ビジネスでなければよいと言えそうである。例えば今回は、自己研究に基づくので問題がない。
Microsft Bingのランキングエンジンのクエリ(neologdに内在している辞書を利用)することによって、膨大なダイバシティの検索結果が得られます。
検索結果のランキングを見ることにより、同等のランキングエンジンが作成可能であると期待できます
ランキングアルゴリズム一覧
- lambdarank, lightgbmに実装あり
- lambdamart, xgboostに実装あり
読むべき論文
よく見る評価指標
目的関数
ranksvmフォーマット
資料が全くなく、調査して理解するまで結構かかりました。
ranksvmフォーマットはgroup fileというのが別途必要になっている
bingのデータクローン
- neologdで一般単語をとりだす
- bingでクエリを作成して、ひたすら大量に集める
- 1位=4, ２位=3, 3位=2, ４位=1で、単一ページでないドメイントップのサイトをランキングする
- 言語処理的にtitle, meta, bodyの自然言語でランキングしてみる
(本当はこれ+DeepLearningでやってもいい)
オペレーション
Githubで公開しています（問題等があればtwitterにておしらせくださいませ）
Operation 1. ランククエリ生成
neologdなどからnoun（名詞）を取り出して、それを検索クエリ群にする
import glob import pickle import json nouns = [] for name in glob.glob('mecab-ipadic-neologd/build/*/*.csv'): f = open(name) for line in f: ents = line.strip().split(',') if '名詞' not in ents: continue term = ents[0] nouns.append(term) open('nouns.json', 'w').write( json.dumps(nouns, indent=2, ensure_ascii=False) )
Operation 2. bingをスクレイピング
$ python3 scrape.py
Operation 3. フルドメインが入っているリンクをパース
$ python3 scan_pair.py
Operation 4. bingの結果からフルドメインをスクレイピング
$ python3 pair_scrape.py
Operation 5. フルドメインのHTMLをパース
$ python3 10-parse-htmls.py
Operation 6. 分かち書きして特徴量化
$ python3 20-make-vector.py
Operation 7. 疎行列で表現してranksvm形式のファイルを出力
$ python3 30-index.py
学習
OP7を実行すると学習可能なファイル群が出力されます
(xgboostのバイナリがlibcなどの互換がなくて実行できない場合は、xgboostを再コンパイルしてください)
$ cd rank $ ./xgb mq_train.conf
map(mean average precision)の略で、平均精度です。pairwiseで評価すると、mapでの評価になります。他の関数のndcgなどはうまく動作しません。なぜ？
1000roundでの精度はこの程度です
[20:36:05] src/tree/updater_prune.cc:74: tree pruning end, 1 roots, 936 extra nodes, 1252 pruned nodes, max_depth=36 [20:36:05] [999] test-map:0.721291
学習が完了すると、rank.modelというファイルが出力されます
予想
rank.modelをもちいて未知のクエリに対してランキングすることができます
$ ./xgb mq_predict.conf [20:51:20] 144775x162216 matrix with 3899318 entries loaded from test.data [20:51:20] start prediction... [20:51:49] writing prediction to pred.txt
pred.txtの中にランキングされたファイルが記されています。
ランクの値と、実際のランクはこのように表現され、やはり相関など何も考えなくても単純にランキングが上になりがちな構成という物がありそうです
(予想ランク＠左、実測ランク＠右)
1.05754 4 -0.578957 2 0.386893 0 0.511651 4 0.683687 2 -0.800342 0 0.642033 4 0.35129 2 0.74472 0 1.39248 4 0.454038 2 0.221512 0 ...
単純なSVMなどを利用すると、簡単に配信システムで計算できますが、勾配ブーストのようなランキングはどうなんですかね。決定木なのでC++のファイルなどに変換させるのが良いと思います
xgboost, lightgbmランキング意外と便利
ランキング学習はレコメンドエンジンとも深く結びついた技術でマネタイズのコアをなしうる重要なテクノロジーです
AIで自動判別でなんかすごいのを作る前の前哨戦で、レコメンドはぜひとも検討に値するテクノロジーです
おまけ
勾配ブーストによる特徴量選択の結果を見ることができます
強力に非線形化されているので、これ単独で見ることにあんまり意味はないのですが、どんな特徴量が選ばれやすいのかは視覚的に確認できます
例えばランキングに影響する単語群はtitleとkeywordの重要度が高いのはなるほどという感じなのですが、車なども強いことがわかります
title:インポートファッションアイテム 1989114 title:Sledge 680939 title:バンキング 465049 title:西善 314689 title:メイプルストーリー 188914 keyword: ベローズ の 専門 メーカー 180548 title:ラセン 153568 title:DV 86233 keyword:建築 資材 68659 title:あぜ 68124 body:none 60321 keyword: クロス ロード 51767 title:Shade 46926 title:食通 44635 body:, 43729 keyword:競艇 38174 keyword: 常滑 32940 title:多摩丘陵 29434 title:cherry 25848 body:MAZDA 25152 title:の 23459 title:エビス 23234 title:本田技研工業 23085 body:Jewelry 22530 title:・ 21902 ...
brand-transition(ブランドの変遷)
brand-transition(ブランドの変遷)
SVMで極性評価した単語をもちいて、声優のポジティブネスをniconicoニュースコーパスを利用して、時系列的に表現します
時系列的な変遷を分析することで、バズの検知や、話題、炎上などをシステム的にキャッチアップしやすくなります
もともとの起草
これは、もともともブランドの毀損などを評価しうるものとして、prophetなどの系列予想システムと連結させることで、急激なブランド毀損（炎上）などを検知して、炎上に対して適切な対応をとることにより、ブランドイメージを守ろうとするものでした(これは個人研究でやっていたのですが、３ヶ月ほど前にいろいろなところに提案しましたが、どこにも引き取ってもらえてないので、いくつか再スクラッチして自分の所有しているデータセットに変換し、公開ナレッジ化します)
Amazon, RakutenなどのレビューをコーパスにSVMなどで大規模極性辞書を作成する
もともとブランドのネガティブさ、ポジティブさというのはどのように評価すればいいのかわかりません。
この時、SVMなどをレビュー情報（星の数）などを教師データに、極性を重んじた学習の分割が可能になります
星の数を1,2,3個をネガティブとして、5個をポジティブとすると、非常にそれらしい結果が得ることができます。
学習した結果のウェイト
negative度が高いもの
売り手 -4.393270938125656 ガッカリ -3.947897992103171 がっかり -3.648103587594949 残念 -3.130127382290406 致命 -3.112032623756082 期待はずれ -3.083929660401355 返品 -2.948516584384151 灰皿 -2.87787780959521 ３つ -2.783511547585251 駄作 -2.771137686778778 物足りなかっ -2.663694159049179 最悪 -2.655338531812268 うーん -2.499197140760456 二度と -2.480062770645911 意味不明 -2.420151065200296 いまいち -2.419859090879487 失せ -2.41635935742869 つまらない -2.404018144393537 単調 -2.368271765218191 堀江 -2.34675269334997 つまらなかっ -2.316511096716675 タートル -2.288030642964168 イマイチ -2.27754859957102 目新しい -2.269002906892812 まずい -2.23071763111786 欠ける -2.222289341852733 ...
positive度が高いもの
お買い得 1.987645060840108 最高傑作 1.990702627997584 別格 2.011164421643425 目からウロコ 2.014549379784212 これ程 2.019119980229243 杞憂 2.026934292869131 戻れ 2.052378639149482 オジさん 2.061753308187434 痛快 2.061960603545156 欠か 2.087942969787786 叩け 2.08933 2.130187229517098 pop 2.1307765382222862 病みつき 2.142924963400594 憎め 2.160722430925575 洋楽 2.169574554504112 強いて 2.224321728820268 バイブル 2.229368722596254 絶妙 2.245596441611436 従う 2.254309352677592 五つ 2.255604793487576 待ち遠しい 2.25806614954727 逸品 2.265821501069568 最高 2.289466171874273 傑作 2.293924930835376 サウンドトラック 2.295214513832636 是非 2.311342110589227 半信半疑 2.39707658523505 ガル2.661651342883942922 R&B 2.6851915989280470909009 一括 2.730196185564076 リッツ 2.766706018272894 大正解 2.874333983897774 手放せ 2.948887203551322 必読 3.012749694663035 セレクトショップ 3.050995942436786 ５つ 3.081741024496506 秀逸 3.229761176207314 ...
このようにそれらしい結果が得られます
データセットをDropboxで公開していますので必要ならばご利用ください（商用利用は法的に望ましくないです）。
ある名詞（人名）が含まれているドキュメントが含まれているドキュメントのネガポジをその語の含まれている文脈の意味とする
仮説ベースで、ヒューリスティックにうまくいく方法ですが、このようにすることで、ドキュメントの極性と、ドキュメントに含まれる単語の紐付けを行うことができます
図1.
時系列的にドキュメントを並べて、ある人名のポジティブ度をSVMで作成した重みを利用して時系列順に並べる
niconicoニュースのコーパスは、毎日、ある程度更新されており、ライセンスの関係かわかりませんか、結構昔に遡れます（新聞社は多くの場合、過去に遡ることができません）
そのため、コーパスを日時の粒度でまとめて、並べ直して、その時のniconicoニュースのコーパスを利用すると、下記の図にすることができます。
SVMでレビュー情報を学習した単語に付与される重み情報から、ドキュメントのスコアを算出します（強調的に状態が見えるようにいくつかヒューリスティックにしてあります）
図2.
実験結果
100日以上、話題にされている声優でかつ、私がわかる声優さんが含まれるニュース記事の極性を判定して、sigmoidにかける前の重みで、重みのリストを手動でいくつか編集した物を用いて、日付順で極性のスコアの変遷を見ていきます。
声優を題材としたのは、単純に、niconicoニュースがオタクよりのコンテンツが強いからであって、それ以上の他意はございません
図３. 早見沙織の時系列データ
図4. 水瀬いのりの時系列データ
図5. 日笠陽子の時系列データ
単純に日々のニュースでポジティブに紹介されたようなことがあると、グラフ的に跳ねる現象になり、なんらかの異常値検知システムにて自動化もできそうです
コードとオペレーション
niconico newsなどのコーパスは各自でご用意ください
(スクレイパーもありますが、1secのsleepを入れていますが、そもそもどの程度許容されるものなのかよくわかっていません)
レビュー情報をパース
$ python3 10-scan-reviews.py
liblinear(sigmoid)で学習したウェイトを分析して、単語の重み付きファイルを構築する
$ python3 20-scan-weights.py
niconico newsを時系列で処理する
$ python3 30-news-time-series.py
声優名が含まれるコーパスを重み付き単語ファイルで評価
$ python3 40-actor-time-series-polarity.py
各々の声優名のデータを取り出す
$ python3 50-data-pick.py
結果
このように、時系列データして扱うと、ところどころ、ポジティブさみたいなものが跳ねるような事象を観測することができて、プラスの意味での炎上（ただの話題ですが）を観測したりアラートを流すことができたりしそうです。
声優統計みたいな感じになりましたが、他意はございません。niconicoニュースとオタク関連の記事の相性がよかったので題材をこのように定義しました。
ポアンカレエンベッディング
ポアンカレエンベッディング
Euclid空間にエンベッディングするようなword2vecは意味の上下関係が明示的に記されません。(情報としたあったとしても僅かでしょう)
ポアンカレボールという双曲幾何学空間に埋め込むことで、効率的に意味(や木構造)の上位関係をとらえることができます[1]
理解
ポアンカレボールはこのような、外周部に行くほど密になる球みたいなものなのです。
ポアンカレボールでは外に行くほど情報が密になり、空間が広がっているともとらえます。
数式で表現するとこのようになって、
gEというユークリッド距離がxが1に近づけば無限に大きくなることがわかります。
このポアンカレボール上にある二点間の距離はこのように表現され、単純なユークリッド距離ではないことが見て取れます。
この距離関数に基づいて損失関数L(Θ)を定義します。
これをSGDやFBリサーチの論文ではRiemannianSGDというオプティマイザを利用して最適化しています
双極幾何学空間に埋め込むと、情報が何らかの上下関係を持っており、木構造で表現できるとき、ルートノード（つまり抽象度が高い）方が真ん中にきて、枝葉に近いほど、外周部に行く傾向があるとのことで、これはポアンカレ空間に木の幹と枝を配置しようと試みるとき、幹が真ん中にきて枝が外周に来るとおさまりがいいのは、直感的に理解できると思います。
なんか以前やったDeep Graph Convolutionに似ているなと思っていたら、Abejaさんのブログでも同様の記述を発見しました[2]
何でもいいので、優秀なエンベッティングは距離空間を適宜定義することでその空間の形に応じた特性を獲得できそうということでもあり、ポアンカレボールは意味的、木構造的な関係を獲得できるし、別の距離空間ではそのようなものが定義できるのだと思います。
以下の実験のコード
実験
pythonの言語処理ライブラリであるgensimですでにpoincare embeddingが実装されています。
可視化の方法もjupyterを用いて簡単にできるので、なんかの情報のペアで木構造を持つと仮定できるデータセットがあれば、学習することができます。
poincare embeddingの論文では、動物名と動物の所属する種類などのペアのデータセットを利用して、poincareに埋め込んで評価しています。
(ライオン, ネコ科) (ネコ科, 哺乳類) ...
こんなどちらが上位の概念化は順序がむちゃくちゃでいいので、ペアのデータセットがたくさん作成します
データセット
旧日本海軍の艦種のいくつかのデータセットを用いてやってみましょう。
軍艦を発信点にして、大分する艦種と、艦種と艦名のペアです。
軍艦 駆逐艦 軍艦 戦艦 軍艦 巡洋艦 軍艦 空母 駆逐艦 陽炎型 駆逐艦 朝潮型 駆逐艦 吹雪型 駆逐艦 白露型 朝潮型 朝潮 朝潮型 大潮 朝潮型 満潮 ...
可視化
gensimでの実装は、jupyterとplotlyを用いてこのようにすることで、簡単に可視化できます
(おそらくFacebook ResearchのPyTorchでの実装は同じ方法は通用しませんが、こっちの方が本来性能はよさそうです)
import plotly import gensim.viz.poincare import pickle model = pickle.loads(open('model.pkl','rb').read()) relations = pickle.loads(open('relations.pkl', 'rb').read() ) plotly.offline.init_notebook_mode(connected=False) prefecutre_map = gensim.viz.poincare.poincare_2d_visualization(model=model, tree=relations, figure_title="艦種", show_node_labels=model.kv.vocab.keys()) plotly.offline.iplot(prefecutre_map)
評価
ポアンカレボール上に配置するときに、乱択アルゴリズムでサンプリングするらしいので、小さいデータセットではきれいな円状に配置されませんが、おおむねそれらしい結果が得られています。（割り切ってランダムネスの影響を許容するといいでしょう）
朝潮型が変なところに来ています。初期値のラムダムネスにより変なところにきているようです
なかなかgemsinで実行するとうまくいきませんね。（最適化アルゴリズムにSGDなどの乱択がはいるので仕方がないですが。。。）
より、細やかに丁寧に距離函数を再定義できそうな実装系としてFacebook社のPytorchのSGDオプティマイザと距離函数を双曲線距離に定義した物を使うと、learning rateを最初に大きく取って少なくしていくなどの戦略が取れるので、より細やかに綺麗に学習が収束しそうです[3]
図 Facebook ResearchによるPoincare Embedding
参考文献
RNNで暗号であるEnigmaを解く
RNNで暗号であるEnigmaを解く
Enigma暗号とは
1918年に発明されたEnigmaは第二次世界大戦時に発明された暗号化機であり、電線の配線のパターンと、ロータといわれる入力するたびに回転する円盤のパターンで、様々な文字の置き換えを行います。
ドイツ軍で用いたられたアルファベットの数だけ暗号化のもととなる配線が記された三つのロータを組み合わせて、膨大な動的に変換するパターンを構築して文字列を置換して、単純な交換則が成立しない複雑な暗号を構築して連合軍を苦しめました。
図1. JavaScriptによるEnigma Simulator
連合国側のイギリスの特殊チームのULTRAによって解析されたようです。数学的な暗号の原理を追っているのですが、まだ完全にキャッチアップしきっておりませんが、群論とコンピュータのパワーとヒントとなるキーが人間の発想に依存するという特性を利用して解いたそうです。総当たりに近い方法を用いており、とにかくコンピュータリソースが必要でした。
2006年、分散コンピューティングを利用して総当たりにて、最後の未解決であったEnigma暗号を解いたとのことです[1]。
どのようにEnigmaを連合国軍は解いたのか
二つの方法を組み合わせたような表現を確認しました。
- Bombeとよばれるコンピュータで総当たり攻撃した
- 人間が利用しがちなカギや文章（日付などが末尾に入るとか）から推定されるパターンを限定する
図2. 現代に再現さたBombe(Wikipediaより)
今風の機械学習で解くにはどうすればいいのか
2.のように、何らかの暗号化前の文章と暗号化後の暗号文が手に入ったとします。このとき、この対が十分な量があるとき、ディープラーニングのアルゴリズムの一つであるRNNで解くことが可能です[2]
ロータが機械的に回転し、絡み合うような仕組みは、ディープラーニングのような機械学習は苦手だろう思い込みがあったので、この[2]の資料を見たときは驚きました。
ロータが二つのEnigmaを仮定
複雑な三つのロータではなく、簡単にした二つのロータのみで構成されるEnigmaを仮定します
Enigmaのロータは一文字進むごとに回転し、初期値が不明になっており、キーはランダムになっているとします.
初期値が不明なため、26(+3)2パターンの成立しうるロータの状態をディープラーニングのネットワークを施行し、もっとも自然な文字列である初期状態とロータの配線を全探索しないと、原理として解くことはできません。
暗号化として以下のような二つのロータを仮定したスクリプトを作成ました
コーパスとしてBBCの公開ニュースコーパスを利用しています。
total = '' for name in glob.glob('courpus/bbc/*/*'): try: text = open(name).read() except Exception as ex: continue buff = [] for char in list(text.lower()): if char in char_index_0: buff.append(char) total += ''.join(buff) # random slice pairs = [] for index in random.sample( list(range(0, len(total) - 150)),100000): _char_index_0 = copy.copy(char_index_0) _char_index_1 = copy.copy(char_index_1) real = total[index:index+150] enigma = [] for diff, char in enumerate(real): # roater No.1 update _char_index _char_index_0 = { char:(ind+1)%len(_char_index_0) for char, ind in _char_index_0.items() } # get index ind = _char_index_0[char] next_char = chars[ind] # roater No.2 _char_index_1 = { char:(ind+1)%len(_char_index_1) for char, ind in _char_index_1.items() } # get index ind = _char_index_1[next_char] next_char = chars[ind] enigma.append(next_char) cript = ''.join(enigma) crop = random.choice(list(range(len(char_index_0)))) real, cript = real[crop:crop+100], cript[crop:crop+100] pairs.append( (real, cript) ) open('pairs.json', 'w').write( json.dumps(pairs, indent=2) )
DeepLearningのネットワークを設計
Kerasで実装しました。
GRUを用いネットワークはこのようになっています。
初期状態が不明なEnigmaで暗号化された暗号文を最大100文字入力し、対応する100文字を入力します
timesteps = 100 inputs = Input(shape=(timesteps, 29)) x = Bi(GRU(512, dropout=0.10, recurrent_dropout=0.25, return_sequences=True))(inputs) x = TD(Dense(3000, activation='relu'))(x) x = Dropout(0.2)(x) x = TD(Dense(3000, activation='relu'))(x) x = Dropout(0.2)(x) x = TD(Dense(29, activation='softmax'))(x) decript = Model(inputs, x) decript.compile(optimizer=Adam(), loss='categorical_crossentropy')
前処理
Enigmaの配線をランダムで初期化
$ python3 14-make-enigma.py
コーパスから暗号文と正解のペアを作成
$ python3 15-prepare.py
RNNで入力する密ベクトルに変換
$ python3 16-make-vector.py
学習
全体の99%を学習します
$ python3 17-train.py --train
評価
学習で使わなかった1%のデータを評価します
$ python3 17-train.py --predict
出力
[オリジナルの文] all targets, he said. the exceptional quality of the paintings in our permanent collection is also h [入力された暗号文] ccxej,,,xum yh.bfpp,ggm.ihsorjges.iy .cyvmyl wvogaxdqyzqmomtdkzbqqeobszs uyyaoagyy.nsuomynekaescf sc [モデルで評価した文] all targets, he said. the exceptional quality of the paintings in our permanent collection is also h
このように、Enigmaのネットワークが未知であっても、確定してわかるテキストが十分にあれば、RNNでエニグマ暗号は解けることがわかりました。
今回は仮想的なロータを二つソフトウェア的に再現しましたが、ロータが三つでも十分にRNNのネットワークが大きく、データが十分にあれば、この延長線上で解けると思います。
