2015-03-01

JubatusにThompson samplingを実装する

Jubatus0.7.0についにBanditアルゴリズムが実装されたのですが、漸近最適なアルゴリズムがまだ実装されていないので、Thompson sampling (TS) を実装してみました。

TSの詳細はThompson sampling - Wikipedia, the free encyclopediaなどに詳しいです。TSはThompsonさんが1930年に提案された最も古いアルゴリズムの1つなのですが、バンディット業界ではUCBなどと比べるとほとんど知られていませんでした。Googleの中の人がABテストに利用したことや、NIPS2011でTSの性能を他のアルゴリズムと比較した論文が出版され、圧倒的に性能が良いことが示されたことでTSは一躍注目をされるようになりました。理論的にも、TSは漸近最適なアルゴリズム *1の１つとして知られています。このアルゴリズムはベイズ推定に基づくためその実装が報酬の確率分布に依存するのですが、今回は報酬が{0,1}の場合を考えてみましょう。この場合の共役事前分布はBeta分布なので、Beta分布を実装すればTSアルゴリズムを作ることができます。

というわけで、TSを実装してGithubに置いてみました*2。

https://github.com/jkomiyama/jubatus_core/commit/ce2abe22909473a557af957064e2e5c220d361b5

性能を比較してみましょう。
サーバスクリプト: ts.json

{
  "method": "ts",
    "parameter": {
  }
}

で、Banditサーバを起動します。

jubabandit -f ts.json

クライアントでbanditのシミュレーションを回してみます。
クライアントスクリプト: test.py

#!/usr/bin/env python
# coding: utf-8

host = '127.0.0.1'
port = 9199
name = 'test'

import sys
import json
import random
from math import *

import jubatus

def kl(p,q):return p*log(p/q)+(1-p)*log((1-p)/(1-q))

def run(client):
  arms = {
    'best':0.1,
    'soso':0.05,
    'bad':0.02
  }
  player = 'bandit'
  bestAvg = arms['best']
  counts = {}
  for arm in arms.keys():counts[arm]=0

  client.reset(player)
  regret = 0
  for arm in arms.keys():
    client.register_arm(arm)
  for t in xrange(10000):
    arm = client.select_arm(player) 
    if random.random() <= arms[arm]:
      reward = 1.0
    else:
      reward = 0.0
    counts[arm]+=1
    regret += bestAvg - arms[arm]
    client.register_reward(player, arm, reward)
  print "regret =",regret 
  #regret asymptotic lower bound
  lower = sum([log(10000)*(bestAvg-arms[arm])/kl(arms[arm],bestAvg) for arm in arms.keys() if arms[arm] != bestAvg])
  print "lower =",lower

if __name__ == '__main__':
    client = jubatus.Bandit(host, port, name)
    run(client)

サーバがUCB1の場合*3と、今回実装したTSの場合の結果比較：
f:id:jkomi:20150301150125p:plain

約９倍の性能向上（損失減少）ができました*4。

*1:どんなアームの集合に関しても上手く動くアルゴリズムの中で、理論的な性能が最も良いもの

*2:jubatusにpull requestを出したいのですが、著作権周りがよくわからないので保留中・・・

*3:Jubatusにすでに実装されている別のバンディットアルゴリズム、これも有名

*4:バンディットは確率的な問題のため、ちゃんと性能比較したい場合、もっとたくさんの回数のシミュレーションを行って期待値を取る必要がありますが、今回は簡単のため１回しかやっていません

2014-07-23

WWW2014勉強会で論文紹介をさせていただきました

WWW2014勉強会で論文紹介をさせていただきました。

WWW (International World Wide Web Conference)はWebに関する有名国際会議で、トピックは割となんでもOK（データベース、情報検索、データマイニング、自然言語処理、機械学習、ゲーム理論、etc）な印象です。

WWW2014勉強会発表 from jkomiyama

紹介論文は最初の2つがオンライン広告、残り１つが推薦です。

オンライン広告の話はInternet Economics & Monetizationというセッションで、ざっくばらんに言うとEC（オンラインの情報処理とゲーム理論の有名国際会議）と近い雰囲気を感じました。広告の配置をどうすればいいか、というのは実は難しい問題で、売り手と書い手の多人数ゲームとして定式化できます。ECには日本人研究者の論文がほとんどないですが、僕の専門と近いので興味があります。

３つ目の推薦の論文はフィルターバブル問題というものを扱ったものです。フィルターバブル問題は、推薦システムを利用し続けることによって、自分の知りたい一方的な情報しか見られなくなってしまうとする問題で、下のフィルターバブル問題の提唱者のTEDトークでは『facebookでリベラルな友人のリンクをよくクリックしていたら、保守派の友人のフィードが流れてこなくなった』という例で説明されています。

論文の内容は、映画の推薦が本当に「フィルターバブル」されているのかをMovielens（映画推薦サイト）のデータで検証したものです。

2014-04-02

