2015-07-05

Thompson Samplingの実験的な評価

Thompson Samplingの実戦投入の参考になりそうなので次の論文を精読した。
内容はアルゴリズムの紹介、パラメータチューニングとそれによる損失の変化の実験結果、オンライン広告とリコメンドエンジンへの適用例など。以降、Thompson SamplingはTSと表記。

UCBとの比較

実験ではどのパターンも、途中まではUCBと同じ損失だが試行回数がある程度増えた所でTSの損失がUCBを下回っている。腕の数が多い程、報酬の差が小さい程UCBとパフォーマンスが分かれる点は後ろにずれる。
理由は書いてないが、UCBは一旦報酬が低い事がわかった腕も定期的に引くのでこういう結果になるのだろう。TSは報酬の期待値が収束した後は良い物しか引かない。

事後確率の調節

ベータ分布のパラメータaとbについてそれぞれα∈(2, 1, 0.5, 0.25) で割った値にした実験。0.25にすると傾向として損失は下がるが、損失が増える駄目なケースも増える。腕の性能評価を早めるので、誤って評価してしまうのだろう。バリアンスが高くなるので玄人向けのチューニングに見える。

報酬のフィードバック遅延に対するロバスト性

腕を引いて即時に報酬が観測できない事はシステムの制約上良くあるよね、という前段に続いて報酬のフィードバックが遅れた場合の実験結果が載っている。1000ステップ遅れた場合にUCBの損失は10倍近くなるのに対して、TSは6倍程度。TSの方が性能良いという結果。

オンライン広告におけるCTR予測との組みあわせ

Contextual Banditな話。CTRの事後確率をベータ分布では無く、ロジスティック回帰で平均を求め、ラプラス近似でガウス分布にした物を利用する。PRMLでラプラス近似を見た時は何に使うのか理解できなかったが、なるほど納得。

この論文に書いてない事

腕の報酬が変化するパターンの実験はしていない。広告配信では腕の性能が変化する事は考慮しなければならないので気になる所。報酬の変化を捉えるにはUCBの様に一旦低く評価された腕を再度引くしかけが必要になるので、期待報酬の分散を増やすか利用する観測値は直近の物に限定する、といった工夫が必要だろう。

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

2015-06-26

ISAC TokyoでGPS/GNSS高精度測位の世界を垣間みた

今年のInternational Space Apps Challenge、グローバル審査の結果まで出たので顛末を書きます。結果は東京ローカル審査で優秀賞を頂いて、グローバル審査に進んだものの敗退といった所です。

International Space Apps Challenge(ISAC)とは

今年で4回目となるNASA主催の国際ハッカソンで、今年は世界133ヶ所で行なわれた模様。地球観測衛星から得られたデータを有効活用したり、世界規模の問題解決に取り組むといったテーマが与えられた中でチームを作りハードウェアやWebサービスの開発に取り組みます。

何を作ったか

SENSOR YOURSELF テーマを選び、屋外用の安価な高精度測位モジュールを作りました。モチベーションとしては既存の機器、例えば農機や建設機器のオプションとして売られている物があまりに高いため、高精度測位の普及が進んでいない。安価に実現可能な事と利用法を示せれば、廉価品を作るメーカーが出てきたりスマホだけで利用可能になって嬉しいのでは、という話です。農機になぜ高精度測位が必要かと言うと、例えば植えた稲を踏まないように自動運転させるためだそうで。

作りとしてはRaspberry Pi + GPS/GNSS受信機 + ケースです。ネットワーク必須なので、そこはテザリングで。スマホ内蔵の受信機の信号が直接使えるようになればラズパイも受信機も不要なのですが、iOSはCore Location経由でしか位置情報にアクセスできないので不可能なのと、Androidでも特定の機種に限られるのでこの形に。測位モジュールを作るだけでなく、有効なユースケースを提示する予定だったのですがハッカソン中に良い案が思いつかず。

これでどの程度の精度が出るかと言うと、単独測位の誤差が10メートル程度なのに対して誤差1 ~ 10cm程度です。デモページで取得したデータをプロットしているのですが、1cm程度に収まっています。ただ、これは建物の屋上の受信機で測定したデータなので(Height 117m)地上でやるよりも精度が出ています。
デモのスクリーンショット

READMEに載せた構成図
 +------------------+          +--------------------------------------+                            
 | Smartphone       |          | RaspberryPi                          |                            
 | +--------------+ | Location |  +------------+       +-----------+  |           +-----------------+
 | |   Browser    <----(HTTP)-----+ API Server <-(TCP)-+  RTKLIB   <----(Serial)--+ GNSS/GPS Device |
 | +------^-------+ |          |  +------------+       +-----^-----+  |           +-----------------+
 +--------|---------+          +-----------------------------|--------+                            
          |                                                  |                                     
          |                                               (NTRIP)                                     
          |                                                  |                                     
 +--------+---------+                               +--------+---------+                           
 | Web Server       |                               |  Base Station    |                           
 | HTML, JavaScript |                               |                  |                           
 +------------------+                               +------------------+                           
 Serve User Interface
Submitしたプロジェクトページ

