Gunosyデータ分析ブログ

Gunosyで働くデータエンジニアが知見を共有するブログです。

「これからの強化学習」1章の内容で三目並べ

こんちくわ。データ分析部兼サウンドエンジニアの大曽根です。最近は吾妻光良&The Swingin Buppersのライブに行きました。

今回は4/12に開催した「これからの強化学習」の輪読会の1.3節で紹介した価値反復法のアルゴリズムを、教科書とは異なる例で実装してみました。

開催報告については下記のブログをご覧ください。

data.gunosy.io

メジャーなゲームである三目並べを、1.3節にて紹介されているSarsaを用いて学習しました。 教科書とは別の例で実装することで少しでも理解が深まればと思います。

価値反復に基づくアルゴリズム

マルコフ決定過程において価値関数を特定の更新式に従って更新する手法です。(今回はSarsaで試しました。) 発表の際には、tの状態の更新式に次の状態 t+1が含まれているところなどがわかりづらいとの質問を受けました。 価値反復に基づくアルゴリズムでは過去の事例(エピソード)における、次の状態を参考に現在の行動価値関数を変更していくのでその点がわかりづらいかもしれません。

実装

エージェントと対戦相手が特定の座標に交互に手を打っていく形式になります。 (こういう類のシミュレーションでは)先行と後攻を固定する場合もありますが、今回は先行と後攻を対戦ごとに交代する形式の実装にしています。 また、すでに自身もしくは対戦相手が打った場所には手を打たない制御を入れています。

環境

盤面の座標および○×がどこに置かれているか 実際のコードでは ○: 1、×: - 1、空白: 0の3つの値を持つlistで表現しました

s = [ 0, 0, 0, 0, 0, 0, 0, 0, 0]

単純に考えると39通りの状態が考えられ、3目並べ程度のゲームで意外に環境の取りうる範囲は広いことがわかるかと思います。 (実際には存在しない手もあるのでもっと少なくなります。)

行動:

自身の手順の際にs の配列のどこを変更するかを行動としています。 上述の通り環境sの0 (○×のいずれも打たれていない場所) にしか打たない制御をしています。

A = [ 0, 1, 2, 3, 4, 5, 6, 7, 8]

報酬: 勝敗

報酬は勝敗が決定した際のみに振り分けられるものとし、勝利した際(○が3つ並んだ場合)にはプラスの報酬、負けた際(×が3つ並んだ場合)にはマイナスの報酬を振り分けられるようにしました。

f:id:dr_paradi:20170613183916j:plain

また、引き分けの際には報酬なしに設定しました(ここのルール設定によって学習の挙動が異なるかもしれません)。

学習のイメージ

f:id:dr_paradi:20170608015134p:plain

下記の例の場合には正の報酬を得ることができます。

s = [1, 1, 1, 0, -1, 0, 0, -1, 0]

ですので

sn = [ 1, 1, 0, 0, -1, 0, 0, -1, 0]

の際の

an = 2

の場合は勝利することができる(報酬が獲得できる)ため、 Q[sn][an] の価値関数が高くなれば学習が成功していると言えます。

これを繰り返して行くと次の状態価値関数を別のエピソードでフィードバックすることができます。

f:id:dr_paradi:20170613183920j:plain

方策

どの手を打つかの戦略を方策としています。Q値が高いものを打つパターンと、一定確率でランダムの戦略を打つ場合(ε-greedy)の二つを用意しました。

結果

学習に関するパラメータはα = 0.2、γ = 0.8で設定しトータルで10,000ゲームを行い、

  • ベースラインとして用意した完全ランダムのアルゴリズム
  • sarsa
  • sarsa ε-greedy (ε = 10%)

の三種類のアルゴリズムで100試合ごとの勝率をplotしました。 完全ランダムの場合と比較しますると、sarsaのアルゴリズムの場合には徐々に勝率が高くなっていることがわかるかと思います。 今回の例ではあまりgreedyとε-greedyとの間に大きな差はありません。 (plotをみる限りは学習(収束)が割とはやいので探索に対するメリットがないのかもしれません)

f:id:dr_paradi:20170529013128p:plain

考察

