北海道大学大学院情報科学研究科

オンライン学習

オンライン学習とは、予測や選択を繰り返し行い、累積利益を最大化することを目的とする学習です。例えば2つの株AとBがあり、100万円をそれらに1ヶ月間投資して、持ち株の時価総額を最も増やしたプレイヤーが勝ちというゲームを考えましょう。株価は毎日変動し、持ち株の時価総額は毎日変化します。プレーヤーは毎朝、持ち株の時価総額を変えずに、株の売買をすることにより株AとBの構成比を変更することができるものとします。ただし、株売買の手数料は無料とします。30日後、持ち株の時価総額が最大のプレーヤーが勝者です。この例の場合、翌朝の株価を予測して持ち株の構成比の選択を行い、翌朝、実際の株価を知るということを繰り返すわけですが、このように見えない未来を過去の情報から予測し、累積利益を最大にすることを目的にして選択を繰り返すのがオンライン学習です。この株のポートフォリオ問題では、選ばなかった構成比に対する持ち株の時価総額の変化もプレーヤーは知ることができるわけですが、選んだ選択肢に対する情報のみ得られるという設定の問題をバンディット問題といいます。 当研究室では、レコメンデーション等に応用をもつバンディット問題について研究しています。

バンディット問題

あなたのブログのスペースの一部を広告枠として広告仲介会社にレンタルしたとします。広告仲介会社は、あなたのブログのページが誰かに表示される度に、100個の広告から1つ選んで広告枠に広告を配信するものとします。表示された広告に興味ある人は その広告をクリックし、広告の詳細情報を知ることができます。広告仲介会社は、クリック数に応じて広告主から広告掲載料を得ることができるとしましょう。この場合、広告仲介会社は最もクリック数が多くなるような広告を選択したいわけですが、それにはクリック率を推定する必要があります。この問題は、選択した広告に対してはクリックされたか否かのフィードバックは得られますが、選択しなかった広告に対しては何の情報も得られないバンディット問題です。このようなバンディット問題で最終的な累積クリック数を最大化するには、

[知識の獲得] クリック率の推定精度を上げるため、(たとえ過去のクリック率が低くても)選択回数の少ない広告を選択する

[知識の利用] 過去のクリック率が最大の広告を選択する

をバランス良く行う必要があります。この「知識の獲得と利用のトレードオフ」をうまく解決する戦略が理論的に研究されています。

当研究室では、特に選択肢を1つ選ぶのなく、選択肢の組合せを選択する組合せバンディットの研究を行っています。広告配信やレコメンデーションでは、1ページに複数広告や複数アイテム表示することが一般的であり、組合せバンディットの理論は実際の応用に役に立つものと思われます。(担当 : 渡辺

bandit_ad_app.jpg

レコメンデーション

オンラインショップのアマゾンで商品を探して情報を表示させると、「この商品を見た後に買っているのは?」という情報のところに興味のある商品が並んでいることが良くあります。これは商品の購買・覧履歴が似ているユーザが既に購買している商品をおすすめするという協調フィルタリングと呼ばれるレコメンデーション法の一種であり、1990年代半ばのインターネットの普及と共に盛んに研究されているものです。ユーザとアイテムの(隠れた)低次元属性ベクトルの内積で、ユーザのアイテムに対する嗜好度が表現されると解釈できる行列分解モデルは、2000年代半ばから盛んに研究されています。

本研究室では、協調フィルタリングによるレコメンデーションをバンディット問題として捉え、ユーザの満足度を最大化する行列分解モデルによるおすすめ法などについて研究しています。

bandit.jpg

PAGETOP
Copyright © 情報認識学研究室 All Rights Reserved.
Powered by WordPress & BizVektor Theme by Vektor,Inc. technology.