重みつき窓を用いた適応型オンライン予測
Adaptive Online Prediction with Weighted Windows
吉田 真一
1畑埜 晃平
2瀧本 英二
2竹田 正幸
2Shinichi YOSHIDA
1Kohei HATANO
2Eiji TAKIMOTO
2Masayuki TAKEDA
21
九州大学大学院 システム情報科学府 情報理学専攻
1
Department of Informatics, Kyushu University
2
九州大学大学院 システム情報科学研究院 情報学部門
2
Department of Informatics, Kyushu University
Abstract: We propose online prediction algorithms for data streams whose characteristics might
change over time. Our algorithms are applications of online learning with experts. In particular, our algorithms combine base predictors over sliding windows with different length as experts. As a result, our algorithms are guaranteed to be competitive with the base predictor with the best fixed-length sliding window in hindsight.
1
序論
近年の情報爆発により，時間が経つごとに生成され リアルタイムに与えられるデータストリームがより巨 大化し，株価や電気・ガスの使用量を用いた時系列予 測，センサデータによるデータ収集など様々な分野で 利用されている．また，情報科学においてデータベー スやアルゴリズム [1, 2]，データマイニング，機械学習 [3] など様々な分野で研究されている．データストリー ムは，環境の変化によりその傾向が時間とともに変化 し（Concept Drift），全体を保持することができない などの特徴があり，精度の高い予測や分析を行うために データストリームの傾向の変化に適応する必要がある． データストリームに対する予測を行うのに適したデー タ構造としてスライド窓が挙げられる．スライド窓は 最近のデータのみ保持する．新しい例が来るたびに，ス ライド窓は最も古い例を捨て，新しい例を加える．そ して，スライド窓のデータのみを用いて予測器（線形回 帰・SVM など）が予測を行う．時間とともに変化する データストリームに対して，最近のデータは古いデー タに比べてより有益な情報を含んでいる．従って，最 近のデータを保持するスライド窓はデータストリーム に対する予測において有効な手法である． スライド窓はその大きさ（窓幅）によりデータスト リームへの適応度が変化する．窓幅が大きいほど，デー タストリームが生成される環境が急変する場合に急変に 適応することが難しい．逆に，窓幅が小さいほど，デー タストリームが生成される環境が安定している場合に ノイズの影響を受けやすい．その結果，予測精度が悪 化する可能性がある．従って，データストリームに合っ た窓幅のスライド窓を用いて予測を行う必要がある． しかし，窓幅が固定（固定窓）の場合，リアルタイ ムに与えられるデータストリームに対し，事前に最適 な窓幅を決めるのは不可能である．そこで，データス トリームの傾向に合わせて古いデータの取捨選択を決 め，窓幅を可変（適応窓）にするアプローチが用いら れる [4, 5, 6, 7]．しかし，適応窓の手法は古いデータ の取捨選択を決める閾値などパラメータの設定により 性能が大きく変化する．例えば，ADWIN[4] は，スト リームデータの傾向が安定している場合，一時的に発 生するノイズに過敏に反応し窓幅が極端に小さくなり， 予測精度の悪化を招くおそれがある． そこで，本論文ではエキスパートを用いたオンライン 予測に基づく，スライド窓への新たなアプローチを提案 する．我々は複数の窓幅の異なる固定窓による予測を重 み付き平均アルゴリズムにより統合する（Weighted Window, 以下 WW）．統合する固定窓の総数をM とすると，WW は，最も予測精度の高い固定窓に対す る累積損失の差（リグレット）がO(ln M) で抑えられ る．従って，事前に最適な窓幅が分からない場合でも， WW は最適な窓幅の固定窓に匹敵する予測性能を得る ことができる． エキスパートを用いたオンライン予測とは，エキス パートとよばれる複数のオンライン予測器が与えられ， それらの予測を統合する手法である [8, 9, 10, 11, 12, 13, 14]．特に，重み付き平均アルゴリズム (Weighted Averaging Algorithm，以下 WAA)[16] はエキスパート の予測の重み付き平均を予測値とし，予測精度の高い エキスパートの予測が反映されやすくなるように重み の更新を行う．WW は WAA の手法を用いることによ人工知能学会研究会資料 SIG-DMSM-A903-10 (03/30)
り，データストリームの各時点で適した固定窓による 予測を統合した，最善に近い予測を行える．その結果， WW はデータストリームを通して最適な固定窓の予測 精度に匹敵する性能を得ることができるのである． さらに，本論文では，[17] のアプローチを適用し，区 間ごとに実行した WW の予測を統合する Weighted
Window with follow the leading History（以下，
WWH）を提案する．WWH は，任意の区間で実行した WW の固定窓に対する累積損失の差（適応リグレット） がO(ln M ln T +ln2T ) で抑えられる．WWH は，デー タストリームの傾向を捉えるのに適した区間で WW を 実行できるため，WW よりさらにデータストリームに 適応することができる．また，計算機実験の結果，WW・ WWH が他手法に比べて予測精度が高く，任意のデー タストリームに対し WWH が最も良い予測精度であっ たことを示す．
2
準備
N を固定の自然数とし，X ⊂ RNを事例空間と呼ぶ． また，事例空間X の要素 x を事例と呼ぶ．自然数 r, s に対して，[r, s] は連続した自然数列 r, . . . , s からなる 集合を表す． 特に，r = 1 のとき [1, s] = [s] と略記 する．2.1
エキスパートを用いたオンライン予測
本論文では以下のようなオンライン予測問題を考え る．各時刻t = 1, . . . , T において， 1. 環境が事例xt∈ X を予測者に与える． 2. 予測者は 事例 xt に対する予想値 ˆyt∈ [0, 1] を 予測する． 3. 環境は真の値 yt∈ [0, 1] を予測者に与える． 4. 予測者は損失 (ˆyt, yt) を被る． ここで，関数 : [0, 1] × [0, 1] → R を損失関数と呼ぶ． 特に，エキスパートを用いたオンライン予測問題 ([15, 18] など) においては，予測者はエキスパートを利用す ることができる．より正確には，予測者にはM 個のエ キスパートE1, . . . , EMが与えられる．各時刻t におい て各エキスパートEi (i = 1, . . . , M) は事例 xt ∈ X を入力とし，予想値ξt,i∈ [0, 1] を返す． 予測者の目標は（オフラインで見たときに）“ 最適 ” なエキスパートに匹敵する予測を行うことである．よ り具体的には以下２つの指標を最小化することである． t ⌧้ … 0.8 0.72 0.82 0.74 0.74 ͤ❆ᖜ5䠄ᅛᐃ䠅䛾䝇䝷䜲䝗❆䛾ሙྜ t+1 ⌧้ … 0.8 0.72 0.82 0.74 0.74 0.76 ้䛜1㐍䜐 ้t䛻䛚䛔䛶䠈䝇䝷䜲䝗❆䛿᭱䜒᭱㏆䛾 5䛴䛾䜢ಖᣢ䛩䜛 ้䛜㐍䜐䛤䛸䛻䠈䝇䝷䜲䝗❆䛿᭱䜒ྂ䛔 䜢ᤞ䛶䠈᪂䛧䛔䜢ຍ䛘䜛 →㛫䛻ᑐ䛧䛶❆䛜䝇䝷䜲䝗䛧䛶䛔䛟䜘䛖䛻 ぢ䛘䜛 図 1: スライド窓の概要 • リグレット：全区間 [T ] における予測者と最適エ キスパートの累積損失の差 T t=1(yt, ˆyt)− mini=1,...,M
T t=1 (yt, ξt,i). • 適応リグレット [17]：最も“ 意地悪な区間 ”I = [r, s] ⊂ [T ] における予測者とのその区間におけ る最適エキスパートの累積損失の差 sup I=[r,s]⊂[T ] s t=r
(yt, ˆyt)− min
i=1,...,M s t=r (yt, ξt,i) . リグレットは一般的な指標であり，全区間における アルゴリズムの性能を保証している．しかし，データ ストリームの傾向が時間とともに変化する場合，部分 的にアルゴリズムの性能が悪い区間が存在し，その区 間における性能を保証していない．一方，適応リグレッ トはアルゴリズムの性能が最も悪い区間に対する保証 であり，任意の区間に対する最低性能を保証している． 従って，データストリームの任意の変化に対してアル ゴリズムの最低性能を保証していると言える．
2.2
スライド窓
スライド窓 (sliding window) は時間とともに変化 するデータストリームに対してよく用いられる手法で ある．スライド窓のイメージ図を図 1 に示す．スライ ド窓は最近のデータのみ保持する．新しい例が来るた びに，スライド窓は最も古い例を捨て，新しい例を加 える．そして予測アルゴリズムはスライド窓のデータ のみを用いて予測を行う．スライド窓W の定義を定義 1 に示す． 定義 1. 時刻 t におけるスライド窓 W とは時刻 t − 1 からの最新の高々 M 個の例集合であるとする，すな わち， W = ∪t−1 j=1{(xj, yj)} ift − 1 ≤ M ∪t−1 j=t−M{(xj, yj)} if t − 1 > M表 1: スライド窓の窓幅による特徴の違い 窓幅 メリット デメリット 大 ノイズに頑健 急変に追随できない 小 急変に対応 ノイズに過剰反応 である．また，スライド窓の大きさM を窓幅とよぶ． スライド窓はその窓幅によって，表 1 のようにデータ ストリームに対する特性が変化する．窓幅が大きいス ライド窓はデータストリームの変化に頑健である．そ のため，データストリームが安定している場合に一時 的なノイズの影響を受けにくく，より一般的な予測を 行うことができる．しかしデータの傾向が急変した場 合，その変化に追随できず予測精度が悪化する．一方， 窓幅の小さいスライド窓はデータストリームの変化に 敏感である．そのため，データの傾向が急変した場合， その変化に早急に対応することができる．しかしデー タストリームが安定している場合に一時的なノイズの 影響を受けやすく，データの傾向の本質を捉えることが できず予測精度が悪化する．従って，データストリーム の傾向に応じて適した窓幅を逐次選択する必要がある．
2.3
本研究の目標
本研究の目標は，ストリームデータに対する最適な 固定のスライド窓に匹敵する予測を行う事である．そ のために，本研究ではエキスパートを用いたオンライ ン予測の枠組を用いる．具体的には，固定幅のスライ ド窓を用いた予測アルゴリズムをエキスパートと見な し，エキスパートの予測統合アルゴリズムを応用する．3
重み付き平均アルゴリズム
エキスパートを用いたオンライン予測の一つに，重 み付き平均アルゴリズム (Weighted Averaging Algo-rithm, 以下 WAA)[16] が挙げられる．WAA の動作を Algorithm 1 に示す．それぞれのエキスパートには重 みが与えられ，各エキスパートの予測値の重み付き平 均をアルゴリズムの予測値とする．アルゴリズムと各 エキスパートの予測値は正解値ytと比較され，損失 の大きさに従って，アルゴリズムは損失を被り，各エ キスパートはその重みが更新される．損失 の大きさ に従って重みを更新することにより，試行が進むにつ れて，予測精度の高いエキスパートの予測がアルゴリ ズムの予測に反映されやすくなる．その結果，アルゴ リズムの性能が向上することが期待される． Algorithm 1 重み付き平均アルゴリズム (WAA) [16] 1. w1= (M1, . . . ,M1). 2. Fort = 1, . . . , T (a) 事例xtを受け取る． (b) 各エキスパートはEiはξt,iを予測する (1≤ i ≤ M)(c) ˆyt=Mi=1wt,iξt,iを予測する． (d) 正解値ytを受け取る． (e) 各エキスパートEi の重みを更新する (1≤ i ≤ M)． wt+1,i= wt,ie −α(yt,ξt,i) M j=1wt,je−α(yt,ξt,j) . 表 2: α-指数凹な損失関数および α-指数凹を満たすた めのα の十分条件 損失関数 (y, ˆy) の値 十分条件 相対エントロピー (1− y) ln1−y1−ˆy +y lnyyˆ α ≤ 1 二乗誤差 (y − ˆy)2 α ≤ 1/2 Hellinger 距離 12((√1− y −√1− ˆy)2 α ≤ 21/2 +(√y − √ˆy)2 絶対誤差 |y − ˆy| -次に，重み付き平均の理論保証を紹介する．まず，次 の定義 2 を紹介する． 定義 2. 関数 e−α(ˆy,y) が ˆy に関して凹（つまり上に 凸）ならば，損失関数 は α-指数凹であるとよぶ． なお，α-指数凹が成り立つための α の条件を，次の 補題 1 に示す． 補題 1 ([16]). α-指数凹が成り立つための α の十分条 件は， α ≤ y(ˆy) y(ˆy)2 が成り立つことである（ただし，y(ˆy) = (y, ˆy) とす る）． 代表的な損失関数およびα-指数凹が成り立つための α の十分条件を表 2 に示す． 定義 2 を用いて，重み付き平均アルゴリズムの理論 保証を定理 1 に示す． 定理 1 ([16]). 損失関数 が α-指数凹であるならば， WAA のリグレットは α1lnM である．
t ⌧้
M
䝇䝷䜲䝗❆䠖䝃䜲䝈M M M-1… 2 1 㒊ศ❆䠖䝃䜲䝈1䡚M EM EM-1 E2 E1 㔜䜏䛝ከ ᩘỴ䛻䜘䜛 ண 図 2: WW の概要 定理 1 より，アルゴリズムは最優秀エキスパートの 予測精度に高々(1/α) ln M の定数項を加えた値で抑え られることが分かる．従って，選択可能なアルゴリズ ムが複数あり，それらの中でデータに対して良い予測 を行うアルゴリズムが不明の場合，重み付き平均アル ゴリズムの手法を用いることで，それらの中で最も予 測精度の高いアルゴリズムに匹敵する性能を得ること ができるのである．4
アルゴリズム
本章では，我々が提案するアルゴリズムについて述 べる．まず，WW(Weighted Window) を提案する． この WW は 3 節：重み付き多数決戦略のエキスパート として 2.2 節：スライド窓を用いるものである．これに より，良い予測を行うスライド窓の予測に逐次追随し， データの変化に適応することができる．次に WWH(Weighted Window with follow the leading His-tory) を提案する．この WWH は FLH [17] のエキス パートとして WW を用いるものである．これにより， 任意の区間でリグレットが保証され，WW よりさらに データの変化に適応できることが期待できる．
4.1
WW
WW は窓幅の異なるスライド窓をエキスパートとし て重み付き平均による予測を行うアルゴリズムである． WW のイメージ図を図 2 に示す．WW の大まかな流 れは以下の通りである． 1. 窓幅M のスライド窓を用意する． 2. スライド窓から，M 個の部分窓を生成する．そ れぞれの部分窓 W [k] は最近の k 個のデー タを保持する（k = 1, . . . , M）． 3. それぞれの部分窓をエキスパートとして予測を行 う．各エキスパートは部分窓が持つデータのみを 用いて予測を行う． 4. エキスパートの予測を重み付き平均アルゴリズム に従って統合し，アルゴリズムの予測値とする． エキスパートとして用いる，部分窓W [k] を定義 3 に示す． 定義 3. 時刻 t における窓幅 M の窓 W に対する部 分窓 W [k] とは，W における高々 k 個の最新の例集 合であるとする（k = 1, . . . , M）．すなわち， W [k] = ∪t−1 j=1{(xj, yj)} if t − 1 ≤ k ∪t−1 j=t−k{(xj, yj)} if t − 1 > k WW の動作を Algorithm 2 に示す．WW は重み付 き平均と同様に，各エキスパートの予測値と重みの積 の合計をアルゴリズムの予測値とする．これは，各エ キスパートの予測値に重みづけし，それらの平均を予 測値とすることと同義である．アルゴリズムと各エキ スパートの予測値は正解値 yt と比較され，損失 の 大きさに従って，アルゴリズムは損失を被り，各エキ スパートはその重みが更新される．損失 の大きさに 従って重みを更新することにより，試行が進むにつれ て，予測精度の高いエキスパートの予測がアルゴリズ ムの予測に反映されやすくなる．その結果，アルゴリ ズムの性能が向上することが期待される． さらに WW のメリットとして，スライド窓の性質 を利用して任意のデータの傾向の変化に逐次適応して 予測を行える点が挙げられる．データの傾向が急変す る場合，窓幅の小さいエキスパートの予測が反映され るように重みを更新し，データの急変に対応できるよ うにする．一方で，データの傾向が安定している場合， 窓幅の大きいエキスパートの予測が反映されるように 重みを更新し，ノイズに依存せず全体の変化を捉える ようにする．これにより，アルゴリズムはデータの変 化に適した大きさのスライド窓の予測に追随すること で，データの変化に適応して予測を行うことができる． WW の理論保証を定理 2 に示す． 定理 2. 損失関数 が α-指数凹であるならば，WW の リグレットは (1/α) ln M である． Proof. WW は重み付き平均をそのまま利用しているの で，重み付き平均の定理 1 がそのまま成り立つ． 定理 2 により，WW は最も良い予測を行うスライド 窓の予測精度と比べて，高々(1/α) ln M の差で抑えら れることが保証される．これにより，データに適した スライド窓の大きさが不明の場合でも，WW は最大窓 幅 M までのスライド窓の中で，最も良い予測を行う スライド窓に匹敵する性能を得ることができる．Algorithm 2 WW(Weighted Window) 1. w1= (M1, . . . ,M1). 2. Fort = 1, . . . , T (a) スライド窓W は最も新しい例から高々 M 個の例集合であるとする，すなわち， W = ∪t−1 j=1{(xj, yj)} ift − 1 ≤ M, ∪t−1 j=t−M{(xj, yj)} if t − 1 > M. 部分窓W [k] は最も新しい例から高々 k 個 の例集合であるとする（k = 1, . . . , M）. (b) 事例xtを受け取る. (c) 各エキスパートEiはW [i] をもとに ξt,iを 予測する (1≤ i ≤ M).
(d) アルゴリズムは ˆyt = Mi=1wt,iξt,i を予測 する. (e) 正解値ytを受け取る. (f) 各エキスパート Ei の重みを更新する (1≤ i ≤ M). wt+1,i= e −α(yt,ξt,i) M
i=1e−α(yt,ξt,i)
.
4.2
WWH
WWH は FLH のエキスパートとして 4.1 節の WW を用いて予測を行うアルゴリズムである．WWH のイ メージ図を図 3 に示す．WWH の大まかな流れは以下 の通りである． 1. 各時刻i において，その時刻を始点とするエキス パートW Wi を生成する．生成時にエキスパー ト W Wi の寿命lifetimei を設定する． 2. 各エキスパートW Wi は区間内の入力列を用い て WW による予測を行う．それぞれの WW は 最大窓幅を M とし，大きさ 1∼M の部分窓を サブエキスパートとして予測を統合する． 3. アクティブなエキスパートの予測を統合し，予測 値とする． ここでアクティブなエキスパートとは，寿命lifetimei が 1 以上であるエキスパートのことを指す．各エキス パート W Wi の寿命 lifetimeiはi = r2k（r は奇数， k は自然数）と一意に表す場合，lifetimei= 2k+2+ 1 で与えられる．エキスパートW Wiは生成時に寿命が 設定され，時刻ごとに寿命が 1 減る．寿命が 0 になっ たエキスパートはアルゴリズムの統合対象から外れる． t ⌧้ t t-i … t-j E1 Ei Ej 㔜䜏䛝ከ ᩘỴ䛻䜘䜛 ண M … … … e1 e2 eM-1 eM … e1 e2 eM-1 eM … eet-jt-j-1 e1 e2 䝇䝷䜲䝗❆䠖䝃䜲䝈M 図 3: WWH の概要 Atを時刻t においてアクティブなエキスパートのイン デックス集合とする．このとき次の性質が成り立つ． 性質 1 ([17]). 1. 任意のs ≤ t について，[s, (s + t)/2] ∩ At = ∅. 2. 任意のt について，|At| = O(log T ). 3. 任意のt について，At+1\ At={t + 1}. WWH の動作を Algorithm 3 に示す．WWH は，ま ずアクティブなエキスパートの予測のみをその重みに 従って統合する．WWH は各試行ごとに，寿命が 0 に なったエキスパートを削除し，アクティブなエキスパー トについて重みの更新・正規化を行う．次に，各試行 ごとに新たなエキスパートを追加する．新たなエキス パートの追加は，データの傾向が急変した場合に追加 したエキスパートの予測に追随するように重みの更新 を行うことで，アルゴリズムがデータの傾向の急変に 対応しやすくなるというメリットがある． さらに WWH のメリットとして，WW よりもさら に任意のデータの傾向の変化に逐次適応して予測を行 える点が挙げられる．各区間においてデータの変化に 適した大きさのスライド窓の予測に追随し，それらの 予測を統合することにより，データに適した区間で，適 した大きさのスライド窓を用いた予測に追随すること ができるからである． 次に， WWH の適応リグレットの解析を行う．まず， FLH における以下の補題を示す． 補題 2 ([17]). 任意の区間 I = [r, s] に対して，W Wr が I 中に生き残っていたとする．このとき，区間 I に おける WWH とW Wrの累積誤差の差は高々α2(lnr+ ln|I|) である． 補題 2 と定理 2 から，以下の補題が成り立つ． 補題 3. 任意の区間 I = [r, s] に対して，W Wr が I 中に生き残っていたとする．このとき，区間 I に おける WWH と任意の部分窓の累積誤差の差は高々 2 α(lnr + ln |I| + ln M) である．Algorithm 3 WWH (Weighted Window with follow
the leading History)
1. A1={1}，w1,1 = 1 に初期化する． WW を予 測器とするエキスパートW W1 を生成する． 2. Fort = 1, . . . , T (a) 事例xtを受け取る． (b) 各i ∈ Atにおいて，各エキスパートW Wi は 時刻i を始点とする WW に基づいて ξt,i を予測する． (c) アルゴリズムは ˆyt=i∈A twt,iξt,iを予測 する． (d) 正解値ytを受け取る． (e) 更新：各エキスパートW Wi (i ∈ At) の重 みを更新する． ˆ wt+1,i= wt,ie −α(yt,ξt,i) j∈Atwt,je−α(yt,ξt,j) (f) 追加：新たなエキスパートW Wtを追加する： ¯ wt+1,i= 1 t+1 ifi = t + 1, (1−t+11 ) ˆwt+1,i ifi = t + 1. (g) 削除：|At| を |At+1| に更新する．各 i ∈ At+1 において， wt+1,i= w¯t+1,i j∈At+1w¯t+1,j . 次に，補題 3 を用いて任意の区間 I = [r, s] におけ る，任意の部分窓に対するリグレットを評価する． 補題 4. 任意の区間 I = [r, s] に対して，このとき， 区間 I を全区間とした場合の WWH のリグレットは O(1 α(lnM + ln s) ln |I|) である． Proof. 性質 1 より，時刻 s および区間 I = [r, s] に 対して，ある i ∈ As が存在して，以下を満たす：(i) i ∈ [r,r+s 2 ]，かつ (ii) エキスパートW Wi は時刻i に 生成され，時刻s においてアクティブである．よって， 補題 3 より，区間 [i, s] における WWH の任意の部分 窓に対する累積損失の差は高々α2(lni + ln |I| + ln M) である． 同様にして，区間 [r, i] についても，ある i が存在 して，i ∈ [r,r+i2 ] が成り立ち，区間 [i, i] における WWH の任意の部分窓に対する累積損失の差を評価す ることができる．ここで，i や iのような時刻により， 評価すべき区間の長さは半分以下となる．よって，考 慮すべき区間は高々 log2|I| 個である．したがって，区 間 I = [r, s] における WWH の任意の部分窓に対する リグレットは高々 2
α(lns + ln |I| + ln M) · log2|I|
=O 1 α(lnM + ln s) ln |I| となる． 最後に，WWH の適応リグレットを示す． 定理 3. WWH の最適な固定窓に対する適応リグレッ トはO(ln M ln T + ln2T ) である． Proof. 補題 4 より，任意の区間I = [r, s] における最適 な部分窓に対するリグレットはOα1(lnM + ln s) ln |I| である．ここで，s, |I| ≤ T より，定理が成り立つ．
5
実験
本章では，4 章で提案したアルゴリズムの性能を測 るため，他のアルゴリズムとの比較実験を行う．まず 5.1 節で本実験の概要を述べ，5.2 節で人工データによ る実験結果，5.3 節で実データによる実験結果について 考察する．5.1
実験の概要
本実験で扱う実験データとして以下からなる 2 次元の 例集合を考える：S = {(x1, y1), (x2, y2), . . . , (xt, yt)}(1 ≤ t ≤ T )，ただし， • 事例=時刻：xt=t • 正解値=系列（時刻に対する値）：yt=value とする．そして，アルゴリズムは時刻ごとに次の時刻 の正解値を予測する． 損失関数 は二乗誤差を用いる．すなわち，(y, ˆy) = (y − ˆy)2 とする．このとき，損失関数 は α = 0.5 の時α-指数凹を満たす． 本実験では，各部分窓における予測器を最小二乗法 による線形回帰アルゴリズムとする．最小二乗法は，例 集合について各データとの二乗誤差が最小になる線形 回帰式を求め，事例xtに対する 正解値ytを予測する ものである．回帰式を ˆy = ax + b とおくと，回帰式と 各データとの二乗誤差の総和ni=1(yi− ˆyi)2が最小に なる定数a, b は次のようになる． a = ni=1(xi− ¯x)(yi− ¯y)
n
i=1(xi− ¯x)2 .
ここで， ¯x, ¯y はそれぞれの平均値を表す．
本実験で比較するアルゴリズムは以下の通りである．
• WW(Weighted Window)[提案手法]
4.1 節を参照．
• WWH(Weighted Window History)[提案手法]
4.2 節を参照．
• FLH(Follow the Leading History)[17] • ADWIN(ADaptive WINdowing)[4]
• KAARCh(Kernel Aggregating Algorithm for
Re-gression with Changing dependencies)[19]
• best window WW において最も予測精度の高いエキスパート アルゴリズム． 本実験では以下のパラメータを変化させて実験を行 う． • 最大窓幅 M 実験データの例の総数に応じて設定する． • 重み付き平均の学習率 α α = {0.1, 0.2, 0.3, 0.4, 0.5} を用いる． なお，以下のパラメータは変化させない． • ADWIN の信頼値 δ 予測精度にあまり変化がないため，δ = 0.9 に 固定． • KAARCh の学習率 a 最も良い理論保証が得られる以下の値に固定 [20]． a =Y2c2T (T − 1)/2s(T )
5.2
人工データによる実験
本節では以下の人工データを扱って実験する．それ ぞれの人工データは全部で 1000 step の入力列からな り，5.1 節で述べた例集合に従って生成する． • radical：時刻 t = 500 で値が急変する入力列（図 4） • slope：時刻 t = 300 から t = 700 にかけて緩やか に値が変化する入力列（図 5） • temporal：200step ごとに一時的な外れ値（入力 列の傾向に合わない値）が発生する入力列（図 6） • random：変化点・変化が共にランダムな入力列 （図 7） これらに正規乱数（分散：0, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3， 平均 0）をそれぞれ加えた例集合を生成する． 各人工データに対するアルゴリズムの累積損失の変 化を図 4，5，6，7 に示す．ここでは代表的な実験結果 として，正規乱数の分散var = 0.05，WW・WWH の最 大窓幅M = 10，WW・FLH・WWH の学習率 α = 0.5 として行ったものを示す． 全ての人工データに対して，WWH の予測精度が最 も良いことが分かる．また全ての人工データに対して， WW は best window と比較してほぼ同程度の予測精 度であることがわかる．一方，その他の比較アルゴリ ズムは実験データに対し性能が良い場合と悪い場合が あり，良い場合でも WW と同程度の予測精度である ことがわかった．特に，FLH は時間が経つほど，デー タの変化に対する適応度が悪くなっており，後半のス テップで変化が起きる実験データに対しては予測精度 がかなり悪化していることが分かる．また，ADWIN は temporal のような一時的なノイズが発生した場合 に予測精度が悪化していることがわかる．5.3
実データによる実験
本節では以下の実データを扱って実験する． • nikkeiavg：日経平均株価の日足値 期間 1984/1/4∼2009/8/27延べ 6311 営業日にお ける日経平均株価の日毎の終値（図 8） これらの実データを比較アルゴリズムに与えた場合 の累積損失の変化を図 8 に示す．ただし正規乱数の分 散var = 0.05，WWA・WWH の最大窓幅 W = 50， WWA・FLH・WWH の学習率α = 0.5 として行った． nikkeiavg に対して，best window に次いで WW と WWH が最も予測精度が高くなった．特に，nikkeiavg は傾向の変化が激しく，その他の比較アルゴリズムは 傾向の変化を捉えることができなかったと推測できる． WW と WWH は逐次重みの更新を行うことで，best window に匹敵する予測精度を示していることがわかる． 今回，特に人工データにおいて WWH がかなり良い 予測精度を示した．これには以下の 2 つの要因が考え られる． • step ごとに適した大きさのスライド窓をいくつ か選択して予測を行っている • 区間ごとに WW を実行することで，傾向が変化 した場合に過去のデータに影響されない WW が 存在する 特に 2 点目の区間ごとに WW を実行することにより 予測精度が大きく変わったと考えられる．従来の WW では，傾向が変わった場合でも過去のデータの傾向に 従って設定された重みを用いて予測を行わなければな らなかった．今回 WWH は区間ごとに WW を実行す ることで，傾向が変わった時点で新たに WW を実行す ることにより，過去のデータの傾向に依存しない重み （一様分布）から予測を行うことができるため，データ の変化に対する適応度が向上したと考えられる．0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 500 600 700 800 900 1000 value step radical 0 2 4 6 8 10 0 100 200 300 400 500 600 700 800 900 1000 cumulative loss step FLH ADWIN WW best window WWH 図 4: radical データ（左）および各アルゴリズムの累積損失（右） 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 500 600 700 800 900 1000 value step gradual 0 1 2 3 4 5 6 7 8 0 100 200 300 400 500 600 700 800 900 1000 cumulative loss step FLH WW ADWIN best window WWH 図 5: gradual データ（左）および各アルゴリズムの累積損失（右） 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 500 600 700 800 900 1000 value step temporal 0 2 4 6 8 10 12 14 0 100 200 300 400 500 600 700 800 900 1000 cumulative loss step ADWIN FLH WW best window WWH 図 6: temporal データ（左）および各アルゴリズムの累積損失（右）
0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 500 600 700 800 900 1000 value step random 0 1 2 3 4 5 6 7 8 0 100 200 300 400 500 600 700 800 900 1000 cumulative loss step FLH ADWIN WW WWH best window 図 7: random データ（左）および各アルゴリズムの累積損失（右） 5000 10000 15000 20000 25000 30000 35000 40000 0 1000 2000 3000 4000 5000 6000 value step nikkeiavg 0 2e+008 4e+008 6e+008 8e+008 1e+009 0 1000 2000 3000 4000 5000 6000 cumulative loss step FLH ADWIN WW WWH best window 図 8: nikkeiavg データ（左）および各アルゴリズムの累積損失（右）．
6
結論
本論文では，エキスパートを用いたオンライン予測 に基づくスライド窓への新たなアプローチを提案した． まず，複数の窓幅の異なるスライド窓による予測を統 合する WW を提案した．WW は，最も予測精度の高 い固定窓に対する累積損失の差がO(ln M) で抑えられ ることを示した．さらに，区間ごとに WW を実行し， それらの予測を統合する WWH を提案した．WWH の 解析により，WWH は任意の区間で実行された WW の 任意の固定窓に対し，累積損失の差（適応リグレット） がO(ln M ln T +ln2T ) で抑えられることを示した．ま た，計算機実験により，人工データ・実データともに WWH が最も予測精度が高いことを示した． 今後の課題として，WW の重みの更新に，Share Up-date 法 [8] や Mixing UpUp-date 法 [11] を適用して，k-分 割リグレットに対する保証と比較実験を行いたい．参考文献
[1] S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
[2] 徳山豪. オンラインアルゴリズムとストリームア ルゴリズム. 共立出版, 2007.
[3] C.C. Aggarwal. Data streams: models and
algo-rithms. Springer-Verlag New York Inc, 2007.
[4] A. Bifet and R. Gavald`a. Learning from time-changing data with adaptive windowing. In
Pro-ceedings of the 7th SIAM International Confer-ence on Data Mining (SDM’07), pp. 443–449,
2007.
[5] J. Gama, P. Medas, G. Castillo, and P. Ro-drigues. Learning with drift detection. In SBIA
Brazilian Symposium on Artificial Intelligence,
pp. 286–295, 2004.
[6] R. Klinkenberg and T. Joachims. Detecting con-cept drift with support vector machines. In
Pro-ceedings of the Seventeenth International Con-ference on Machine Learning (ICML), Vol. 11,
2000.
[7] G. Widmer and M. Kubat. Learning in the pres-ence of concept drift and hidden contexts.
Ma-chine learning, Vol. 23, No. 1, pp. 69–101, 1996.
[8] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge Univ Pr, 2006.
[9] M. Herbster and M.K. Warmuth. Tracking the best linear predictor. The Journal of Machine
Learning Research, Vol. 1, pp. 281–309, 2001.
[10] J.Z. Kolter and M.A. Maloof. Dynamic weighted majority: A new ensemble method for tracking concept drift. In Proceedings of the Third
Inter-national IEEE Conference on Data Mining.
Cite-seer, 2003.
[11] O. Bousquet and M.K. Warmuth. Tracking a small set of experts by mixing past posteri-ors. The Journal of Machine Learning Research, Vol. 3, p. 396, 2003.
[12] J.Z. Kolter and M.A. Maloof. Using additive ex-pert ensembles to cope with concept drift. In
Proceedings of the 22nd international conference on Machine learning, p. 456. ACM, 2005.
[13] P. Auer, N. Cesa-Bianchi, and C. Gentile. Adap-tive and self-confident on-line learning algo-rithms. Journal of Computer and System
Sci-ences, Vol. 64, No. 1, pp. 48–75, 2002.
[14] M. Herbster and M.K. Warmuth. Tracking the best expert. Machine Learning, Vol. 32, No. 2, pp. 151–178, 1998.
[15] N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and
computa-tion, Vol. 108, pp. 212–212, 1994.
[16] J. Kivinen and M.K. Warmuth. Averaging ex-pert predictions. In EuroCOLT ’99, pp. 153–167, 1999.
[17] E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In
Pro-ceedings of the 26th Annual International Con-ference on Machine Learning. ACM New York,
NY, USA, 2009.
[18] V. Vovk. Aggregating strategies. In Proceedings
of the 3rd Annual Workshop on Computational Learning Theory, pp. 371–386, 1990.
[19] S. Busuttil and Y. Kalnishkan. Weighted kernel regression for predicting changing dependencies. In ECML, pp. 535–542, 2007.
[20] S. Busuttil and Y. Kalnishkan. Online regression competitive with changing predictors. In ALT, pp. 181–195, 2007.