初期の盤面のQ値をあまり学習できていなかったので、

  • 初期の盤面のみルールを与える
  • リーチの時点で少し報酬をあたえるなど

なども試してみると面白いかと思いました。

感想

非常にシンプルなゲームですが、ターンの概念や勝敗判定などゲームの基礎的な部分の実装に以外と時間がかかってしまいました。 強化学習は環境の設定と報酬の設定など、本で読むより実装すると気づく部分も多いかと思います。全てを実装する必要はないかと思いますが、本を読みつつ実装してみるのも学びを進める上では重要かと思います。

今後

他のゲームの実装や、学習過程の可視化なども試して行きたいです。

Gunosyデータ分析サマーインターン募集のお知らせ

こんにちは、データ分析部の久保です。 今日はサマーインターンの募集を開始したのでそのお知らせです。

データ分析コース|Gunosy Summer Internship 2017

詳しくはリンク先を見ていただくとして、実際のGunosyプロダクトで使われるような「生きた」データ分析を体験できるインターンとなっています。

期間は3日間と短くなってはいますが、出題される課題を通じていろんなことが学べるように私達も準備しています。

当日はデータ分析部メンバーを始め、現在Gunosyで深くデータに関わっているメンバーがメンターとして適宜アドバイスも行うので、データ分析という仕事に興味はあるけど、実際どんなものなのか体験したいという学生の皆さんはぜひ応募してみてください(ちなみに今回のサマーインターンとは別に研究開発、データ分析アルバイトは通年でも募集しています)。

3日間六本木でおいしいご飯を食べられる、という特典ももれなくついてきます。

またこれも宣伝ですが先日、最近始めた会社のポッドキャストに出演して、データ分析部とはどういう雰囲気で仕事をしているか、というのも話しているので興味があればぜひこっちも聴いてみてください!

#2 ざっくりわかる、データ分析部 by gunosy.fm | Gunosy Fm | Free Listening on SoundCloud

iTunesでの購読はこちらから

それでは夏休みに皆さんと会えるのを楽しみにしています!

Gunosyデータマイニング研究会 119回, 120回を開催しました

こんにちは。グノシーデータ分析部の関です。 最近はMaison book girlのkarmaをよく聞いています。

今回の投稿では4/24に開催したGunosy DM #119と5/10に開催したGunosy DM #120について紹介します。 これまで同様、これからの強化学習の輪読と論文紹介を行っております。

書籍輪読 - これからの強化学習

#119では2.1節を関が紹介し、 #120では2.2, 2.3節を関が 2.4節をatlimited様に紹介いただきました

1章では価値関数が離散的な状況を想定していましたが、 2.1節では価値関数が連続的であることを考慮し、その中で関数を近似する方法を検討しています。 通常の機械学習では、入力がi.i.dであることを仮定していますが、 強化学習では、得られるデータが方策に依存するので、マルコフ性を持ってしまうため、収束が保証されません。 そのなかで収束をさせるための様々な方法について論じられています。 後半で、すべての手法がセミパラメトリックモデルで解釈できるという点が面白かったです。

2.2節は探索と利用のトレードオフをどのように理解するかという点について紹介されていました。 リグレット、サンプル複雑性などの指標により、評価されています。 ただ、紹介されていたのはシンプルなルールによる手法で、 このあたりはなかなか難しい領域なのかと思うと同時に、 ルールを導入することで、様々な実問題が解決できるヒントでもあるなと思いました。

2.3節は逆強化学習について紹介されていました。 価値関数を定義することが難しい場合における学習法で、 エキスパートや、正しい方策から価値関数を学ぶ方法について学びました。 将棋の棋譜からの学習のように最終的な勝ち負けが与えられた上で、その過程を学習するのは、こういうアプローチなのだなと。

qiita.com

2.4節は経験型強化学習についてでした。 どのように試行回数を減らすかという点についての章で、 学習が過度に行われてしまうようなパターンをうまく回避するような方法が紹介されていました。

論文紹介

#119では 米田より A Complete Recipe for Stochastic Gradient MCMCの紹介が行われました。

