AtCoderはじめました

AtCoderというか蟻本の輪読会が社内で始まったのでこっそり若者に混じっている。

モチベーション

グラフアルゴリズムの概観とその実装の感覚を叩きこんでおきたいのがある。最近はGraph Embedding等のグラフを用いた手法によく出会うが自分の中に基礎が無いのでなかなか理解できた気にならない。自分のブログを漁ると10年前に最短経路問題をJavaScriptで解いているので、その手の活動を再開したとも言える。

進捗

以下のページを参考に、本の内容に対応するAtCoderの問題を解きつつ

AtCoder 版！蟻本 (初級編)
https://qiita.com/drken/items/e77685614f3c6bf86f44

まずはAtCoder過去問の4つをSubmit

• ARC029A - 高橋君とお肉
• https://arc029.contest.atcoder.jp/submissions/8853102
• ABC022D - 派閥
• https://abc002.contest.atcoder.jp/submissions/8914873
• ATC001A - 深さ優先探索
• https://atcoder.jp/contests/atc001/submissions/8954320
• ARC031B - 埋め立て
• https://atcoder.jp/contests/arc031/submissions/8957196

テストコードが書けないコードは許しがたいのでclassにしてあるが、書いている内に depth_first_search は dfs と書きたくなるし if __name__ == "__main__": のお決まりの一文すら書くのが面倒くさくなってきた。人間は変わってしまうのか。

現状苦痛なのはコードを提出した後にRuntime Errorという結果だけが得られて、その時の入力が何だったかわからない点。仕事なら「ログを仕込んで次回に備えよう」となるがそうはいかない。比較的新しいコンテストは入力がDropboxに置いてあって安心した。

書いたコードを残すGitHubリポジトリ
https://github.com/hagino3000/study-programming-contest-challenge-book
進捗メモ
https://scrapbox.io/tnishibayashi/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF%E7%AC%AC2%E7%89%88

IBIS2019でポスター発表しました

IBISは機械学習の研究会です。今年は11月20〜23日の名古屋開催でした。

第22回情報論的学習理論ワークショップ (IBIS 2019)
http://ibisml.org/ibis2019/

今回はポスター発表にアドネットワークのクリック単価決定方策を持っていきました。プロダクト開発が本業なので外部発表や論文を書く事はメインタスクでは無いのですが、実験の過程で得られた結果など発表できる物は外に出していきたいです。バンディットアルゴリズムのポスター発表も数件あり、オンライン意思決定の方策に詳しい先生方の意見が得られる貴重な機会でもあります。

様子です。

その他講演メモ

• グラフ文法を用いたグラフ生成
• 分子グラフ、例えばH20だと(H⇔O⇔H) を学習したい
• 安定性などの制約を満たすグラフを生成したい
• ハード制約とソフト制約の組みあわせ
• 大学でやったタンパク質の構造解析を思い出しつつ聞いた
• 形式言語で記述してグラフにして学習という流れが面白い
• 回帰による再帰型ニューラルネットワークからの重み付きオートマトンの抽出
• RNNの動作を再現するWeighted Finite Automataを抽出する研究があるとのこと
• 重み付き有限オートマトンに置換すると推論の計算コストが低くてふるまいが明快になるメリットがある
• ネット広告分野だと「RNNでコンバージョン予測モデル作った」という報告は多々あるものの、何をどう学習したかわからないし説明性厳しいでしょと思っていたので興味をそそる内容だった
• しかし重み付き有限オートマトンを知らなかったので後で調べた
• オートマトン理論再考 - J-Stage
• 隣接代数と双対平坦構造を用いた学習
• 難しかったがIBISではよくあること
• Data-Efficient Reinforcement Learning of Mechanical Control Systems
• 強化学習
• 不確実性の予測を使って学習すると上手くいく
• ガウシンアンプロセスだから計算コストすごい高いはずだけど、少ない試行回数の間に学習できてしまえば勝ちっぽい
• ニューラルネットはregressionに向いてないと考えてるとの事
• Problems with CNNs by Hinton先生
• 「CNN is bad」
• CNNは人間の様に学習していないからadversarial examplesの問題がある
• 何が写っているか考慮しない、背景を学習してしまっていたりする
• 心理学的なアプローチ
• 図形を表現する時はスケーリングされるし、共通のメンタルモデルがある
• 三角形や四角形という基本図形の組合せで認識する
• Cupsules (2019)
• Capsules for triangles, and squares 星座っぽい所が検出できる
• 星座生成モデルとか
• 人間が物をどうやって見ているか、という観点を使って学習するといいよという話で面白かった
• サンプリングによるデータ駆動科学
• 根源的な構造はわからなくてもいい、機能を獲得したい
• 工学的なアプローチだなー
• データ駆動科学の立場からみた物質科学と情報科学の接点
• 材料科学 → XXに使える材料が無いか追求する
• 物質科学 → なぜXは透明なのか理屈を追求する
• 初日の有機化学とはがらりと変わって無機科学。グラフでは無く原子の繰り返し構造に
• 繰り返しパターン中の原子の位置を文字列で表現してパターンマッチ
• 機械学習に対するソフトウェア工学の技術動向
• 中の人としてプロダクト開発をしている身からすると契約してPoCやって検収・納品というのを見るとすごい大変に見える
• 機械学習と知財・契約
• 外部ベンダーにプロダクトの一部を開発してもらうとしたらどう落し所をつけるか、みたいな事はしばしば考えるのでとても参考になった
• 完成した成果物を、契約当事者双方がどうのように使えるかを「開発+利用規約」において定めるこのが非常に重要
• 物体ではない(コピー可能)ので権利帰属よりもどう使うか
• 知財権を共有にして、利用条件を決めずに進めるのは危険
• http://ibisml.org/ibis2019/files/2019/12/slide_kakinuma.pdf
• 継続的改善をし続けるための機械学習基盤の課題
• MLflow trackingよさそうだった
• 日本におけるデータサイエンスの現状と今後
• 滋賀大学データサイエンス学部
• 日本に統計学部が無いから作った
• 名前はあれだけど統計学に重点を追いたカリキュラムで自分が入学したい
• データからの価値創造の流れ
• 課題が先にあって必要なデータを収集するのが基本
• データが手元にあってそこから新たな知見をさがすのも有用になりつつある
• 竹村先生が本当にすごい人だった、尊敬する