意訳：2009年から2014年の機械学習の理論的進歩について教えてください

Quoraに投稿された質問 "What has happened in theoretical machine learning in the last 5 years (2009-2014)?"

「2009年から2014年の機械学習の理論的進歩について教えてください」

への、機械学習研究者Yisong Yueの回答を翻訳しました。そのままだと通じない部分は意訳しているので、原文に忠実ではありません。

「2009年から2014年の機械学習の理論的進歩について教えてください」への回答

私の個人的な視点で話します。

潜在変数モデルに対する最適推定について:

理論的な進歩として私が最初に思いつくのは、潜在変数モデルに対する（ほぼ）最適な推定です。この潜在変数モデルの最適推定は一般的に非凸な問題であり、つまり（よく知られている）凸最適化の手法の通用しない難題です。

最も輝かしいアプローチはスペクトラル学習を利用するものです。スペクトラル学習の最も重要なツールは特異値分解です。特異値分解は、問題の構造を仮定することにより、特定の非凸の問題を最適に解くことができます。大雑把にいうと、スペクトラル学習や関連手法は線形代数とモーメントの方法を使い、潜在変数のある非凸な問題を特異値分解によって最適に解ける問題に再定式化します。

近いアプローチとして、低ランク行列復元とスパース辞書からの完全情報復元があります。これらの手法に共通しているのは、推定問題に対する代数構造の性質をうまく利用することによって最適な解を導くというものです。

機械学習のコミュニティにはそんなに有名ではないかもしれませんが、ノイズのあるデータからの超解像という問題があります。基本的なアイディアとしては、同じデータに対して複数の解像度の低いノイズを含むソースがあった場合にそれらを重ねあわせて信号解析を行おうというものです。ソースが解像度が低くノイズが乗っているにもかかわらず、解像度の高いデータを復元可能なことをこの論文は示しました。

インタラクティブな機械学習について：

近年、適応的・インタラクティブなアルゴリズムの最適性について多くの研究がなされています。

適応的劣モジュラ性の方向性は非常に興味深いです。劣モジュラ関数は、情報量の増加や多様性を扱うためのツールとして近年注目されています。まず、その前に能動学習について説明しましょう。能動学習は、クエリ（データ要求）を適応的に出すことによって少ないデータ数で問題に対しての不確定性を減らし正確な推定を得る方法です。

適応的劣モジュラ性は、多くの能動学習の問題を一般的な枠組みで解く仕組みだと思ってください。これらの問題が適用可能な例としては、医療テストでの患者の病気をできるだけ少ない問診で絞り込む問題などです。

関連問題として、インタラクティブ劣モジュラ集合被覆の問題などがあります。

能動学習の分野はここ数年で大きな進歩がありました。とくにこれという論文は思いつきませんでしたが、いくつか良い論文が挙げられます。能動学習において強い性能保証があるアルゴリズムを作るための課題は、問題を解く決定木の組み合わせが指数的になることです。例えば、20のYes/No式の組み合わせがあった場合には、2^20通りの組み合わせが知識の状態としてありえることになります。理想的なアルゴリズムは、20の問題の回答がどのようにあっても解くことができなければなりません。

関連する研究の流れとしては、多腕バンディット問題のアルゴリズムがあります。この分野で最も興味深い進歩は、トンプソンサンプリングをはじめとする確率マッチングのアルゴリズムでしょう。これらのアルゴリズムは、計算的な単純さから非常に大きな興味を持たれています。しかし、理論的な解析はこれまであまり行われていませんでした。近年の２本の論文（とその関連研究）は、この分野における理論的な解析を行っています。とくに、後者の論文は確率マッチングの解析をよく知られている信頼上限法の解析に還元するものですが、適用範囲が非常に広く興味深いです。

機械学習とゲーム理論：

ゲーム理論は戦略的な意思決定を扱う分野です。

ゲーム理論の応用例としては、オンライン広告における価格の決定があります。オンライン広告の価格は、ウェブサイトと広告出稿者の収益を最適化するように決められます。最適価格は広告のコンバージョン率や、コンテキスト（つまり検索クエリ、コンテンツ、ユーザ情報）に依存するため、この価格の学習ではこれらの要因を考慮にいれる必要があります。

一般的に、ゲーム理論の研究者はこれまで、エージェントが(A)十分大きな計算リソースを持っていることと(B)自分にとっての環境に対して完全な情報を持っていることを仮定してきました。言い換えると、(A)は指数的な計算量を要求するような戦略を許容すること、(B)は環境に対する学習が要らないことを意味します。

もちろん、この2つの仮定は現実世界では正しくありません。しかし、多くのゲーム理論における解析はこの２つの仮定において特定のメカニズム（メカニズムの例としては、オンライン広告では広告出稿者が広告市場とどのようにやりとりを行うかの枠組みを想定してください）が誘引両立的であること（訳注：戦略的に価格を操作したりしてもメリットが得られない健全なシステムであること）を示すことに成功してきました。この分野はメカニズムデザインと呼ばれています。