この論文はNIPS2015で発表されたもので、一言でいうとすべてのMCMCアルゴリズムが、一般的な確率微分方程式で記述できることを示したものです。 これによって、様々な問題に対するMCMCアルゴリズムを設計することが、容易になったといえます。 当日は数学科出身の米田を中心に、濃密なディスカッションが行われました。

#120では吉田より、 Attention and Engagement-Awareness in the Wild: A Large-Scale Study with Adaptive Notificationsの紹介が行われました。

こちらの論文はYahoo!Japanが発表した論文で、スマートフォンアプリケーションにおけるプッシュ通知の効果を最大化するために、 ユーザの状態を考慮してプッシュを発火させるものです。 実際のYahooアプリにおいて大規模な実験が行われ、その効果が立証されていることが印象的でした。

おわりに

次回の#121は5/16に、#122は5/31に開催予定です。 皆さんの参加をお待ちしております。

Pandasによる実践データ分析入門

こんにちは。データ分析部のオギワラです。最近は「NANIMONO (feat.米津玄師)」をよく聞いています。 今回はPythonのデータ分析ライブラリであるPandasについて、実践的なテクニックを「データ処理」「データ集計(Group By)」「時系列処理」の3カテゴリに分けてご紹介していきます。

Pandasに関する基本的な内容については、前エントリーで既に紹介されているので、是非こちらもご一読して頂けると幸いです。

data.gunosy.io

今回、サンプルデータとしてKaggle上に公開されているFourSquareの行動ログデータを利用しています。

FourSquare - NYC and Tokyo Check-ins | Kaggle

このデータは、2012年の4月から2013年2月まで間にFourSquareを利用したユーザの、以下のようなチェックイン情報が記載されています。

- ユーザID (user_id)
- 入店したお店のカテゴリID (venue_category_id)
- 入店したお店のカテゴリ (venue_category)
- お店の緯度・経度情報 (lat, lng)
- 入店時刻 (timestamp)

このデータを利用して実際の分析内容・シチュエーションにも触れながらPandasの実践テクニックをご紹介していきます。 また、今回使用したJupyter NotebookをGitHubのリポジトリに配置したので、実際の動作等を確認したい方はぜひ利用して下さい。

pandas_analysis_topic/pandas_data_analysis_topic.ipynb at master · ogiogi93/pandas_analysis_topic · GitHub

データ処理

データの取り出し(query)

今回のデータには197ものお店カテゴリが存在し全カテゴリを一度に分析することは困難です。そこで対象のお店カテゴリを交通機関に絞って見ます。そのような時にquery 関数を利用することができます。 query関数はSQLのクエリのように条件を記述することでデータの取り出しを行うことができます。

>>> #venue_categoryがAirtportまたはSubwayである行を抽出する
>>> df.query("venue_category in ['Airport', 'Subway']")
'''
  user_id venue_category  timestamp
10    589 Airport 2012-04-04 04:59:06+09:00
32    1876    Subway  2012-04-04 05:59:52+09:00
34    499 Subway  2012-04-04 06:04:04+09:00
'''

条件文に基づくデータ処理の適用(where)

今回のデータでは特に必要ありませんが、データによって欠損値や異常値が含まれていることがあります。これらの値を含む行を除く場合欠損値はdropna、外れ値はquery関数を利用することができます。しかし行を除くのではなく何かしらの値で置換したいと考えた場合、欠損値は fillna関数で利用することができますが、異常値に対しては利用することができません。このような時にwhere関数を利用することができます。where関数は条件文に基づく行に対してのみ処理を適用することができます。(ex. 負値は0に置換する、異常値は平均値に置換するなど)

>>>#例: user_idが10以下の行に対して, +10加算する
>>>#条件を満たさない行(other)に対して処理が適用されます
>>>df['test'] = df['user_id'].where(cond=lambda x: x >10, other=lambda x: x + 10)
'''
user_idが10以下であるため加算処理が適用されている
  user_id test
9168  1   11
'''
'''
user_idが10以上であるため加算処理が適用されていない
  user_id test
3659  2292    2292
'''

各行への関数の適用(apply)

各行に対して関数を適用したい時、apply関数を利用することができます。また複数の列に対して適用したい時は、行和を指定(axis=1) することで適用することができます。
注意: 大規模なデータセットを分析している場合apply関数は非常に時間がかかるため、DataFrameを一旦リスト化・numpyでベクトル化して関数を適用するなどの工夫をした方が良いです。次回以降の高速化に関する内容も執筆していきたいと思っています。

