ゆるふわめも

東京か京都にいます。

Hyperoptなどのハイパーパラメータチューニングとその関連手法についてのメモ

ねむい。SMACとTPEが概要しかつかめていないので次はここを調べよう。

追記:jsaiにて発表があるのを見つけました、行けばよかった…自分で断っといといてあれだけど…

jsai2017:3Q1-7in1 サンプリングを用いた機械学習パイプライン探索手法

データ全てを使って訓練・評価を行うのは時間がかかるため、サンプリングして交差検証の時間を短縮している。参考文献にはないけれども以下のものと同じ考えなように思う、初めは少ないデータで精度が高そうなモデルの選択肢を減らして、厳密に評価していく時にデータ数を増やしていく。

[1601.00024] Selecting Near-Optimal Learners via Incremental Data Allocation

ハイパーパラメータの定義

データセットとモデルが与えられた時に、 モデルが求めるパラメータ以外のあらかじめ決める必要があるパラメータ。

例:Random Forest における n_estimators など

予測モデルを作成するに当たって、新しいデータに対してより評価手法の値を良くするようにハイパーパラメータを定めたい。以下では最大化するほど良い評価手法が与えられた時に、その値を向上させることを「精度向上」とか「性能向上」と書いています。

探索手法

このような予測モデルのアルゴリズムの選択・ハイパーパラメータの探索手法には、異なるデータセットでの実験結果を用いるものと用いないものがある。今回は「用いない」ものについて。

ランダム、全ての選択に対して一様に確率を割り当てて選択する。

Manual coordinate descend

普段行うように、いくつか変更するパラメータの集合を人力で選択して少しずつ精度を改善させてゆく。

ハイパーパラメータを幾つかの離散的な値に分けてしらみつぶしに探す。これをもっともよかったパラメータの組み合わせに対して再帰的に行う。一般的だが、探索空間が広いと適用は難しい。

Particle Swarm Optimization

粒子群最適化とも。連続最適化、組み合わせ最適化両方に適用可能。並列的な探索を行うが、各探索は「どれくらい精度を改善したか」を速度として持つ。 もっとも精度が改善した探索とその探索の際のパラメータの情報を、付近を探索していた探索に伝搬させる。上記ステップを繰り返す。

Genetic Algorithm

Randal S. Olson, Ryan J. Urbanowicz, Peter C. Andrews, Nicole A. Lavender, La Creis Kidd, and Jason H. Moore (2016). Automating biomedical data science through tree-based pipeline optimization. Applications of Evolutionary Computation, pages 123-137.

論文:[1601.07925] Automating biomedical data science through tree-based pipeline optimization

予測モデルのパイプラインを遺伝的アルゴリズムで最適化する。以下のTPOTではこれを用いているらしいけれど、コードの詳細を見れていない。アルゴリズムの探索にXGBoostが含まれているので、一旦これを取り除いて既存手法と同じ設定での比較をしたいところ。また、比較手法がRandomForestのみ?なぜだろう。

Sequential Model-Based Optimization(SMBO)

Particle Swarm Optimizationでは「どれくらい改善したか」の情報を速度として持っていたけれど、SMBOの枠組みでもこれに近いExpected Improvement(EI)を求める。あるハイパーパラメータの選択をした時の精度向上の期待値。FLASHなど最近の手法は時間当たりのEIであるExpected Improvement Per Second[2]を計算する。

各手法の評価については以下を参照。

pdf:Towards an Empirical Foundation for Assessing Bayesian Optimization of Hyperparameters

Tree-structured Parzen Estimator(TPE)

Bergstra, James, Daniel Yamins, and David Cox. “Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures.” Proceedings of The 30th International Conference on Machine Learning. 2013.

ドキュメント:Tree-structured Parzen Estimator — Optunity 1.1.0 documentation

HyperOptにて使われている手法。後ほど詳細を追記したい。

Sequential Model-Based-optimization for general Algorithm Configuration(SMAC)

Hutter, F. and Hoos, H. H. and Leyton-Brown, K. Sequential Model-Based Optimization for General Algorithm Configuration In: Proceedings of the conference on Learning and Intelligent OptimizatioN (LION 5)

論文:Sequential Model-Based Optimization for General Algorithm Configuration (extended version)

