2016-12-06

報酬が線形モデルで表せる時のバンディット問題

バンディット問題の理論とアルゴリズム』本の,報酬がなんらかの特徴の線形モデルによって表現される場合に使える線形バンディットが前から気になっていたので輪読会で発表担当をするなど.

スライド


アルゴリズムの実装と人工データによる実験

感想

行動(腕)毎の報酬を推定するのでは無く,報酬モデルのパラメータを推定するという方策.妥当なモデルが作れたら実際に使えそうな感触.
実装は一発書きおろしで検算をしていないが,一応それっぽく動いた.ラプラス近似の処理が重いので勾配ベクトルとヘッセ行列の計算過程はキャッシュしておかないとつらい.
LinUCBかThompson Samplingかどちらを使うかというと,報酬が同期で観測できない広告配信は後者一択で,報酬が二値の場合はロジスティック回帰モデル方策がよさそう.あとはクリックやコンバージョンを線形で表現するための特徴量が上手く見付かればいいのだが…….

さらに現実的なケースとして9章には報酬が時間変化する例もあるので,続きも読んでいきます.

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)
本多 淳也,中村 篤祥
講談社
売り上げランキング : 79416
Amazonで詳しく見る by AZlink


このエントリーをはてなブックマークに追加

2016-11-22

IBIS2016 ポスターセッションのメモと感想

講演セッションのメモの続き

ポスターセッション

  • D1-64: ニュース・動画サービス間のクロスドメイン推薦における課題
    • Yahoo! ニュースのデータを元にGYAOのリコメンドモデルを作るという問題
    • Dmain Adversarial Trainingとか言うらしい。
    • 一つのDNNのモデルを、ヤフーニュース、GYAOの両方の素性を食わせても同じ結果がでる様に訓練するアプローチ
  • D2-57: 転移学習を利用したクロスドメインレコメンデーション
    • クロスドメイン推薦
    • サービスAとサービスBの二つのドメインを結びつける変換行列を求めて、それを予測に利用する
  • D1-49: Scalable Clustered Multi-task Learning
    • マルチタスク学習。店舗毎のデータサイズが14と非常に疎ではあるが、全ての店舗をまとめて学習する事でうまくいっている。
    • 広告配信でもコンバージョンは非常にスパースなので、スパース+マルチタスク学習は相性がいいかもしれない。
  • D1-39: クリックフィードバックを用いた記事の地域性推定モデルの構築
    • ローカルニュースの配信最適化のために、ニュース記事と地域性の関係性を学習する。訓練データはクリックをした端末の位置情報とニュース記事のBoW表現のため、全自動運転できるのがメリット。結果からは単純に記事中に出てくる地域名とのマッピングでは求められないような関係性が見いだせるのが面白い。
  • D1-6: VAEとGANを活用したファッションアイテムの特徴抽出と検索システムへの応用
    • 画像+テキスト検索。画像で表現した方が良い物と、テキストで表現した方が良い物、それぞれ利用できるため利用シーンはファッションに留まらないと思う。
  • D2-5: Large-Scale Price Optimization via Network Flow
    • すごい。ある商品Aの値段を変えた時の、他の代替品の需要増加or減少までモデルに入れた価格調整アルゴリズム。従来の手法では計算が遅すぎたが、劣モジュラを利用した最適化問題とする事でスケールさせる事に成功。既に案件に投入しているとの事。
  • T2-18:バンディットアルゴリズムを用いたメンテナンスタイミング適正化
    • メンテナンス対象の機器の故障傾向がわからない問題設定、これをバンディット問題として解く。各腕を1日目にメンテ、2日目にメンテ、3日目にメンテ … と置く変則型。時刻tはメテナンス試行回数目に相当する。実際に損失は減ったとの事。
  • D1-19: 区間値公開による安全な予測値公開メカニズムと差分プライバシーメカニズムの有用性による比較
    • 診断アプリの様なユーザーの特質Xを入力して結果Yが得られるアプリケーションにおいて、結果Yから特質Xが特定できてしまうのを避ける方法。

このエントリーをはてなブックマークに追加

2016-11-21

IBIS2016 講演セッションのメモと感想

第19回情報論的学習理論ワークショップ, 2016.11.16〜19, 京都大学 吉田キャンパス

順序構造上の情報幾何的解析