>>>#user_idをハッシュ化する関数を適用する
>>>df['hashed_user_id'] = df['user_id'].apply(_hash) #user_idを引数とする_hash関数を適用、新たな列を生成

>>> 緯度・経度情報から住所を取得する
>>> df['address'] = df.apply(gis_to_address, axis=1) # 関数上で複数列(緯度・経度)を指定し住所を取得、新たな列を生成

データ集計(Group By)

カラム毎に異なる集計を適用する(agg)

地点・時間別でのチェックイン数の平均・中央値などを知りたい時に、agg関数を利用することでまとめて集計することができます。 今回は例として15分ごとに各店舗(カテゴリ)のチェックイン人数をカウントし、その後店舗(カテゴリ)ごとにチェックイン人数の平均・中央値を求めてみます。

>>># Round関数を適用し、timestampを15分間隔に丸める
>>>df['15min'] = od.DatetimeIndex(df['timestamp']).round('15min')
>>>#15分ごとの各店舗(カテゴリ)のチェックイン人数をカウント
>>> number_of_people = df.groupby(['venue_category', '15min']).agg({'user_id': 'count'}).reset_index()
'''
  venue_category  15min   user_id
10705 Subway  2012-04-04 07:30:00+09:00   8
10706 Subway  2012-04-04 07:45:00+09:00   12
10707 Subway  2012-04-04 08:00:00+09:00   12
10708 Subway  2012-04-04 08:15:00+09:00   12
10709 Subway  2012-04-04 08:30:00+09:00   12
10710 Subway  2012-04-04 08:45:00+09:00   20
'''
>>># 各店舗(カテゴリ)ごとにチェックイン人数の平均・中央値を算出
>>> number_of_people('venue_category').agg({'user_id': ['mean', 'median']})
'''
venue_category    user_id
mean  median
0 Airport 1.207921    1
1 American Restaurant 1.055556    1
2 Antique Shop    1.000000    1
'''

最大・最小値である行を取り出す(first)

各ユーザの最終アクションに関するデータを抽出したい時、groupby及びfirst関数等を用いることで実現することができます。 具体的な流れは(1) 対象のカラム値でソートする(最大値は降順、最小値は昇順) (2) 最大・最小値を抽出したいカラムでグループ化(3) 各グループの最初の行を抽出する 以下に各ユーザの最終地点(timestampが最後の行)を抽出する例を示します。

>>>#(1) 時間順で降順でソート (2) ユーザIDでグループ化 (3) ユーザごとに最初の行を抽出
>>>df.sort_values('timestamp', ascending=False).groupby(['user_id'], as_index=False).first()
'''
  user_id venue_category  timestamp
0 1   Train Station   2012-04-08 12:24:53+09:00
1 2   Train Station   2012-04-13 11:03:36+09:00
2 3   Smoke Shop  2012-04-13 07:26:35+09:00
3 4   Arcade  2012-04-14 11:24:53+09:00
4 6   Train Station   2012-04-08 21:36:10+09:00
'''

標準化や正規化処理を適用する(transform)

カテゴリごとに標準化・正規化したい時、groupby及びtransform関数を利用することができます。 以下に店舗(カテゴリ)ごとにチェックイン数を標準化する例を示します。

>>>#標準化関数
>>>zscore = lambda x: (x - x.mean()) / x.std()
>>>number_of_people['standarized_num_people'] = number_of_people.groupby('venue_category').transform(zscore)
'''
  venue_category  15min   num_people  standarized_num_people
10703 Subway  2012-04-04 07:00:00+09:00   3   -0.501261
10704 Subway  2012-04-04 07:15:00+09:00   4   -0.208489
10705 Subway  2012-04-04 07:30:00+09:00   8   0.962599
'''

時系列処理

時間の丸め処理(round)

既に上記でも登場していましたが、日付や1時間単位での集計だけではなく、15分や3分など独自の時間間隔で集計したいことがあります。このような時、round関数を利用することができます。 round関数はtimestampを指定した間隔に丸めることができます。