Random Forestを用いて逐次的に最適化を行う。 FLASHなどの多くの実験では SMAC がベースラインとなっているが、[1]にてランダムな探索を使った時と比べあまり精度向上はないとも指摘されている。

Fast LineAr SearcH(FLASH)

Zhang, Yuyu, et al. “FLASH: fast Bayesian optimization for data analytic pipelines.” arXiv preprint arXiv:1602.06468 (2016).

予測アルゴリズムの選択とそのハイパーパラメータの選択を同時に最適化するが、そのまま予測のパイプラインをブラックボックス関数とみなして最適化するには探索空間が大きすぎる。そのため、二段階のベイズ最適化を行い、アルゴリズムの選択+ハイパーパラメータチューニングを行う。各ステップで加わる誤差を線形にモデル化して、性能が高いパイプラインを選択する。高速化のためのキャッシュなども実装。

参考文献

[1] Li, Lisha, et al. “Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization.” arXiv preprint arXiv:1603.06560 (2016).

[2] J. Snoek, H. Larochelle, and R. P. Adams. Practical bayesian optimization of machine learning algorithms. In NIPS, 2012.

強化学習関係のMOOCs(オンライン講座)のメモ

CS294をいつか見たいけれども、朝になった。 次はTree-structured Parzen Estimatorとかを調べる予定。

CS 598 LAZ: Cutting-Edge Trends in Deep Learning and Recognition

講義ページ:CS 598 LAZ

最近の deep 系の主な話題を順番にふれていく講義。強化学習も途中に一回。Feature pyramid networksとか 2016/12 以降の完全に追いきれていないテーマの説明がスライドにあるので、概要を把握するのに非常に助かる。扱うトピックは本サイトの「topic list」より閲覧できる。Adamに対するEveもちゃんと載っている。

f:id:misos:20170607015433p:plain 

上はObject Detection, (Sihao Liang Jiajun Lu Kevin Perkins)の講義資料からの一ページを引用。詳細は引用元であるCS 598 LAZ の「Object detection (Jiajun, Sihao, Kevin)」より閲覧してください

CS 294: Deep Reinforcement Learning, Spring 2017

本ページ:CS 294 Deep Reinforcement Learning, Spring 2017

講義動画一覧:CS294-112 1/18/17 - YouTube

有名どころなので subreddit もあった。多分ぶつかりがちな問題や質問は subreddit にも投稿されていると思う。

宿題や問題への回答はないけれども、 github にたくさん上がっているのでそれらを参考にしながら解きたい。

UCL Course on RL

ユニバーシティ・カレッジ・ロンドンの強化学習の講義資料。

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

Sutton本

論文メモ:Learning Hidden Features for Contextual Bandits

バンディット系のメモです。かなり適当です、すいません。

元論文

Learning Hidden Features for Contextual Bandits

Wang, Huazheng, Qingyun Wu, and Hongning Wang. “Learning Hidden Features for Contextual Bandits.” Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 2016.

実装の(一部は)以下にあります。

github.com

まとめると

  • 普通のContextual Banditでは利用可能なデータを全て特徴量として扱う
  • 実際にはデータ全てを用いることは計算量的にも望ましくないし、必要なデータを特徴ベクトルとして全て観測できる設定は現実に即していない
  • そのため、潜在的な特徴をユーザとアイテムに追加して観測できなかった特徴をモデル化
  • regretの上限を証明して、また coodinate descent は一部のパラメータだけを参照してデータを更新するので計算速度も比較的はやい
  • 性質上、スパースなデータでは精度向上の幅は小さい

背景

Contextual Bandit

Contextual Banditとはバンディット問題における探索と活用のトレードオフを補助的な情報(つまり、ユーザーやアームに関する特徴量)を用いて最適にしてゆく問題設定。通常はアクセスできる特徴全てを利用して報酬( もしくは損失 )をモデル化する。

推薦システムのところで既出。

paper.hatenadiary.jp

既存手法の問題点

このようなContextual Banditで利用可能な情報全てを用いて計算を行うのは現実的ではない。ニュースのレコメンド例を用いて考えてみると、全ての情報を使いたくないので例えば「ニュースのカテゴリ」、「ニュースの発生場所」を特徴としてContextual Banditを行う。このような時、例えば「ニュースの発信源」でニュースをみるか決めている人についてはいつまでたっても正しいレコメンドはできない。つまり、一部の人にだけ特化した推薦システムができてしまう。しかし、利用可能な情報全てを初めから用いた推薦システムの構築は難しく、プライバシーの問題などから当初は利用できない特徴もある時がある。なので、そのような利用できない特徴もモデル化できるContextual Banditのアルゴリズムが欲しい。