大阪大学 杉山麿人
資料: http://mahito.info/files/Sugiyama_IBIS2016.pdf

  • Posets = 半順序構造はいろんな所に出てくる
    • 例えばベキ集合 (Power Set)
  • パターンマイニングでは
    • Frequencyをよく使う、何回出現したか。空集合は1。和は1を越える
    • Probabilityも考えられる。空集合はゼロ。和は1
    • FrequencyとProbabilityの関係は、確率の和でFrequencyが出てくる
  • log p(X) = Σζ(s, x)θ(s)
  • η(x) = Σ_{s∈S}{ ζ(x, s)p(s) } = Σ_{S≧X} {p(s)}
  • ゼータ関数 ζ(s, x)
    • 1 if s ≦ x else 0
  • 構造上におけるアイテム毎の確率分布を考える事で、ベキ集合の全てが揃っていないデータの解析が可能になる。
  • 従来のパターンマイニングは2I個の事象列挙が前提になっており、パターンが増えるとメモリに乗りきらない問題があった、この問題を解決できる。

感想

広告配信(アドネットワーク)だと枠とキャペーンの組み合わせでCVRを考えているが、パターンマイニングのアプローチを取ると2^(枠*キャンペーン)個の組み合わせを列挙しなければならない所が、データ出現箇所のみのデータからべき集合の確率分布を起せる??
ある構造のKL-Divergence分解をする事で、特定のアイテムがKL-divegenceにどれだけ寄与しているか求められるというのも面白い。

頻度論とベイズをつなぐ統計的信頼度

大阪大学 下平英寿

ベイズ統計と頻度論におけるp値の差異はどこからきているか、という話

感想

ちゃんと理解できてない、苦手な所だ……。

低ランクテンソルの学習理論と計算理論

東京工業大学情報理工学院/JSTさきがけ   鈴木大慈
資料: http://www.slideshare.net/trinmu/ibis2016
  • スカラー → ベクトル → 行列 → 3階のテンソル → 4階のテンソル……
  • 行列分解による予測と同様に、テンソル分解による予測処理ができる。低ランクテンソルに分解する方法と実際のYahoo! ショッピングの予測まで。

感想

Yahoo! JAPANのデータが出てくるあたり、産学連携してるっぽさ。
なぜテンソルを分解したいのか今まで理解していなかったので、ためになった。なるほど行列分解と同じモチベーション (そりゃそうだ)。

Strategies & Principles for Distributed Machine Learning

Eric Xing, カーネギーメロン大
  • すごい人きた
  • 機械学習システムの設計の話
  • モデル学習時の計算をどのように分割するか
    • Structure Aware Parallelization
    • Structure-aware Dynamic Schedule
  • http://www.cs.cmu.edu/~epxing/papers/2016/Xing_Engineering16.pdf
  • Sparkのその先のタスク実行効率化、どのようにしてタスクを並列に動かすか
    • Safe/slow (BSP) vs. Fast/risky (Async)
    • A Stale Synchronous Parallel Bridging Model

感想

計算機科学の恩恵に与っているアプリケーション開発現場の人としては、さらなる高速化は楽しみなネタの一つ。Sparkのその先の話は知らなかったので面白かった。

機械学習ビジネス化の進展と今後の方向

日本電気株式会社データサイエンス研究所 森永 聡
  • ビジネス現場のデータ活用の進捗
    • 見える化
    • 予測分析
    • 意思決定 (最適化・制御) ← いまここ
    • 人工知能間の交渉・協調・連携
  • 異種混合学習
    • モデルの自動選択?
  • インバリアント分析
  • テキスト合意認識
  • 自己学習型異常検知
  • BICは自由なパラメータの数が利用されるが、実際はパラメータ間の自由度がもっと低い事がおおい
    • FICを使ってモデル選定をしてしている。
    • FICについては論文読んでください。

感想

NECさんは独自の用語を使うので、元の技術を探すのが大変な印象。
異種混合学習の元ネタはAISTATSのこのあたりらしい

時系列ビッグデータ解析の新たな展開