あとはインターネットの方々が詳細な聴講メモを残してくださったのでありがたく拝見しています。

IBIS2019参加記録 | カイヤン雑記帳
http://chijan.hatenablog.jp/entry/ibis2019

IBIS2019行った | 糞糞糞ネット弁慶
https://repose.hatenadiary.jp/entry/2019/11/27/083823

データ分析系3daysインターンシッププログラムで伝えたかったこと

担当した3daysインターンシッププログラムが無事に終ったので、自分が何を考えていたかをまとめます。いわゆる「機械学習エンジニア」向けのインターンです。

https://voyagegroup.com/internship/adventure/

背景

期間3日でやりたいと打診を受けた時に真っ先に思いついたのはコンペ形式のプログラムでした。しかしKaggleを筆頭に実際のビジネスで発生したデータを使ったEDAおよび機械学習予測モデルの開発ができる機会は今やいくらでもあるため、Kaggleそのままの形式では目新しさに欠ける。さらに実際の開発業務では求めた予測値を使って意思決定を自動化する所までが求められるため、予測器を作って精度を見て終りというのは片手落ちとなってしまう。よって、求めた予測値を利用して意思決定を行なうアプリケーションを実装してビジネス指標が出力として得られる部分までを範囲としました。

内容

ハンズオンチュートリアル形式でアドネットワークの広告配信ロジックの開発およびデータ分析を行ないました。配信ロジックは「広告リクエストに対してどの広告を返すか」と「広告のクリック単価をいくらにするか」を広告リクエストを受けた時に決める処理です。

開発は運営が用意したPython環境で起動しているJupyter Notebook上で行ない、これは参加者それぞれ専用のサーバーで動作しています。用意したPython環境にはアドネットワークシミュレーターがインストールされており、参加者は実装した配信ロジックを即座に実行して結果を確認する事ができます。結果には広告キャンペーン毎の獲得コンバージョン数やメディア毎の収益額が含まれており、任意の加工を行ない可視化する事で動作確認が可能です。

個々のトピックとして次の物を取り上げました

• 両面市場(Two Sided Market)における値付け
• 多腕バンディット方策による累積報酬最大化
• 広告配信ログの分析
• 機械学習によるCVR予測
• 推論処理のアプリケーション組み込み
• フィードバック制御によるリカバリ

収益予測と広告選択ロジックが実装する範囲

出題の意図

講義ノートの所々に仕込んだ練習問題や、全体の流れの意図のネタばらしです。

顧客の問題を解決しよう