>>>df['date'] = df['timestamp'].dt.date
>>>df['hour'] = df['timestamp'].dt.hour
>>>df['15min'] = pd.DatetimeIndex(df['timestamp']).round('15min') #15分間隔
'''
  user_id venue_category  timestamp   date    hour    15min
0 1541    Cosmetics Shop  2012-04-04 03:17:18+09:00   2012-04-04  3   2012-04-04 03:15:00+09:00
1 868 Ramen / Noodle House    2012-04-04 03:22:04+09:00   2012-04-04  3   2012-04-04 03:15:00+09:00
2 114 Convenience Store   2012-04-04 04:12:07+09:00   2012-04-04  4   2012-04-04 04:15:00+09:00
'''

時系列データの差分計算(diff), 変化率計算(pct_change), 移動平均値の計算(rolling)

時系列データの変動を分析したい時、前時刻との差分はdiff関数, 変化率はpct_change, 移動平均値はrolling関数を用いることで簡単に算出することができます。また、店舗(カテゴリ)別やuser_id別で算出したい場合もgroupbyと組み合わせることで実現することができます。

>>>count_people_div_15min['diff'] = count_people_div_15min['num_of_people'].diff() #差分
>>>count_people_div_15min['pct_change'] = count_people_div_15min['num_of_people'].pct_change() #変化率
>>>count_people_div_15min['pct_change'] = count_people_div_15min['num_of_people'].rolling(window=3, center=False).mean() #移動平均
'''
15min num_of_people   change  pct_change  rolling_mean
0 2012-04-04 03:15:00+09:00   2   NaN NaN NaN
1 2012-04-04 04:15:00+09:00   5   3.0 1.5 NaN
2 2012-04-04 04:30:00+09:00   1   -4.0    -0.8    2.666667
3 2012-04-04 04:45:00+09:00   2   1.0 1.0 2.666667
4 2012-04-04 05:00:00+09:00   2   0.0 0.0 1.666667
'''
>>>#店舗カテゴリ別で算出したい場合はgroupbyと組み合わせる
>>>count_people_div_15min_venue_category['change'] = count_people_div_15min_venue_category.groupby('venue_category')['user_id'].diff() #店舗カテゴリ別差分
>>>count_people_div_15min_venue_category['pct_change'] = count_people_div_15min_venue_category.groupby('venue_category')['user_id'].pct_change() #店舗カテゴリ別変化率
>>>_rolling_mean = count_people_div_15min_venue_category.groupby('venue_category')['user_id'].rolling(window=3, center=False).mean() #店舗カテゴリ別移動平均
>>>count_people_div_15min_venue_category['rolling_mean'] = _rolling_mean.reset_index(level=0, drop=True)
'''
venue_category    15min   user_id change  pct_change  rolling_mean
10701 Subway  2012-04-04 06:00:00+09:00   2   NaN NaN NaN
10702 Subway  2012-04-04 06:45:00+09:00   2   0.0 0.000000    NaN
10703 Subway  2012-04-04 07:00:00+09:00   3   1.0 0.500000    2.333333
10704 Subway  2012-04-04 07:15:00+09:00   4   1.0 0.333333    3.000000
10705 Subway  2012-04-04 07:30:00+09:00   8   4.0 1.000000    5.000000
'''

Pandasと合わせて利用したい、おすすめライブラリ

Pandas及びJupyter Notebookでデータ分析していく際に是非利用した方が良いライブラリを2つご紹介します。

for文やapply関数などの進捗をバーで表示する(tqdm)

GitHub - tqdm/tqdm: A fast, extensible progress bar for Python and CLI

Pythonのfor文などの進捗を色付きバーでリアルタイムに表示してくれます。平常心を保ちながら大規模データを分析していくためにはこのライブラリは必須ですね。 Pandas向けの進捗バーも準備されており、tqdmを有効化した後にapply → progress_apply, map → progress_map に変更し実行することで表示されます。

>>> from tqdm import tqdm, tqdm_notebook
>>> tqdm_notebook().pandas() # pandas向けtqdmを有効化
>>> df.progress_apply(f)

f:id:ogiogi93:20170508113353p:plain

