5 Conclusion
2.3 多重スケール単語分布推定
多重スケール単語分布ωt,z,w(s) は，確率的EMアルゴ リズムにより推定された潜在トピックを用いて推定でき る．ω(s)t,z,wは時刻t−2s−1+ 1からtにおけるトピック zでの単語wの出現確率であるため，その推定値は下式 により得られる．
ˆ ω(s)t,z,w=
Nˆt,z,w(s)
∑
wNˆt,z,w(s)
=
∑t
t0=t−2s−1+1Nˆt0,z,w
∑
w
∑t
t0=t−2s−1+1Nˆt0,z,w
, (10) ここで Nˆt,z,w(s) は時刻t−2s−1+ 1からtまでのトピッ クzにおいて単語wの期待出現回数であり，Nˆt,z,wは 時刻tにおける期待出現回数である．期待出現回数は
Nˆt,z,w =Nt,zφˆt,z,wにより計算できる．ここでφˆt,z,wは
φt,z,wの推定値を表し ，
φˆt,z,w =Nt,z,w+∑
sλt,s,zωˆ(s)t−1,z,w Nt,z+∑
sλt,s,z
, (11)
により得られる．式(10)において，期待値Nˆt,z,wでは なく，実際の値Nt,z,wを用いることも可能だが，ˆω(s=1)t,z,w
とφt,z,wの推定値を
ˆ ωt,z,w(s=1)=
Nˆt,z,w
∑
wNˆt,z,w
= ˆφt,z,w, (12)
のように一致させるため，期待値を用いた．
期待値Nˆt,z,w(s) は下式のように，一時刻前の値Nˆt(s)−1,z,w から逐次的に計算できるため，2s−1回の加算は必要は なく，二回の加算のみで推定可能である．
Nˆt,z,w(s) ←Nˆt(s)−1,z,w+ ˆNt,z,w−Nˆt−2s−1,z,w. (13) しかしながら，Nˆt,z,w(s) の更新には時刻t−2S−1からt−1
までのNˆt,z,wが必要であるため，記憶容量はスケール数
に対して指数的に増加し，多重スケール単語分布の更新 に計O(2S−1ZW)の記憶容量が必要となる．そこで，長 期スケールの更新頻度を減らし，近似的に期待値を求め ることにより，記憶容量を削減するアルゴ リズム（表3） を提案する．Nˆt,z,w(s) を毎時刻更新するのではなく，2s−1 時刻毎に更新することにより，一時刻前のNˆt(s)−1,z,wの 近似値と新たに得られたデータから，Nˆt,z,w(s) の近似値を 計算することができる．つまり，各時刻の期待値Nˆt,z,w の保持が不要で，記憶容量をO(SZW)に抑えることが でき，記憶容量はスケール数に対して線形に増加するた め，長期スケールの単語分布もモデルに組み込むことが 可能である．図4に，期待値Nˆt,z,w(s) の提案近似更新図 を示す．各矩形はNˆt0,z,wを表し，矩形内の数字はt0を 表す．各時刻の各行はNˆt,z,w(s) を表し ，塗潰し 矩形は値 が更新されたことを表す．長期スケールの単語分布の変 化は短期スケールの単語分布の変化よりも遅いと考えら れるため，長期スケールの更新頻度を減らすことは妥当 であると考えられる．図1(c)にオンライン推定する場 合の提案モデルののグラフィカルモデルを示す．
単語分布のデ ィリクレ事前分布のパラメータとして，
(1)にあるように，多重スケール単語分布の重み付き和 を用いた．このパラメータは，下式の様に，各時刻の単 語分布の重み付き和として表現することができる．
∑S
s=1
λt,z,sωˆ(s)t−1,z,w =
∑S
s=1
λt,z,s
∑t−1
t0=t−2s−1Nˆt0,z,w
∑
w
∑t−1
t0=t−2s−1Nˆt0,z,w
=
t−1
∑
t0=t−2S−1
λ0t,z,t0φˆt0,z,w, (14)
1: Nˆt,z,w(1) ←Nˆt,z,w 2: fors= 2,· · · , Sdo
3: if tmod 2s−1= 0 then
4: Nˆt,z,w(s) ←Nˆt,z,w(s−1)+ ˆNt(s−−1,z,w1)
5: else
6: Nˆt,z,w(s) ←Nˆt(s)−1,z,w
7: end if
8: end for
図3: Algorithm for the approximate update of ˆNt,z,w(s) .
1 2 3 4 3 4 4 t=4 s=3 s=2 s=1
1 2 3 4 3 4 5 t=5
5
1 2 3 4 5 6 6 t=6
6
1 2 3 4 5 6 7 t=7
7
5 6 7 8 7 8 8 t=8
8 1 2 3 4
1 2 3 4 3 4 3 4 4 t=4 s=3 s=2 s=1
1 2 3 4 1 2 3 4 3 4 3 4 5 t=5
5
1 2 3 4 1 2 3 4 5 6 5 6 6 t=6
6
1 2 3 4 1 2 3 4 5 6 5 6 7 t=7
7
5 6 7 8 5 6 7 8 7 8 7 8 8 t=8
8
図4: Illustration of approximate updating ˆNt,z,w(s) from t= 4 tot= 8 with S= 3.
ここで重みは λ0t,z,t0 =
∑S
s=dlog2(t−t0+1)+1e
λt,z,s
∑
wNˆt0,z,w
∑
w
∑t−1
t00=t−2s−1Nˆt00,z,w
(15) である．従って，提案モデルは過去の各時刻の単語分 布に依存するモデルとみなすこともできる．提案モデ ルでは，多重スケールモデルとして考えることにより，
重みパラメータΛtの数をO(2S−1Z)からO(SZ)に削 減できるため，頑健なモデル推定が可能となる．さら に，近似を用いることにより，上述のように記憶容量も O(2S−1ZW)からO(SZW)に削減できる．
3 実験
提案法を評価するため，NIPS，PNAS，Digg，Ad-dressesの4つの実文書データセットを用いて実験を行
った．
NIPSデータは国際会議NIPS (Neural Information Processing Systems) の 1987年から 1999年までの論 文データであり，文書数1,740，語彙数14,036であっ た．PNASデータは論文誌Proceedings of the National Academy of Sciences の1915年から2005年までのタ イトルデータであり，文書数79,477，語彙数20,534で あった．DiggデータはソーシャルニュースサイトDigg (http://digg.com)に投稿された2009年1月29日から2 月20日までのブログ記事データであり，文書数108,356，
語彙数23,494であった．Addressesデータは1790年か
ら2002年までのアメリカ大統領の一般教書演説のデー タであり，三段落を集めたものを一文書とみなした[18]．
このとき文書数6,413，語彙数6,759であった．全デー タセットにおいてストップ ワード を省き，単位時間を NIPS，PNAS，Addressesでは1年，Diggでは1日と した．
提案法MDTMをDTM，LDAall，LDAone， LDAon-lineの4手法と比較した．DTMはオンライン学習可能 な時間発展トピックモデルであり，提案モデルMDTM でスケール数をS = 1としたときのモデルに対応し，多 重時間スケールは考慮していない．LDAall，LDAone，
LDAonlineは時間発展を考慮しないLDAモデルである．
LDAallでは過去の全データを学習に用いる．LDAone
では一時刻前のデータのみ学習に用いる．LDAonlineは LDAをオンライン学習したものである[3]．トピック数 は全モデルZ = 50とした．提案モデルにおけるスケー ル数は、最大スケールの分布がデータ全期間を含むよう に設定したS =dlog2T + 1e．ここでTは時刻数であ る．また，γ= 1とし，ディリクレ分布のパラメータは，
過学習を防ぐため，αt,z≥10−2の制約のもとで最適化 した．各手法の予測誤差をパープレキシティによって評 価した．低いパープレキシティは低い予測誤差を表す．
全体の10%の文書をテスト文書とし ，テスト文書に含
まれる半数の単語を予測した．10セットの学習・テスト データをランダムに作成し，その平均パープレキシティ で評価した．
平均パープレキシティを表2に，各時刻毎のパープレキ シティを図5に示す．全データセットにおいて，MDTM が最も低い平均パープレキシティであり，MDTMは多 重スケールでの時間発展を考慮することにより，多様な 文書データの時間発展を適切にモデル化できることを示 す．DTMのパープレキシティが高い理由は，長期間の依 存性を考慮していないためであると考えられる．LDAall
とLDAonlineは時間発展を考慮していないため，高い
パープレキシティとなっている．また，LDAoneは一時 刻のみのデータしか学習に利用せず，過去の情報を無視 するため，高いパープレキシティとなっている．
提案法においてスケール数を変化させたときの平均 パープレキシティを図6に示す．スケール数が増加する に従い，パープレキシティが減少している．この結果は，
複数の時間スケールの分布を考慮することの重要性を示 している．
図7にXeon5355 2.66GHz CPUの計算機を用いた場 合の，一時刻あたりの平均計算時間(秒)を示す．MDTM の計算時間はスケール数に対して線形に増加している．
また，MDTMでは多重時間スケールを考慮しているに
表2: Average perplexities over epochs. The value in the parenthesis represents the standard deviation over data sets.
MDTM DTM LDAall LDAone LDAonline
NIPS 1754.9(41.3) 1771.6 (37.2) 1802.4 (36.4) 1822.0 (44.0) 1769.8 (41.5) PNAS 2964.3(122.0) 3105.7 (146.8) 3262.9 (159.7) 5221.5 (268.7) 3401.7 (149.1)
Digg 3388.9(37.7) 3594.2 (46.4) 3652.6 (27.1) 5162.9 (43.4) 3500.0 (43.6) Addresses 1968.8(56.5) 2105.2 (49.7) 2217.2 (75.3) 3033.5 (70.9) 2251.6 (62.0)
1600 1700 1800 1900 2000
2 4 6 8 10 12
perplexity
epoch
0 2000 4000 6000 8000 10000 12000
10 20 30 40 50 60 70 80 90
perplexity
epoch
MDTM LDAall LDAone
(a) NIPS (b) PNAS
2000 3000 4000 5000 6000
5 10 15 20
perplexity
epoch
1000 2000 3000 4000 5000 6000
50 100 150 200
perplexity
epoch
MDTM LDAall LDAone
(c) Digg (d) Addresses
図 5: Perplexities for each epoch with MDTM, LDAall, and LDAone.
も関わらず，全データを用いて学習するLDAallに比べ て極めて少ない計算量であると言える．
図8に推定されたスケール毎の重みλt,z,sを示す．各 時刻，各トピックで和が1になるように正規化してい る．スケールが長くなるに従い，重みが減少する傾向が ある．この結果は，最近の分布は，現在の分布を推定す るためにより重要であるという，直感と合致した結果で ある．
4 おわりに
本稿では，多重時間スケールでの時間発展を考慮し たトピックモデルと，その効率的なオンライン学習法を 提案した．また，実験により，提案法は従来法に比べよ り高い精度で予測できることを示した．今後の課題と しては，ディリクレ過程を用いたトピック数の自動推定
[15, 16]や，スケールの自動設定などが考えられる．
参考文献
[1] L. AlSumait, D. Barbara, and C. Domeniconi. On-line lda: Adaptive topic models for mining text streams with applications to topic detection and tracking. In ICDM ’08, pages 3–12, 2008.
[2] C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jor-dan. An introduction to MCMC for machine learning.
Machine Learning, 50(1):5–43, 2003.
[3] A. Banerjee and S. Basu. Topic models over text streams: A study of batch and online unsupervised learning. InSDM ’07, 2007.
[4] D. M. Blei and J. D. Lafferty. Dynamic topic models.
InICML ’06, pages 113–120, 2006.
[5] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirich-let allocation. Journal of Machine Learning Research, 3:993–1022, 2003.
[6] K. R. Canini, L. Shi, and T. L. Griffiths. Online in-ference of topics with latent Dirichlet allocation. In AISTATS ’09, volume 5, pages 65–72, 2009.
[7] T. L. Griffiths and M. Steyvers. Finding scientific top-ics. Proceedings of the National Academy of Sciences, 101 Suppl 1:5228–5235, 2004.
1700 1720 1740 1760 1780 1800 1820 1840 1860 1880
0 1 2 3 4 5
perplexity
#scales
2800 3200 3600 4000 4400 4800 5200
0 1 2 3 4 5 6 7 8
perplexity
#scales
3200 3400 3600 3800 4000 4200 4400 4600
0 1 2 3 4 5 6
perplexity
#scales
1800 2000 2200 2400 2600 2800
0 1 2 3 4 5 6 7 8 9
perplexity
#scales
(a) NIPS (b) PNAS (c) Digg (d) Addresses
図6: Average perplexity of MDTM with different numbers of scales.
0 1 2 3 4 5 all one online 0
500 1000 1500 2000 2500 3000 3500 4000
0 1 2 3 4 5 6 7 8 allone online
0 100 200 300 400 500 600 700 800
0 1 2 3 4 5 6 allone online
0 1000 2000 3000 4000 5000 6000
0 1 2 3 4 5 6 7 8 9 allone online
0 100 200 300 400 500 600 700 800 900 1000
(a) NIPS (b) PNAS (c) Digg (d) Addresses
図7: Average computational time (sec) of MDTM per epoch with different numbers of scales, LDAall, LDAone, and LDAonline.
0.04 0.06 0.08 0.1 0.12 0.14 0.16
1 2 3 4 5
lambda
scale
0.04 0.08 0.12 0.16 0.2 0.24
1 2 3 4 5 6 7 8
lambda
scale
0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18
1 2 3 4 5 6
lambda
scale
0.06 0.08 0.1 0.12 0.14 0.16
1 2 3 4 5 6 7 8 9
lambda
scale
(a) NIPS (b) PNAS (c) Digg (d) Addresses
図8: Average normalized weightλwith different scales estimated in MDTM.
[8] T. Hofmann. Probabilistic latent semantic analysis. In UAI ’99, pages 289–296, 1999.
[9] T. Hofmann. Collaborative filtering via Gaussian probabilistic latent semantic analysis. In SIGIR ’03, pages 259–266, 2003.
[10] T. Iwata, S. Watanabe, T. Yamada, and N. Ueda.
Topic tracking model for analyzing consumer purchase behavior. InIJCAI ’09, 2009.
[11] T. Iwata, T. Yamada, and N. Ueda. Probabilistic la-tent semantic visualization: topic model for visualizing documents. InKDD ’08, pages 363–371, 2008.
[12] T. Minka. Estimating a Dirichlet distribution. Tech-nical report, M.I.T., 2000.
[13] R. Nallapati, W. Cohen, S. Ditmore, J. Lafferty, and K. Ung. Multiscale topic tomography. InKDD ’07, pages 520–529, 2007.
[14] S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming pattern discovery in multiple time-series. In VLDB
’05, pages 697–708, 2005.
[15] L. Ren, D. B. Dunson, and L. Carin. The dynamic hi-erarchical Dirichlet process. InICML ’08, pages 824–
831, 2008.
[16] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei.
Hierarchical Dirichlet processes.Journal of the Ameri-can Statistical Association, 101(476):1566–1581, 2006.
[17] C. Wang, D. M. Blei, and D. Heckerman. Continuous time dynamic topic models. In UAI ’08, pages 579–
586, 2008.
[18] X. Wang and A. McCallum. Topics over time: a non-Markov continuous-time model of topical trends. In KDD ’06, pages 424–433, 2006.
[19] X. Wei, J. Sun, and X. Wang. Dynamic mixture mod-els for multiple time-series. InIJCAI ’07, pages 2909–
2914, 2007.
情報論的学習理論テクニカルレポート2009
Technical Report on Information-Based Induc-tion Sciences 2009 (IBIS2009)
Observational Reinforcement Learning
Jaak Simm, Masashi Sugiyama, and Hirotaka Hachiya
∗Abstract: We introduce an extension to standard reinforcement learning setting called observational RL (ORL) where additional observational information is available to the agent. This allows the agent to learn the system dynamics with fewer data samples, which is an essential feature for practical applications of RL methods. We show that ORL can be formulated as a multitask learning problem. A similarity-based and a component-based multitask learning methods are proposed for learning the transition probabilities of the ORL problem. The effectiveness of the proposed methods is evaluated in experiments of grid world.
1 Introduction
Recently, there is an increasing interest for methods of planning and learning in unknown and stochastic environments. These methods are investigated in the field of Reinforcement Learning (RL) and have been applied to various domains, including robotics, AI for computer games, such as tetris, racing games and fight-ing games. However, one of the main limitfight-ing factors for RL methods has been their scalability to large en-vironments, where finding good policies requires too many samples, making most RL methods impractical.