熊本大学 櫻井保志
  • 大規模テンソル分解
    • 非線形モデリング
    • The Web as a Jungle
    • 競合関係ネットワーク
  • 特徴自動抽出
    • AutoPlait: Automatic Mining of Co-evolving (SIGMOD 2014)
    • Automatic mining algorithm
  • モデル自動選択
  • 非線形テンソル分解 (CompCube WWW 2016)
    • 時系列予測?
    • Local seasonality for IPod
    • 地域性で分解
    • SARIMAよりも性能がいい
  • リアルタイム予測
    • RegimeCast KDD 2016
      • レジームシフトの概念を使っている
      • レジームシフト → 自然界における構造や性質の急激な変化
      • Googleトレンドの3ヶ月先を予測する
      • 円ドル相場の未来予測
    • BRAID SIGMOD 2005
      • IoTデータストリーム解析
      • Smart assistant service

感想

新しいネタを追えてなかったので助かった。RegimeCastはソースもPythonで読みやすそうなので使ってみたい。

IT企業における機械学習

京都大学 山田誠
  • Yahoo Labsはどんなものだったか
  • Yahoo.comのサイトに何が使われているか
    • 検索 → GBDT (決定木)
    • 広告 → ロジスティック回帰, Factorization Machine
    • 検索結果ランキング → GBDT
      • 低次元なデータには非線形なモデルを使う
    • 詐欺検知
      • 詐欺の傾向は耐えず変化する
      • 最終的な詐欺か詐欺じゃないかは人間が行なう → 能動学習
      • 特徴が少ないのでGDBTを使う
  • 検索結果ランキング (WSDM 2016 Best paper)
    • 視線が最初にどこに行くか → 画像のまわり。ランキングの上からクリックされるという前提は崩れている
    • CTRをどう最適化するか
      • 満足度 = Q(検索結果, 表示方法) となるようなQを学習する
      • 表現方法 = argmax(Q, 表現方法) となる表現方法を利用する
  • どう学習するか
    • Quadratic interaction model
    • (Factorization machine)
    • 高次元x大規模xスパース
      • 次元数も標本数も大きいがスパース
      • テキストデータ
      • クリックデータ
      • リンクデータ
    • ナイーブにはSVD、観測できていない所はゼロにしてしまう。
      • しかしこれは強い仮定となる。
      • Alternating Least Squares (ALS)
      • じゃあどうするか、観測されている要素のみを使って行列分解
    • 今度はコールドスタート問題
      • Collective Matrix Factorization (Factorization Machineと関連)
      • 情報の無い人に推薦できない。補助情報を使うと良い。
      • 凸の複合行列分解
    • Tumblrのブログ推薦
      • Tumblr - Dashboard
      • ↑の手法を使って行列分解
  • まとめ
    • 低次元大規模サンプルには GBDT使え (Gradient Boosted Decision Tree)
    • GBDTは非線形性が使えて特徴選択もできるためパフォーマンスが高くなる
    • SVMはうまくいかない
    • 大規模疎行列 (クリックデータ)
      • Collective Matrix Factorization

感想

バンケットで山田先生が「雑な発表で申しわけない〜」みたいな事をおっしゃっていたが「xxな時はとりあえずyy使え、理由はzzz」というのはアプリケーションを実装する人間にとっては試行錯誤のコストが減らせるので大変ありがたい。GBDTは決定木なので、人間が見て理解できる形に落せるのが安心できそう。いざという時の説明責任が果たせる。

詐欺検知について「詳しい事は言えない」との事だが、自分も不正クリック検出やってたのでわかる……。外に漏らした瞬間に対応されて労力が無になる。ただ、社内だけで検出方策を練っていても手づまり感があるので、適度に外の意見も貰いたいと思う事もしばしばあります。暗号アルゴリズムの様に、公開する事で強くなる方法があればなあと。

ポスターセッションのメモに続く

このエントリーをはてなブックマークに追加

2016-10-17

Spotify社のエンジニア評価制度

Spotifyが日本に上陸しましたね。現在はアプリをインストールしてもすぐにサービスが利用できない様子、その隙に彼等の技術職評価制度についてのブログエントリを読みます。
ブログエントリは3部作になっており、技術職のキャリアパスフレームワークを作ったモチベーションに始まり、そこから得た物まで纏まっています。