Latent Factor Model

おそらく理解に必要なので。

www.slideshare.net

座標降下(Coordinate Descent)法

いつか張った気がしますが、再掲。

www.slideshare.net

問題設定

入力は、 - アームの集合A - アームを引く回数T - 各アームの特徴ベクトルX - ユーザーの集合U

出力は、 - 時刻tにアームaとユーザーuを選択した時の regret の時系列

最終的な目的関数は - オラクル(ベストな選択肢)を常に選択する場合と比較して regret を最小にすること

注意として、入力には含めてないけれどもモデル化する潜在的な特徴量の次元数をあらかじめ定めておく必要あり。

アルゴリズム

f:id:misos:20170602024752p:plain

時刻tにおけるユーザーuに対してアームaを選択した時のregretは、アームの特徴(context)とユーザーの嗜好(θ_u)とガウスノイズを使って上のように記述できる。

けれども応用先によっては、アームの特徴に関する情報全てに常にアクセスできるとは限らない。つまり、上の式でのxに手元にあるデータ全てを与えるのは現実的ではない。なので観測できない特徴ベクトルとそれに対応するバンディットのパラメータを導入すると regret は

f:id:misos:20170602030753p:plain

とかける。 今、アームに新しく潜在特徴ベクトルをつけたのでユーザーの特徴ベクトルにもそれに対応する潜在ベクトルを追加する。あとはこの追加した潜在ベクトルに対応するパラメータを coordinate descent にて求める。

f:id:misos:20170602174451p:plain

この時、回帰にて最適化する式は (報酬の推定値と実際に観測した値の二乗誤差)と(ユーザーの特徴ベクトルに対する正則化項)と(アイテムの潜在ベクトルに対する正則化項)を追加したもの。この式に対して、regretのバウンドが証明されている。 新たに考量する潜在的な特徴ベクトル v 関係する項をなくせば、確かに普通の contextual bandit の式の形になる。

実験

ベースライン

  • LinUCB
  • hybrid-LinUCB
  • PTS
  • UCB-PMF
  • ALS ε-greedy

hybrid-LinUCBについてはユーザー情報がないデータセットでの実験の場合、省いていることに注意。

実験結果

データセットの説明などは論文を参照。ベースライン手法と比較して、データがスパースではない(つまりユーザー一人当たりのサンプル数が少なくない)場合ほどLinUCB(Yahooのニュース記事のレコメンドに関するcontextual banditの手法、有名)に差をつけて勝利する。

一部のデータセットで精度向上の幅が少なくなるけれども、それはデータがスパースなもの。そもそもcoordinate descentはスパースなデータに対してあまり有効な手法ではないと自分は考えているので、納得できる実験結果だったように思う。

課題

潜在ベクトルの次元数が固定、あらかじめ決める必要があるので最適な次元数を求める方法を考えたいなど。

論文メモ:The Limits of Popularity-Based Recommendations, and the Role of Social Ties

“The Limits of Popularity-Based Recommendations, and the Role of Social Ties.”[1] について. mathjaxで書くと時間かかるので数式は論文を要参照.

冷静に考えると最近アニメや漫画にかけている時間が少なすぎる気がしてきました.

まとめると

  • SNSのつながりを利用した推薦システムの数理モデルを作って解析したい
  • 既存研究では「影響力の高いユーザー(有名人など)」の推薦や友人の影響でユーザーの購入が変化することが指摘されていた
  • 推薦システムによってユーザーにコンテンツを推薦して購入する商品を変化させたいが
  • SNSのようなつながりはこの購入する商品の変化を妨げることが数理モデルで示唆された

モデル

推薦システムが利用されている市場と利用されていない市場のモデルを作る

推薦システムが利用されていない市場のモデル

  • f: コンテンツを購入する確率(市場の中で時刻tに商品を購入することを決定するパラメータ)をユーザーごとに持つ
  • b: ユーザー個人の嗜好で, 時刻tでコンテンツを購入すると決まった時に購入する商品の分布に影響を与えるパラメータ

推薦システムが利用されている市場のモデル