DataFrameをMarkdown形式で出力する(pytablewriter)

GitHub - thombashi/pytablewriter: A python library to write a table in various formats: CSV / HTML / JavaScript / JSON / LTSV / Markdown / MediaWiki / Excel / Pandas / Python / reStructuredText / SQLite / TOML / TSV.

分析結果をGithubのissueなどに転記する時に利用しています。DataFrameを自動的にMarkdown形式で出力してくれます。

>>>import pytablewriter
>>>writer = pytablewriter.MarkdownTableWriter()
>>>writer.from_dataframe(count_people_by_15min_category.head(5)) # Markdownに変換したいDataFrameを入力する
>>>writer.write_table()
'''
venue_category|         15min          |user_id|change|pct_change|rolling_mean
--------------|------------------------|------:|-----:|---------:|-----------:
Airport       |2012-04-04T05:00:00+0900|      1|   NaN|       NaN|         NaN
Airport       |2012-04-04T07:00:00+0900|      1|     0|         0|         NaN
Airport       |2012-04-04T08:15:00+0900|      1|     0|         0|        1.00
Airport       |2012-04-04T10:30:00+0900|      1|     0|         0|        1.00
Airport       |2012-04-04T11:45:00+0900|      2|     1|         1|        1.33
'''

さいごに

Pandasには今回紹介したメソッド以外にも、数多くのメソッドが実装されています。ぜひPandasの公式ドキュメントも読んでみて下さい! また、最近Pandasのリポジトリ上に「Pandas Cheat Sheet」という基礎内容が一つのpdfファイルにまとまったシートが公開されているので、ぜひダウンロードしておくことをお勧めします!

github.com

参考資料

【これからの強化学習】 Gunosy データマイニング研究会 #118 を実施しました

gunosy-dm.connpass.com

こんにちは。グノシー開発部のアルシャマンです。最近は、KID FRESINOのSalve feat. JJJをよく聴いています。

今日は4/12(水)に開催したGunosy DM #118について紹介します。前回に引き続きこれからの強化学習の1.3~1.5節の輪読と、論文紹介を行いました。

Gunosy DMこれからの強化学習については、以下のブログ記事で紹介しています。 data.gunosy.io

書籍輪読(これからの強化学習)

データ分析部の大曽根と吉田からそれぞれ1.3~1.4節と1.5節についての発表がありました。

1.3節では、MDP(マルコフ決定過程)における価値関数の表現と、それを推定するアルゴリズムについて学びました。具体的には、ある方策πのもとでの行動価値関数について成立する再帰式であるベルマン方程式とSarsaという学習法、最適行動価値関数について成立する再帰式であるベルマン最適方程式とQ-learningという学習法についてです。

1.4節では、方策を行動価値関数とは別のパラメータで表現された確率モデルと考え、そのパラメータについて最適化することで強化学習問題を解く方策勾配に基づく方法について学びました。

1.5節ではPOMDP(部分観測マルコフ決定過程)における強化学習について学びました。「エージェントは状態を部分的にしか観測できない」とした場合の強化学習についてです。どの状態にいるのかを表す確率分布である信念状態を導入して、価値関数を表現します。

論文紹介

次にデータ分析部の関から、Optimizing the Recency-Relevancy Trade-off in Online News Recommendationsという論文の紹介がありました。

ニュースサイトのトップページに掲載するニュースを選択する時に考慮される「Recency(新しさ)」と「Relevancy(ニュースの重要さ)」というトレードオフ関係にある2つの指標についての分析と「Highest Future-Impact(ニュース掲載後にどれだけPVを稼ぐか)」に基づいたニュース選択方法の提案がされています。

最後に

今後もGunosy DMは隔週開催予定です。次回の#119は、4/25(火)を予定しています。

次回の内容は、今回論文発表を担当した関からこれからの強化学習の2.1~2.3節の輪読と、同じくデータ分析部の【Edward】MCMCの数学的基礎からStochastic Gradient Langevin Dynamicsの実装までというブログの著者のmathetakeからA Complete Recipe for Stochastic Gradient MCMCという論文の紹介となっています。

興味ある方は、ぜひご参加下さい。

gunosy-dm.connpass.com