アドネットワークというビジネスには広告主とパブリッシャーという2つの顧客グループが存在し、それぞれが何を求めているかという点から配信ロジックに求められる要件を解説しました。この考え方が出来ると「予測できて何が嬉しいのか、ビジネスにどんな貢献をするのか」という視点に常に立ち戻れます。機械学習が好きな人は「予測ができる事」に目が行きがちですが、時間をかけていらない物を作ってしまうリスクを減らす為にも重要な考え方だと感じています。

検証方法を考えよう

実装したロジックが意図通りに動いているか、どの様に確認すべきでしょうか? 実務では自分で考える他ないので同様に体験してもらいました。特に確率的なふるまいをするロジックのリリース後の動作確認は難しく、どのデータを取りどの様な可視化を行なうと自信を持ってバグが無いと言いきれるのか、頭を悩ます点でもあります。

予測誤差を意識しよう

広告キャンペーン毎のコンバージョン率を誤差範囲と共にプロットする課題を用意しました。それぞれサンプルサイズが異なる事から誤差範囲もバラバラ、よって平均値の比較だけでは何も言えません。意思決定には予測誤差を考慮する必要がある点は多腕バンディット方策の活用と探索の話に繋がります。また確率pがゼロに近いため二項分布の正規近似で上手くいかない点もミソです。

予測が外れる事を前提として自動リカバリ手段を用意しよう

予測精度100%というのはまずありえないので、予測を誤った時にどうするかが重要となります。自動リカバリの手法としてフィードバック制御を紹介して、みなさんに実装してもらいました。

コールドスタート問題をなんとかしよう

コンバージョン率予測モデルで新規の広告キャンペーンに対しては未学習となっている状態を見せました。コールドスタート方策の一つとしてパラメータのThompson Sampling (ロジスティック回帰ならベイジアンロジスティック回帰) があり、これはパラメータ推定値の誤差の大きさを行動に反映できます。

単一の指標で評価しない

Kaggleの様に何らかの評価指標に絞ってロジックの性能を評価するのはやめました。プラットフォームを運営するのであれば買い手を優遇したい時期、売り手を優遇したい時期、またプラットフォーマーの粗利額を優先したい時期どれもあります。プラットフォーマーの短期的な利益を削ってプラットフォームの成長を促したり、売り手間の公平性を考慮したりと様々な実装が出て来た方が面白いと考えました。

高速に動作するプログラムを書こう

広告配信ロジックにおける処理は広告リクエスト X に対して配信可能な広告 a ∈ A それぞれについてのクリック率 P(click = 1 | X, a)・コンバージョン率 P(cv = 1 | X, a, click=1)を求める必要があります。ここからアドサーバーにおける推論速度の要件を解説しました。10ミリ秒以内に100回の前処理と推論をしたいという事も普通にあるので、遅いコードはそもそもリリースできません。

しかしこれは説明するまでもなく、遅いコードを書くとシミュレーターの動作がどんどん遅くなっていくため気づけたかと思います。事前に配信候補の数を絞る方策も有効ですが3日間という期間を考慮して省きました。

まとめ

インターンシッププログラムの内容を考えて講義資料を作り、専用システムを開発するのは初めてだったのですが学ぶ所が多くありました。また実務のエッセンスをどう伝えるかはまだまだ改良の余地があるので、次回があれば良くしていきます。

KDD2019本会議の聴講リスト

明日からKDD2019の本会議なので聴講リストを整備した。マーケットデザイン・オンライン広告・バンディットアルゴリズムが中心。

招待講演

• Welfare Maximization in Online Two-sided Marketplaces
• 4 Perspectives in Human-Centered Machine Learning
• Addressing Challenges in Data Science: Scale, Skill Sets and Complexity
• Seven Years of Data Science at Airbnb

口頭発表

• Anomaly Detection for an E-commerce Pricing System
• Two-Sided Fairness for Repeated Matchings in Two-Sided Markets: A Case Study of a Ride-Hailing Platform
• Deep Landscape Forecasting for Real-time Bidding Advertising
• Optimizing Impression Counts for Outdoor Advertising
• Personalized Purchase Prediction of Market Baskets with Wasserstein-Based Sequence Matching
• Scaling Multi-Armed Bandit Algorithms
• Scaling Multinomial Logistic Regression via Hybrid Parallelism
• Reserve Price Failure Rate Prediction with Header Bidding in Display Advertising

ポスター