ここ数年の優れた論文は、メカニズムデザイン下での学習（誘引両立的を満たす学習）をこの２つの伝統的な仮定の外でも行うにはどのようにすればいいかを示しました。例えば、(B)を仮定せずに不確定性のある状況下でどのような学習をすればよいか。例としては"Truthful Mechanisms with Implicit Payment Computation"という論文があります。

もうひとつの研究の流れは、複雑なマーケットの動きを予測することです。こちらは戦略の計算量の削減に貢献し、２つの仮定の(A)を取り除いた計算可能な戦略を作ることに貢献しました。例としてはこの論文を挙げておきます。

機械学習とプライバシー：

プライバシー保護は、データを扱う上でどんどん重要になっています。差分プライバシーという概念は、公開データに故意にノイズを入れることによってどれだけその中にあるプライベートなデータを守れるのかを統計的に考察します。差分プライバシー下での機械学習は近年の研究の１つの流れとなっています。この論文が参考例です。

（訳はここまで）

所感：

Yisong Yueの論文は結構追っているので、彼が機械学習に対してどういう概観を持っているのかというのは僕にとっては面白いですね。

あまり関係ありませんが、YisongのHPは彼の顔写真がたくさん掲載されていてすごい自信家だなーと思います。

2014-03-31

MSRA（北京）滞在持ち物リスト

2013年11月から2014年2月までMSRAに滞在していたので、その間の持ち物のリストです。

keisksさんとceekzさんのエントリを参考にしました。
http://keisks5.blogspot.jp/2013/05/msra.html
http://d.hatena.ne.jp/ceekz/20120715

前提知識

利便性

ホテル近くにウォルマート、会社近くにカルフールがあるのでたいていの日用品はそこで揃います。
夜10時ぐらいまで開いているので退社後でスーパーに行くことができます。

買うのに会話が必要なもの（例：SIMカード）

基本的にMSの外では英語は通じないので、現地インターンに手伝ってもらうことになります。

必須持ち物

パスポート：要ビザ

クレジットカード：ATMでいざとなったら人民元を引き出す為
現地通貨：クレジットカード決済はなぜか通らないリスクがあるらしいので、支払いは基本的に現金でした。最初の給料振り込みまでの時間に必要な現金を持っていく必要があります（１ヶ月の生活費は2013年では4000元程度でしたが、物価変動が激しいので将来は違うかもしれません）。

薬
処方箋薬は滞在時間中必須です。市販薬（例：正露丸）は現地のWatsons（屈臣氏）でも買えますが、安全性とかを考えると風邪薬とかは持っていたほうが無難です。

衣類
最低で２、３日ぶんぐらいあればいいかもしれません。現地にユニクロなどがあるので現地でも買えます。

ノートPC（＋充電ケーブル）

携帯電話
現地のSIMを契約するには現地インターンに手伝ってもらう必要があります。僕は結局SIMを買いませんでした。
インターネットが使いたい場合は喫茶店とかに行っていました。

書類のコピー（パスポート、査証、地図、オファーレター）

オファーレター以外は使わなかったですが、トラブル対策用に持っておくべきでしょう。

必須ではないけど持って行くと役に立ちそうなもの

旅行保険
僕はかけませんでしたが、他のインターンは掛け捨ての旅行保険に入っていました。

ビタミン剤
現地のWatsonsで買って飲んでいました。安全性はどの程度か未知数です。

爪切り
現地でも買えますが品質が日本より悪そうです

予備のメガネ
使う可能性低いですが入手が難しいので

マスク
N95（防塵）のマスクをつける必要があります。現地でも買えます。他のインターンから余っているものをもらえるかもしれません。

歯ブラシ・歯磨き粉
現地でも買えます。品質を気にするなら持って行ったほうが良いです。

髭剃り
現地でも買えます。品質を気にするなら持って行ったほうが良いです。

シャンプー
現地でも買えます。品質を気にするなら持って行ったほうが良いです。

ポケットティッシュ
基本的に北京のトイレには紙が用意されていることが期待できないので、水に流せるタイプのを用意したほうがいいかもしれません。現地でも買えます。

タオル
現地でも買えます。たまにハズレがあります（洗濯すると綿が散るタオルを買ってしまいました）。

ヘッドホン
現地でも買えます。電子機器の値段は日本と比べてそんなに変わらないです。

文房具（ペン、ノートなど）
現地でも入手可能です。品質は日本より悪いですが使えないレベルではないです。

ドライヤー
現地でも買えます。

保湿クリーム
現地でも買えます。

図書（研究関係・小説）
意外と使わないです。

モバイルブースター（エネループ）
これも意外と使わないです。

海外プラグ変換アダプター
プラグの形は日本と同じですが電圧が異なります。ノートPCなどは中国の電圧でも動くので基本的に必要ないです。