最近はGPSでは無くGNSSと呼ぶらしい

今回のハッカソンで勉強になったのがGPS周りの技術。基本的な所ではGPSは米軍の衛星測位システムを指すが、ロシアのGLONASSやEUが稼動準備中のGalileoと利用可能な衛星測位システムは複数存在するため、今はGPSでは無く総称のGNSS(Global Navigation Satellite System)を使うのが時流らしい。といっても文献ではGPS/GNSSと併記しているパターンが一番多かったので、この記事でも併記にしました。

単独測位と高精度測位

スマートフォンでWi-Fiを切った状態での位置情報の正確さ、地図上で小さな通りだと一本ずれてしまう事は良くあります。受信機単体測位による精度は良くて10メートルとされているので、普段の感覚通りですね。この時、4つ以上の衛星との距離を元に3次元空間上の位置を計算しています。距離は信号伝播時間と光速度の積で求まります。3点からの距離さえわかれば位置は計算できるはずですが、受信機の時計補正のために4台目の衛星を必要としています。

この精度を上げる方法がいくつかあり、DGPSだとメートル単位、RTKだとセンチメートル単位での測位が可能になります。
  • DGPS (Differential GPS) 
  • PPP (Precise Point Positioning) 
  • RTK (Real Time Kinematic GPS)
今回のハッカソンでは海洋大のRTK基準局が使えるとの事で、RTKにしました。ただ、RTKの基準局の有効範囲は15km程度なので、基準局がどこにでもある時代にならないとこの方式は普及しないのでは、とも思ったり。
出展: RTK-GPSの原理と応用

渋谷とIngressとマルチパス

これらの高精度測位が使えれば、常に数十メートルのドリフト(位置のずれ)によって苦戦を強いられている渋谷IngressエージェントもUltra Strikeが有効活用できそうですが、ビルの谷間では上手くいきません。前述の高精度測位手法は、誤差を発生させる要因の1つである反射波(マルチパス)をケアしないからです。ハッカソン会場は秋葉原だったのですが、地上においてRTK方式では一度も位置がFixしませんでした。RTK方式が利用できるのは、空が開けた場所に限定される様です。

ハッカソン参加で得られた物

1年目は二行軌道要素(TLE)について知り、2年目は太陽光パネルの発電量計算モデルと電力買い取りサービス、Modis(地球観測システム)のデータとGIS。今年はGPS/GNSS。普段の仕事では組まない人とプロジェクトをやると新しい知見が得られて面白い。あと、気になってるけど触った事のないライブラリを試すのに良くて、今年はRxJSを投入。毎年何らかの学びがあるので楽しみにしています。

状況です。

関連プロジェクト

どちらも専用ハードで小型化を実現していて凄い。海外だとRTK基準局がそこら中にあるのか、もしくは基準局を自分で立てて運用できるGPSおじさん向けのプロダクトかもしれない。

参考文献

坂井 丈泰: GPS/GNSSの基礎知識
土井下健治, 村本英一, 神田俊彦: 建設機械への ICT 応用
浪江 宏宗: RTK-GPSの原理と応用
安田 明生 et al, 東京湾仮想RTK基準局ネットワーク

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

2015-06-12

弱くてニューゲームしてアドテクエンジニアになりました

近況。2015年からアドネットワークのデータサイエンスチームにおります。前の部署ではメディア寄りの所でモバイルアプリの開発をしていたので、ほぼ転職に近い状態です。アドネットワークなにそれという方向けの説明としては、広告主と広告枠をまとめていい感じにディスプレイ広告を配信するシステムだと思ってもらえれば。

現在のミッション

データ分析や広告配信アルゴリズムの改良というアプローチでアドネットワークの収益改善に取り組むのがミッションです。会社ブログにMortal Multi-Armed Banditsの記事を書いた頃は多腕バンディットアルゴリズムの調査や実装をしていました。

データサイエンスといっても、いきなり機械学習を使った仕組みをプロダクションに投入できるかというと全くそんな事は無く、ログの収集と解析基盤を構築する所からでした。まっさらなAWSアカウントでCloudFormationテンプレートを書いて、VPCやサブネットを切っていたのが2月頃。その間に並行して勉強も進めました。

弱くてニューゲーム

データ解析系の業務に興味はあったものの、経験は無く実力としては新卒以下。2011年に画像認識の論文で機械学習を知り、興味本位で勉強会に参加してみたもののPRML(後述)はニューラルネットが理解できず挫折し、Andrew Ng先生のオンラインコースは課題提出が間にあわず途中で落第する始末。それから3年経って仕事になるとは、どう転ぶかわからない物です。

解析系スキルとドメイン知識は1から修得しないといけない一方、新しいデータを得るために広告表示のJavaScriptコードに機能を追加したり、Scalaで動いてる配信サーバーにも手を入れたりします。このあたりは人に頼まなくても自分でやれてしまうので楽。広告表示のJavaScriptは流行りのライブラリなど一切使わないので、ECMAScript標準とDOMをおさえておけば書ける、元DOM職人としては血が騒ぎますね。

面白い所