上記に加えて

  • 時刻t以前に購入した商品の履歴
  • α: ユーザーが推薦にしたがって商品を購入するかを決定するパラメータ
  • w(v, u): ユーザーv, u の間の信頼関係であり, 友人の購入に影響されてコンテンツを購入する状態をモデル化するために必要

突然「時刻t以前」と書きましたが, t=1より前の購入履歴はあらかじめ与えられている. 初期のユーザーの嗜好bの分布は幾つかの分布で実験を行う.

Market distortion

推薦システムが存在しない場合, ユーザーは何らかの事前分布に基づいて適当にコンテンツを購入する. 推薦システムによってこの事前分布がどれくらい変化して購入するコンテンツが変化するかの指標がMarket distortion. [1]中の(5)に定義.

実験

利用データ

Amazon, Yelp, TripAdvisor, SoundCloud, Last.fmの友人のつながりのグラフデータを使う. そこに上でモデル化した商品購入・レコメンデーションのモデルを適用する. そのため, データそのものには商品購入のデータは含まれていないことに注意. 以下のStanford Large Network Dataset Collectionなどからこのようなグラフ構造のデータを入手できる. Yelpは別ページにて.

super-node

全てのユーザーに常に同一の商品を推薦する. テレビコマーシャルなどをモデル化するためのもの.

結果

有名人などの影響力のあるユーザーが存在しても, t→無限大とすればMarket distortionは収束してしまう. つまり推薦システムを利用しても市場の変化はほとんどない状態で, SNSによるつながりが推薦システムによる市場の変化を妨害していることが示唆される.

一方でsuper-nodeがある場合はデータによってMarket distortionが異なる. これはテレビコマーシャルなど大量のユーザーへのコンテンツの訴求が市場に影響を与えることを示唆している.

感想など

論文ではsuper-nodeは全員に推薦をしていたが, 実際にはテレビコマーシャルなどは全員が見るわけではない. 全体の数割にのみ影響を与えて, その友人にはさらに半分の影響を与えて…といったように拡散カーネルで伝搬していく感じなのだろうか(適当).

行動の変化/分析対象 ユーザーの行動によって 周辺の環境が変化しない ユーザーの行動によって 周辺の環境が変化する
モデルの出力の確率分布がわからない 多腕バンディット 強化学習
モデルの出力の確率分布が決まっている 決定理論 マルコフ決定過程

の分類で理解をしているけれど, 今回のモデルは右下に該当するものだと思う. 推薦システムの文脈では多腕バンディットもよく出てくる. 下にメモがあったような.

コード

論文著者のコードは以下.

https://github.com/Steven–/recommender

参考文献など

[1] Bres Marco, et al. “The Limits of Popularity-Based Recommendations, and the Role of Social Ties.” arXiv preprint arXiv:1607.04263 (2016)

推薦システムに関する資料集とメモ

  • 推薦システム
    • 定義
    • 評価指標
    • 講義・解説スライドなど
  • 推薦システムの分類
    • 個人化による分類
    • アルゴリズムにて用いるデータによる分類
    • アルゴリズムによる分類
      • 類似度
      • 行列分解
      • ベイズ推定
      • バンディット
      • Deep Learning
      • xxx2vec
  • Web上における推薦システム
    • データの前処理
    • ユーザーの行動パターンの発見
  • 時間情報を考慮した推薦
  • 参考文献

個人用のメモです, 推薦システムを勉強したことがなかったので, おさらい. 後で目次含め中身丸ごと書き換え予定.

推薦システム

定義

以下に挙げることを行ってくれるようなシステム. 一言でいうと, ユーザの興味に合わせておすすめのコンテンツを勧める・お勧めでないコンテンツを除外するシステム.

  • 推薦:ユーザーの目的に合致するコンテンツを幾つか選択して提示する
  • 予測:コンテンツへのユーザーの評価を予測する
  • フィルタリング:ユーザーにとって迷惑なコンテンツ(スパムなど)を選択して除外する

評価指標

  • 精度
  • 適合率・再現率
  • セレンディピティ
  • ユーザーへのアンケート評価
  • 顧客生涯価値[5]

どの評価指標が適切かは、後に書く推薦システムの分類(運用目的での手法の分類など)でどの種類になるかによって変わってくる. なので「精度が高かったからok!」と言えるかどうかはシステムの目的に応じて判断しないといけない.

講義・解説スライドなど

続きを読む