• 150 successful Machine Learning models: 6 lessons learned at Booking.com
• Adversarial Matching of Dark Net Market Vendor Accounts
• AiAds: Automated and Intelligent Advertising System for Sponsored Search
• Applying Deep Learning To Airbnb Search
• Bid Optimization by Multivariable Control in Display Advertising
• Dynamic Pricing for Airline Ancillaries with Customer Context
• Finding Users Who Act Alike: Transfer Learning for Expanding Advertiser Audiences
• Online Purchase Prediction via Multi-Scale Modeling of Behavior Dynamics
• Recurrent Neural Networks for Stochastic Control in Real-Time Bidding
• Reinforcement Learning to Optimize Long-term User Engagement in Recommender Systems
• Predicting Different Types of Conversions with Multi-Task Learning in Online Advertising
• Conversion Prediction Using Multi-task Conditional Attention Networks to Support the Creation of Effective Ad Creatives
• TV Advertisement Scheduling by Learning Expert Intentions
• A Unified Framework for Marketing Budget Allocation

「WTF経済 ―絶望または驚異の未来と我々の選択」感想

ティム・オライリーの視点でここ数年のテック業界でどのような変化が起きているか纏めてあり、トピックは多岐に渡る。その中でも下記の2点は広告業界のソフトウェアエンジニアとして思いをめぐらす所があった。

WTF経済 ―絶望または驚異の未来と我々の選択
オライリー・ジャパン
Tim O'Reilly (著), 山形 浩生 (翻訳)
O'reilly,  Amazon
原著: WTF: What's The Future and Why It's Up To Us

アルゴリズムの管理者としてどうあるべきか

本書の前半はUber, Lift, Google検索を例に価値創造の場におけるアルゴリズムの重要性を説いている。そしてプログラマーは管理職でありプログラムが労働者であると。Googleの検索品質改善の例では、利用者の求めていない低品質なサイトが検索結果の一番上に表示される状況をどう改善したかの紹介がある。すぐに思いつく手段の一つはルールを追加して低品質なサイトを検索結果から除外しまう事だが、彼らはユーザーが検索結果をクリックした後の遷移先の滞在時間をスコアとして利用し、スコアの低い検索結果を除外した。
ルールベースのアルゴリズムは理解が容易で、何かまずい事が起きた時の暫定対応としてプロダクションに投入しがちである。しかしユーザーのフィードバックを利用した方が汎化性能が高くロバストなソリューションになる事はランキングやリコメンド開発者として頭に留めておきたい。

またFacebookにおける見出し詐欺、実際の記事の内容とは異なる刺激的なタイトルを使って利用者を釣っている記事への対応のくだり。

グーグルは、その検索アルゴリズムの厳密な細部は公開しない。ランキングを上げようとする連中に悪用されるのを恐れるからだ。同様に、フェイスブックが見出し詐欺の記事を取り締まったとき、ニュースフィードの製品管理担当副社長アダム・モセリはこう書いた。「フェイスブックは見出し詐欺を定義する複数ページにわたるガイドラインを公開したりはしません。というのもその大部分は実際にスパムであり、もし我々がずばり何をどのようにしているか明らかにすれば、リバースエンジニアリングされて、それを回避する方法を見つけられてしまうからです」

ネット広告における不正対策に繋がる部分であるが、どの様なふるまいを不正とみなすかは公開する事はやはりできない。利用規約にどこまで詳細に記すか、問いあわせにどこまで答えるかの議論が度々発生するが堂々と非公開にして良いのだ。

インターネット広告がネットメディアに与える影響

ネットメディアが主に収益源とする広告収益のもたらす影響について。

検索エンジンやソーシャルメディアで関心を集める必要性は、ニュースメディアの低劣化、偉大な出版物ですらのお手盛り、インチキな論争など、トラフィックを増やす各種技法への堕落をもたらしている。どん底への競争の一部は、ニュース産業の収入が購読料から広告収入に大きくシフトした結果である。

辛辣な表現だが事実として受け止めるべきだろう。Webサイトの価値としてPV数と広告のクリック率が通貨さながらの扱いを受けているのは違和感を禁じえない。しかしインターネット広告がある事でそのようなインセンティブを与えてしまっているのだ。今日たまたま学会で聴いた話で、マイクロソフトの検索エンジンの開発者は「ユーザーが得られた情報の量を操作数で割った物」を指標にしているとの事だった。

https://sites.google.com/view/kdd2019-exp-evaluation/ より

Information Gainの計測はクリックの様な明示的なフィードバックの集計だけで済まないためコストはかかる*1が、情報検索を役目とするサービスの指標として秀逸さに感銘を受けた。広告業界もネットメディアがこのような指標に集中できるような仕組みを目指すタイミングであると思う。そのためにはメカニズムデザインや因果推論が重要な役割を果たすのではと考えている。

*1: 検索結果のリストを見て満足してサイトを去るケースがあるため