扱うデータの量が今まで(そこまでヒットしていないサービス開発)とは桁が違う。マルチコアを使い切る、かつサーバーを横に並べればスケールするプログラムを書き、c4.8xlarge複数台並べてログの処理をするのは爽快。しかしそれも最初だけなので、新鮮な気持は忘れないでおきたいですね。

あとは論文が読める点。アドテク業界はプレイヤー同士がeCPMを高めるために金と計算機とアルゴリズムで殴り合いをしている様な物ですが、論文という形で成果が発表されるので、読みまくれば勉強になる。読むだけなのも何なので数年以内には書いてみたい。

読ん(だ|でいる)本をいくつか

ザ・アドテクノロジー~データマーケティングの基礎からアトリビューションの概念までザ・アドテクノロジー~データマーケティングの基礎からアトリビューションの概念まで
菅原健一,有園雄一,岡田吉弘,杉原剛
翔泳社
Amazonで詳しく見る by AZlink
アドテクノロジー プロフェッショナル養成読本~デジタルマーケティング時代の広告効果を最適化! Software Design Plusアドテクノロジー プロフェッショナル養成読本~デジタルマーケティング時代の広告効果を最適化! Software Design Plus
養成読本編集部
技術評論社
Amazonで詳しく見る by AZlink
どちらもネット広告の進化の歴史と要素技術をざっと見わたせる。THE AD TECHNOLOGYは広告全体におけるオンライン広告の位置づけ、マス広告・オフライン広告との関連にページが割かれているので広告業界初心者には良い。

プロフェッショナル養成読本シリーズは、どちらかと言えばマーケッター向けの内容だった。表紙がスーツマンなのはそういう事か。クロスデバイスターゲティング等のスマホ回りの仕掛けは載っていないので、スマートフォン向けの広告をやっている人は物足りないかも。

パターン認識と機械学習 上パターン認識と機械学習 上
C.M. ビショップ,元田 浩,栗田 多喜夫,樋口 知之,松本 裕治,村田 昇
丸善出版
Amazonで詳しく見る by AZlink
基礎を身につけるための定番の1冊。3年前は挫折したものの、今回はそうも言ってられない。とにかく数式をコードに落としてしまえば、動作もするし容易に理解できるのでなるべく手を動かす事にしている。最近だとQiitaに投稿したベイズ線形回帰によるパラメータ分布の収束がそれ。毎週の社内勉強会で読み進めているので2年もすれば下巻まで終りそう。これのおかげか、論文に書いてある事が理解できない事案が減りました。

データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (確率と情報の科学)データ解析のための統計モデリング入門――一般化線形モデル・階層ベイズモデル・MCMC (確率と情報の科学)
久保 拓弥
岩波書店
Amazonで詳しく見る by AZlink
PRMLはガウス分布が多めですが、こちらは何でもかんでもガウスで当てはめが上手く行く訳がない、という主張。ポワソン分布, 二項分布, ガンマ分布, etc. といった確率分布と適用例を紹介し、いかにデータの特徴をとらえた確率分布・モデルを選ぶかという事に主眼がおかれている。機械的に素性選択をする手法ばかり見た後に読んだので、自分にとってはカウンターカルチャー的な存在。

深層学習 (機械学習プロフェッショナルシリーズ)深層学習 (機械学習プロフェッショナルシリーズ)
岡谷 貴之
Amazonで詳しく見る by AZlink
次の輪読会でいきなり発表担当。既に背水の陣。

UDEMY ベイズ推定とグラフィカルモデル:コンピュータビジョン基礎1
こちらは進捗51%。Computer Vision向けの内容だがとにかくわかりやすい。PRMLで詰まったら立ち戻るのに良い。

まとめ

レベル0から出直しといいつつも、稼いでなんぼのエンジニア。事業にコミットしつつ、先生きのこるための鍛錬に励みます。

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

2015-05-16

データ分析コンペについてLTをした

Powerd by enjo-generator
といった内容でした。

まだまだ修行あるのみ。週末はkddcup2015に向けて助走を開始します。


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

2015-05-10

Google Cloud StorageとBigQueryで困ったら、まずはStack Overflowに書くと良さげ

GCPでサポートパッケージを購入していない人向けの話。

困ったらどうするか

GCPのサポートページを見ると、課金しないで利用できるのはドキュメントとコミュニティフォーラムとある。コミュニティフォーラムとしてGoogleグループとStack Overflowへのリンクが載っている、がGoogleグループはStack Overflowへ移行したとあり、現状機能はしていない。さらにBigQueryについてはGoogle Codeにissue trackerがある。

まとめると窓口は

Stack Overflowが一番反応が早い

自分が投稿した質問
こういう質問を投稿すると数日で「まだ現象が再現するならメール頂戴」みたいなレスが付く。他の質問を見ても、解答もしくはなんらなかのコメントが付いている。

Stack Overflowよりも先にGoolge Codeの方にも投稿したがこちらは3週間経っても反応が無い。よって、まずはStack Overflowに投稿するのが良いだろう。Stack Overflowは日本語版も出ているが、GCPについてのやりとりは活発では無い様子。

まとめ

Stack Overflowで解決しなかったら金での解決(サポートパッケージ購入)を検討しよう。

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