印象に残った箇所

  • キャリアパスフレームワークをいつ作るか
    • 会社の初期の頃にはキャリアパスフレームワークは不要である。しかし8年間、Spotifyは昇格・昇給の正式な手続きが存在しなかった。
    • 昇格にはラインマネージャかプロダクトオーナーになるのが必要だと社員は考える様になってしまった。Spotifyにおいては、それは職種変更同然で開発者としての成長では無い。
    • 2014年の春に "career ladder" の開発に着手した。
  • 目標
    • Spotifyの文化に適合しており、社員の多様性、さまざまな経験度・ロールに適用可能なフレームワークを作る事。
  • 5つの特質
    • 個人の成功よりもチームの成功
    • 継続的な個人/チームの成長
    • 説明責任を持つ事
    • 仕事のビジネスインパクトを考える事
    • 各人がそれぞれの分野で熟練する事
  • 4つのステップとレベル定義
    • Individual
      • 新規要員。どのように生産的であり貢献できるかわかっている。
    • Squad / Chapter (チーム)
      • チームメンバとして貢献できており、一緒に働くメンバーの力になっている。
    • Tribe / Guild (より大きな組織)
      • 所属するチームを越えて活躍できる人。もしくはある技術に造詣が深い・困難な問題を解決するスキルがある・部署を越えた問題を解決に導ける。
    • Technology / Company (組織の最高レベル)
      • 会社全体に貢献できるレベル。組織を越えた活動に十分な時間を費やす事を期待される。
  • 各ステップに期待する行動
    • たくさん (気になる人は原文を参照してみてください)
  • ステップの昇格手順
    • squad/chapterへの昇格は、ピア(入社時に割り当てられるサポート担当?)のフィードバックに基づいて決定される。
    • tribe/guildへの昇格は、tribeレベルのリーダーで相談した後、関係するtribe leadの承認が必要。
    • technology/companyへの昇格は、technicalレベルのリーダーで相談した後、CTOの承認が必要。
    • 昇格には責任範囲の拡大が共なう。
    • 実績よりも振舞いを重視する。これはイノベーションを推奨するためであり、失敗は起る物とする。
  • 給与
    • 同地域・同業界の給与をベンチマークとしている。しかし厳密に合わせているわけでは無く、推奨レベル。
    • ステップと給与の関係は未完成。
  • 肩書(役職?)
    • ステップと肩書は連動しない。

感想

序盤の「The road is more important than the destination」という節にあるのですが、自社のキャリアパス制度を作ろうとしている時に、他社のやり方をそのまま使いたくなるかもしれないが、それはお勧めしない。なぜなら企業文化はそれぞれユニークであるから。とあり、楽はできないんだなと。彼らは評価制度を作るのに有志によるワーキンググループを作ったが、企業文化によってはここから別のルートになる所もあるだろう。
社員の成長をサポートする、つまりどの様に成長して欲しいかを定義するのは企業文化と照しあわせる作業であり、そのプロセス自体も企業文化に即していなければならない。

ステップ(レベル)と役職が連動していないのは、給料を上げるにはマネージャーにするしかない、という残念な状況を生み出さないので理にかなっている。(しかしそんな残念な会社もたまにあると聞く)

Companyステップに期待する事の一つが
Gives talks at industry events, and/or publishes research papers, and/or publishes company white-papers and/or may be a Spotify representative in industry groups or committees.
つまりこういった記事をブログで公開する事、彼ら自身が利用しているソフトウェアをGithubで公開したり研究成果を論文にするのも要求事項として明記されているんですね。素晴しい。

このエントリーをはてなブックマークに追加

2016-09-09

GCP NEXT Tokyoとbq_sushiで弊社事例の紹介をしました

9月6日に開催されたGCP NEXT Tokyoの事例紹介セッション及びパネルディスカッションでの講演機会をいただいたので登壇してきました。一緒に出演されたメルカリ様、DeNA様はApp Engine Goをバリバリに使っている事例で、VOYAGE GROUPはBigQueryと、他社のサービスに無いプロダクトを全面にプッシュしていたのでわかりやすい話になったかなと。反省点は、資料に沿って話すのに精一杯で、まだまだ自分の言葉で話せなかった所ですかね。

そして、この事例で紹介した仕組みで動いている処理の一つが先日発表した不正クリック検出なわけで、GCPのデータセンタには足を向けて寝られません。

そのまま夜はbq_sushi #4で事例紹介の縮小版をやりました。異常検知で利用しているクエリを紹介しようとしたらスライドに貼りきれず失敗したので、Qiitaに全部貼りました……。

bq_sushiで使用した資料

GCPではじめるスモールスタートなデータ活用 // Speaker Deck

ETL処理とlambdaアーキテクチャ

今回のGCP NEXTとbq_sushiで目を引いたのはETL処理とlambdaアーキテクチャ。リアルタイム性と遅れてくるデータの扱いをどうすべきか、最近の悩みでもあったのでヒントになりました。SpotifyのオンプレからGCPへの移行ケースの話も極めて俺得でした。Spotifyといえばジョブパイプラインの制御にluigiを使ってますが、もしかしてluigiのGCPまわりの開発が加速されるのかなと、密かに期待。


このエントリーをはてなブックマークに追加

2016-09-05

不正クリック検出の歴史と実装について発表しました

第56回データマイニング+WEB@東京で不正クリック検出について発表してきました。参加者の三割ぐらいがネット広告業界のエンジニアだったため、釈迦に説法にならないか心配でしたが、配信業態が変われば相対している問題も異なるようで良かったです。

発表資料


個人的にはパブリッシャーのブラックリストを広告業界全体で共有するくらいの事はやっても良いのでは、と思っています。 今は圧倒的に防御側が利用できる情報が少なく不利な状況にあります。(そして自分が楽をしたい)

あとはつい先日、CAリワードから「DNN+オンライン学習で不正検出してます」というプレスが発表されて、どうやっているんだろうと気になってしょうがないのですが、CAの人に会える機会が無くもやもやとしております。

このエントリーをはてなブックマークに追加

2016-08-17

[論文] Combating online fraud attacks in mobile-based advertising (2016) 読んだ

Combating online fraud attacks in mobile-based advertising

要旨: Abstract

広告バナーに対して機械的にクリックを生成するAndroidアプリ(不正クリックbot)を実装して、実際のAdNetwork8社に対してbotによるクリックが有効かどうかを検証した。
検証結果から、不正クリックbot対策の提案を3つする。

実装: Implementation of online fraud attacks

CPC収益モデルの広告に対して、悪意のあるPublisherはクリックイベントを生成する事により自身の利益としている。それらは実にシンプルに生成されているが、実際のAdNetwork各社がそうやって生成されたクリックに対して今だに脆弱であるかは疑問があった。
これを検証するため、次の実装とした。

  • 独立したAndroidアプリとし、表示された広告に対して自動でクリックイベントを生成する
  • Publisher自身の端末でこれを動かすシナリオを想定
  • Android Debug Bridge (ADB) を利用してクリックイベントを端末に送信
  • Device ID (or android_id) がサーバーに送信されるため、これをランダムに書き換える

実験結果: Experiments

6つのAdNetworkは機械的に生成したクリックを防げなかった。2つのAdNetworkは自動生成クリックに対抗し、アカウントがブロックされた。

対抗手段: Countermeasures

1. Androidのアーキテクチャを変更し、物理的なタッチイベントについてトレース可能にする。イベントの生成元がわかれば、プログラムによって生成されたクリックイベントをフィルタする事ができる。
2. 人間には見えないバナーでbotを釣る
3. 異常なふるまいを検知する
----

感想

攻める側の視点とは珍しいなと思って読んでみたが、全く難しい事をしておらず拍子抜け。しかも6つのAdNetworkにはこれが有効という結果。しかしbotの運用期間が書いてなかったので、不正検知に引っかかる前に実験を終えた可能性もある。

AdNetworkによってはAdvertising IDでは無くAndroid IDを端末の識別子として利用しているという点は、2016年にもなってそんな事するか?? と疑問ポイント。使える物は便利に使ってる、というだけかもしれないが。


このエントリーをはてなブックマークに追加

2016-03-06

GCP ja night でCloud DatalabとBigQueryについて発表をしました

「AppEngine ja night」がいつの間にか名前が変わって「GCP ja night」になってました。今回は仕事でどうGCPを使っているかをネタにしました。


他の発表陣が軒並GKEを使ったシステム構成の話をする中で、自分だけGoogle Cloud Datalabでデータ解析チーム内での実験ノート共有手法の話をするという、非常に苦しい場ではありましたが何かの参考にしていただければ幸いです。一つ失敗したのは、Cloud Datalabの話をするのに、Cloud DatalabのベースとなっているJupyterの解説を飛ばしてしまった事ですかね。



このエントリーをはてなブックマークに追加