平成藷岱率慶
≡塵東学東学院志学研究科 博忠節期課饗情報濫学専政
森 口 鞍 草三∴
適応的分位点回帰分析に関する研究
[ 21.2. 3
手工･､̀､etT,亡Tl奴ヨ訂y‑I/::.;:'
三重大学大学院工学研究科情報工学専攻 博士前期課程2008年度修了
森口 浩行
:̲
tTl:人′､;:人′､jJ':E;I;i I.̲ノ?'･'LrL)r･']JtJi千:f･
目次
目次
第1章 はじめに 1.1研究の背員
1.2 研究の目的および概要 第2章 分位点回帰分析
2.1分位点.
2.1.1分位点と平均値の比較.
2.1.2 条件付き分位点.
2.2 分位点回帰分析.
2,3 線形分位点回帰分析
2.4 二次正則化項付き非線形分位点回帰分析 2.4.1双対問題の導出.
2.4.2 カーネルトリック.
2.4.3 Mercerカーネル.
2.5 カーネル分位点回帰分析.
2.5.1最適性条件
第3章 適応的カーネル分位点回帰分析 3.1感度.
3.2 データの挿入.
3.3 データの削除.
3.4 イベント.
3.4.1 出力イベント.
3.4.2 入力イベント.
3.4.3 イベントの同定.
3.5 適応的分位点回帰分析の計算員
:.巾二人ノ､j::人′､]t,I:院｢ノ､]1,I‑'桝先手ll･
4 4 6 6 6 7 8 9 ll iF!
12 13
15 15 17 17 18 18 19 19 20
3.6 J｡‑￠日寺の動作.
3.7 同時適応的分位点回帰分析.
3.7.1感度.
3.7.2 挿入と削除の同時実行
3.8 ランクワン更新.
3.8.1増加ランクワン更新
3.8.2 減少ランクワン更新
第4章 数値実験 4.1計算コスト
4.1.1 同時適応的回帰分析の検証.
4.1.2 ランクワン更新の検証.
4.2 ケーススタディ.
4.2.1対比手法.
第5章 おわりに
付録Aパラメータの調整 A.1クロスバリデーション 付録B最適化問題
B.1非線形計画問題.
B.2 ラグランジュ未定乗数法.
B.2.1無制約最適化問題.
B.2.2 制約付き最適化問題
B.3 双対性.
参考文献
謝辞
発表論文リスト
巾人′､)I,':人ノ';I:i,'',‑t｢ノ)t･':[T‑]f:'たf;.l･
20 22 22 24 25 27 28
29 29 29 31 33 34
38
44 44 45 46 46 49
51
53
54
図一覧
図一覧
2･1標準正規分布Ⅳ(o,1)の累積分布関数.
2.2 標準正規分布Ⅳ(o,1)の分位点関数.
2.3 BMDデータ,
2.4 丁‑ 0.05,0.570.95の分位点損失関数と最小二乗損失関数.
2.5 様々なカーネル関数での95%曲線.
3.1挿入プロセスのフローチャート
3.2 削除プロセスのフローチャート
3.3 挿入プロセスのフローチャート
4.1適応的分位点回帰分析と同時適応的分位点回帰分析でのイベントの回数.
4.2 各分位点でのイベントの平均回数.
4.3 一般的なコレスキー分解に要する時間と,そのランクワン更新に要する時間
4.4 2006年4月1日から2007年3月31日までの為替データ.
4.5 2007年4月1日から2008年3月31日までの為替データ.
4.6 対比手法1:正規分布を仮定した方法.
4.7 対比手法2:カーネル密度推定を用いた方法.
A.1 (A,J)‑(0.1,0.1)での95%曲線.
A.2 (A,J)‑(1.0,1.0)での95%曲線.
A.3 各パラメータ候補における95%曲線.
Er.:人て･'人ノ;I:ドJ;tLノ､;:脚光t;ごf‑
iii
5 5 7 8 13
21 21 25 32 32 33 35 35 37 37 40 40 43
表一覧
3.1挿入プロセスの概要
3.2 削除プロセスの概要
3,3 線形制約の関係.
4.1適応的アルゴリズムでの実行時問(sec).
4.2 逐次的アルゴリズムでの実行時間(sec).
A.1 10フォールドクロスバリデーションによる汎化誤差
A.2 学習データに対する汎化誤差
:L
Er7.I人′'j,'二人′､i::V;i IL.J､;･':桝先手Il
17 18 24
30 30
42 42
第1章 はじめに
第1章
はじめに
1
1.1研究の背景
近年,ネットワーク侵入検知システム,セキュリティ認証システムや金融データ解析において,
異常検出(Anomaly detection)と呼ばれる手法が注目を集めている.異常検出とは,観察された システムやデータの通常とは異なる振る舞いを示したとき,それを検出するものである.
異常検出が登場するより以前は,不正検出(Misuse detection)と呼ばれる手法が広く用いられ てきた.不正検出とは,観察されたシステムやデータに対して既知の不正なパターンを検出する
ものである.例としては,コンピュータウィルス検出システムでは,シグネチャと呼ばれるウイ ルスパターンを持ち,観測しているシステムなどからがウイルスパターンと同じパターンを檎
出したとき,ウイルスであるとみなす.不正疲出は,既知のパターンに対しては7非常に良いパ
フォーマンスを示す.しかし!未知のパターンに対しては対応できず,新たなパターンが発見さ れた場合は, )ミターンを更新する必要があり,不正なパターンに対して,常に事後処理しかでき ないという問題がある.
この問題に対して,異常検出においては,異常を｢通常とは異なる振る舞い｣であると定義し ているため,未知のパターンを検出できる可能性がある.
1.2 研究の目的および概要
異常検出システムは,監視するシステムの通常状態をあらかじめモデルとして作成しておき, そのシステムがモデルからの逸脱を示すとき,警告を与えることである.
異常検出をするためのアルゴリズムは様々なものが考案されており,例えばフ正常値の値を決 め,正常値から外れたものを異常値とするしきい値監コマンドの使用頻度や使用順序などから
. Lr･‑:人･､;::人ノ;;二L;I;iL.̲J､;::研''Jt1;:I‑
異常を発見する統計手法型,データの分布を求め,分布の外れ値を巽常値とする外れ値型などが ある.
本研究は,外れ値型の異常検出について,分布の外れ値の決定に関わるものである.
外れ値型の異常検出のための有望なアプローチのうちの1つは,通常状態の確率モデルを構 築することである.ある状態を観察する確率が通常状態モデルの下では非常に低い場合,異常の 兆しがあるものとして解釈される.このアプローチの利点は,通常状態からの逸脱として,前例 の無いタイプの異常を検出することができるということである.また,異常検出は常にシステム を監視するため!扱うデータは時系列データであると考える.
時系列データに対する確率モデルは広く研究されている. yt ∈Rを時間Lでの観測とする.以 下のモデルが,現実世界の多種類の時系列データについて記述することができる‥
Yt ‑ f(ytl,yト2,‑,yt̲a)+ごt, E[Et]‑ 0･ (1･1)
ここで, I :哩d ‑取は確定的な関数を表し, Etはノイズを表す確率変数である.時刻Lに おける時系列データは確率変数でありYlと表されている.過去の時系列データをまとめて
xt df (yt‑1,yt̲2,‑,yトT)Tと表すと,時刻‖こおけるデータytの分布p(yLIxt)が本課題で推定 対象となるものである.
最も代表的なARモデルではノイズを正規分布と仮定している.先に述べたように,外れ値 型異常検出では,確率モデルに使われている確率分布のテイル部分を精度良く推定することが 要求される.
本研究では,特定のパラメトリックな確率分布を仮定せずにテイル(梶)部分を直接モデル化す るアプローチを考察する.提案する方法では,数時刻前までのデータが与えられたときフ0 < T < 1
として,次時刻のデータの丁一分位点(100丁パーセント点)を予測する.例えば,丁‑ 0.01とする と,時系列が正常なとき, 1%の確率で予測値を下回り, 99%の確率で予測値を上回ることが期待 古れる.もし,これよりも極端に大きな確率で予測値を下LuJるようなことがあれば,時系列が異 常な状態であるとみなすことができる.
上述のように,異常値検出では時系列データの1%点などを推定する必要がある. P(YtlxL)の
累積分布関数をFytl訂tと表すと,この分布のT ∈ (0,1)分位点は柁♭t(T)と表される･本研究 の目的は,正常な時系列状態におけるP(Ytlxt)の1%見FyITct(o･o1),や597o点,Fy7at(o･o5),を
推定することである.さまざまな条件のもとでの分位点は条件付分位点と呼ばれ,これを条件
xi ∈Rdの関数とみなしたとき,条件付分位点関数と呼ばれる.
条件付分位点関数を推定する有用な方法に分位点回帰分析[8フ7]と呼ばれるものがある.モ デルが線形の場合[8],一般的な非線形の場合[10],ならびにノンパラメトリックな場合[9]など
▲.
･T･.:人ノ､j;:)(ノ､j;二!;J;L(A.ノ､j,I:L[L)r･JJ/t千:f･
第1章 はじめに 3
が提案されているが,本研究ではカーネル法による分位点回帰分析(KQR) [16]を用いることと する.
また,時系列データの確率モデルを構築するにあたっては,大量のデータを高速に処理し,確 率モデルを適応的に更新させていく必要がある.そのためには,最適なモデルを高速に更新でき
るアルゴリズムが必要となる.本研究の主な目的は,時系列モデルにおける条件付分位点関数を 適応的に推定する方法を提案することである.
以下では本論文の構成について述べる. 2章では,分位点回帰分析がどのような問題として定 式化されるかについて述べ,カーネル分位点回帰分析(KQR)とその最適性条件について説明す
る. 3章では, KQRの適応推定アルゴリズムを提案する. 4章では,提案手法であるKQRの適 応推定アルゴリズムの計算速度を従来手法と比較し,ケーススタディとして,現実世界の金融の 時系列データを使用した異常検出システムを例証する. 5毒で本論文のまとめとする.
A.
tTT.:人̀､iり(1j::ド′こIA.ノir':桝'たf:f･
第2章
分位点回帰分析
2.1 分位点
確率密度関数p(v)を持つvについての分布について,累積分布関数F(v) Lま以下のように表 古れる:
F(i,)‑ rnP(w)dw･
このとき, F(v)は単調増加関数であり,o≦F(v) ≦1である.今任意のv′に対するF(v′)杏,
7‑ ‑ F(,u′)としたとき,v′を分布p(,u)の7‑分位点(7‑‑quantile)という.また,累積分布関数F(v) の逆関数F 1(T)を分位点関数(quantilefunction)という.
T分位点とは,データを昇順に整列したとき,先頭から100T%の所にある値を意味する.また, 連続型の確率密度関数においてはデータの整列が不可能であるため,定積分の面積をもって表 現している.
例として,確率密度関数p(v)が標準正規分布N(0,1)の場合を考える.このとき,累積分布関 数F(v)と分位点関数F 1(71)はそれぞれ図2.1,図2.2に示される.v‑0のときF(0) ‑0.5であ
り,このときv‑oを分布p(v)の0･5分位点1であるという･また0.5分位点は中央値(median)
とも呼ばれる･分位点関数において71‑0･5となる点は, F 1(o･5)‑0であり,分布p(v)の0.5
分位点がγ‑oであることが分かる.このとき, T∈ (0,1)を分位点のオーダー(order)と呼ぶ.
分位点の特別なものとして四分位点がある.これはフ0.25分位点, o.5分位息o.75分位点に相 当する点のことを指し,それぞれ,第一四分位息第二四分位点(中央値),第三四分位点と呼ば
れる.また,分布から得た標本に対しては,標本データを昇順に整列し,先頭から10071%の所 にあるデータが標本のT分位点である.
150%分位息50%点ともいう.
A. Err.:人ノ､]':二人ノ､)I::f,'';[ LA̲J､1t,I:桝̀柁fll‑
第2章 分位点回帰分析
｣L
0
i
⊂I
ニ岩
qJ .≧巨
∈ U
｣
〔】
i
空
⊂〉
0.7
0.6
0.5
0.4
0.3
.3 .2,5 ̲2 ‑1.5 ･1 ･0.5 0 0.5 1 1.5 2 2.5 3
V
図2.1‥標準正規分布Ⅳ(o, 1)の累積分布関数
o o.1 0.2 O.3 0.4 0.5 0.6 0.7 0.8 0.9 1
で
図2.2=標準正規分布Ⅳ(o,1)の分位点関数
r l;I,こ l こ川pILLトl
2.1.1分位点と平均値の比較
分位点(とりわけ中央値)と平均値は頻繁に比較されるが,以下の点で異なる.まず,中央値と
平均値は必ずしも一致しない.先の例では,分布を対称分布である標準正規分布としていたた め,平均値と中央値が一致していた.しかし,単峰であり歪んだ分布である場合には,中央値は 平均値よりも峰の近くに存在するため,分布を表現する値として相応しい場合が多い.また,分 位点は平均値に比べてノイズの影響を受けにくい.平均値は標本データの外れ値に強く影響を 受けるが,分位点はデータ順序に関係するため,外れ値の影響を受けにくい.このことより,分
位点は平均値と比べ口/〈スト(robust)な統計量である.しかし,分位点はそれを求めるために
データを整列する必要があるため,単純計算可能な平均値よりも計算コストがかかる.
2.1.2 条件付き分位点
条件x ∈ Rdの下でのy ∈Rの分布p(yJx)について,P(yJx)のT分位点Fy7i(T)を条件付き
分位点という.これを条件x ∈Rdの関数とみなしたとき,条件付き分位点関数と呼ばれる.条 件諾∈ Rdは連続点であるため,
ylxを整列させることができず,条件付き分位点FyTi(T)を求め
ることが困難となる.そのため,条件付き分位点関数を推定する手法が必要となる.
例として,図2.3は, BMD(Bone Mineral Density)データといい,横軸に幼児の年齢,縦軸にそ の年齢での幼児の骨密度の変化量2を表している.横軸x ‑ ‑1,0, 1の時の骨密度変化量yの条
件付き分布P(ylx‑ ‑1),P(ylx‑0), P(ylx‑ 1)の形が異なることから,それぞれの条件付き 分位点が互いに異なることが読み取れる.
2.2 分位点回帰分析
条件付き分位点関数を推定する有用な方法に分位点回帰分析(QuantileRegression)[8,7]と呼
ばれるものがある.
学習データペア((xi∈Rd,yi ∈R))?=1が与えられたとき,オーダT∈ (0,1)における分位点
回帰分析は次のような最小化問題として定式化される:
n
f^T‑
argTEi,n∑仙iE!･‑iJ ‑ I(xi)),
￠丁(㍗)‑ (1‑T)lrl,ifr≦0, Tlrl, ifO < r.
2年齢と変化量のいずれも,平均o,分散1に正規化してある.
三重大学大学院 工学研究科
(2.1)
第2章 分位点回帰分析
3
●‑ヽ
てJ q)
.tgl石
≡
■.̲
⊂〉
⊂
⊂)
≡ En
‑示
⊂
【⊃̲
∽
⊂ q) ロ)
⊂ 可 .=U
q) .≧室
q) α:
2
1
0
1
2
3
2 ‑1.5 ‑1 ‑0.5 0 0.5 1
Age of Child｢en (norma一ized)
図 2.3: BMDデータ
1.5 2 2.5
7
ここで, 7はモデルクラス, rはモデルと各データとの残差(redidual),4,T(r)はT分位点につい ての損失関数(Lossfunction)をそれぞれ表している･条件付き平均を求める上での最小二乗法 での損失関数4,(r)‑喜r2と異なり,左右非対称な絶対値関数となっている･T ‑ 0･05,0･5,0･95
の損失関数と最小二乗法での損失関数を図2.4に示す.制約式における絶対値関数を簡単化す
るため, 4,T(yi‑ f(xi))に対しスラック変数(slackvariable)((ET+i,ET‑i))?=1を導入すると,式(2･1)
は次のような制約付き最小化問題となる:
n
f,{E[TEi;?}?=1妄(TET'i
I(1 I T)i;i)
s.t. yi ‑I(xi) ‑ET+i ‑ET‑i, ET+i≧0, ET‑i≧0･
2.3 線形分位点回帰分析
線型モデル:
f(x)‑ao+alXl+a2X2+‑+apxp
三重大学大学院 工学研究科
(2.2)
.2 ‑1.5 ‑1 ‑0.5 0 0.5 1 1.5 2 R8Sidua[: y
‑f(x)
図2.4= T ‑ 0.05,0 5,0.95の分位点損失関数と最小二乗損失関数
を考える.すると式(2.2)は,
n
{a,,;=oTEilP.E;}?=1妄(TE,'i
'(i ‑ T)E;i)
s.t. yi‑I(ao+alXl+a2X2+.I. +apxp) ‑ET'i ‑ETTi, ET+i≧0, EIi≧0
(2.3)
と表される.この問題は,線形の制約条件の下で線形の目的関数を最小化する問題であり,線形 計画問題と考えられる.
2.4 二次正則化項付き非線形分位点回帰分析
特徴ク即引こおける'jTU;間における線形モデルを
fT(訂)‑ PTT申(x)+ βTO (2･4)
とする.ここで, ◎は特徴空間への写像を, PT ‑ (/3rl,/3T,,.")Tは線形モデルの傾きパラメータ
ベクトルを, /ヲT｡は切片パラメータを表している.式(2.2)の分位点IhT帰推定 員に二次の正則化
T‑i:人 ■i:'ノ･∴ド;i‑l I I ■うと･:r
第2章 分位点回帰分析
項を加えたものは
n
pT琵｡≡･h[yi‑ (PTT◎(xi)+ /3T(,)]+妄,tβTTβ,1
9
(2･5)
F2ヒ⇒円
と表される.ここで,入∈ (07∞)は正則化の程度を表す正則化パラメータである.正則化パラ メータはユーザーによってJj･えられ,後述するクロスバリデーション3 A,?を利川することによっ て適切な入の探索が行われる必要がある,
2.4.1 双対問題の導出
式(2.5)は,式(2.3)と同様にスラック変数〈(ET7;I,,EI,1))?=1を導入することにより以下の最小化 問題として表される:
n
β,,㌔.,{?T･TETTi}T;1妄{TET+i
･ '1‑
T)i;i'･去^pTTpT(2.6)
s.t. yi‑(βTT◎(xi)+βT｡)‑i:i‑EI" i:i≧0, ET7≧0.
すべての制約条件が線形であり,目的関数が凸の二次式であるので,式(2,6)は凸二次計画問題 である.凸二次計画問題の具体的な解法としてラグランジュ未定乗数法4を利用する.
ラグランジュ乗数αi,r7∴77;を導入すると,ラグランジュ関数L:は‥
n
L ‑ ∑(TET･iI (トT)ET‑i)
･芸人βTTpT
i=1
n
･ ∑αi(yi‑ (PTT@(xi)+β,0)‑ ET'i
+ET‑i)
ヨ'iM
TL n
‑∑l/Ii=1 i‑･I‑≡,/,i=1 i‑:.
と表される.ここで,T77T≧oフ灯≧0である･
3付鎚A参照.
4付鎚B参照.
l ■ I I i i ト= ′L 1i
(2･7)
カルーシュ･クーン･タッカーの定理5より:
n
読‑入βT‑∑αi@(xi)‑0i=1
(')I:
∂βTO
∂￡
∂ET+i
⇔｡Tn ‑主皇αi(uxi)っE2‑il
‑∑αi‑0,i=1
‑T‑αi‑r7;‑0
⇔rl[‑71‑αi (≧0),
aaEf:i‑(1‑T)+αi‑灯‑0
⇔･T7;‑(1‑71)+αi (≧0)･
(2.8a,b, c, d)を式(2.7)に代入することで以下の式を得る‥
L‑妄{TET･i･(1‑T,ET‑i}･;A(三善αi@(xi))T(言募α‑))
n n,
+呂αiyi∑E4声il〈積αj@(xj,〉T･i@(xi)‑ ∑αiβTO邑‑〜iln
n n n n,
‑ ∑αiET'i+∑αiET‑i‑ ∑(T‑ αi)ET'i‑ ∑((1‑ T) +αi)ET‑i
i=1 i=1 i=1
1 2入
Tt ll n
∑∑α乞αj◎(xi)T◎(xj)+ ∑αi7Ji.
i‑1 i‑1 i‑i
以上より双対問題は:
1
maX ‑ ‑
((1i)r=1 2入
n n n
i=1
∑ ∑αiαJ(b(xi)T(D(xj)+ ∑αiy7:
i‑i J‑1 i‑i
n
s･t･ ∑αi‑0,αi∈卜1,T]
邑i‑il
と表される.
また, (2.8a)と式(2･4)より,T分位点関数f,(x)は‥
fT(x)‑ ;(tαi@(xi)T◎(x))･ /L3T(,
i=1
5付鎚B参照.
卜I 〜
' 〜
〜 川I1 1i
(2.8a)
(2,8b)
(2･8c)
(2･8d)
(2･9)
(2･10)
(2.ll)
第2章 分位点回帰分析 ll
と表される.
双対問題を導入する利点としては,主問題における不等式制約よりもより簡単な制約下で最
適化が行えること,写像◎が式中において内積◎(x)T◎(x)の形で存在するため,次述するカー ネルトリックにより計算が簡単化されることなどが挙げられる.
2.4.2 カーネルトリック
特徴空間への写像◎の内積を,
xの内積の関数として表現したものをカーネル関数(Kernel function)6といい7 K(xi,Xj),Ar(打xj)あるいはKijと表現する･今写像◎に対するカーネル
関数〟が存在すると仮定する.
簡単な例によりカーネル関数を説明する.二次元空間から三次元空間への写像◎を:
@;R2)R3.
(xl,LT2)‑ (zl,Z2,Z3)‑ (x…,X…rv%1X2)
とすると,写像の内積は以下のように示される:
◎(x)T◎(y)‑ (x至:x….ヽ乃xIX2)(yf,y22,vちyly2)'
‑.,･T'.I/'T'‑
･,･三.I/̲7'‑1'.IIT'･,･i,I;I/̲7'
‑ ((･Tl,･T2)(yl,y2)T)2
‑ (a'Ty)2
‑K(x,y)･
(2･12)
式(2.12)より明らかなように,カーネル関数を剛､ることで写像関数◎(x)の直接の計算を回避 できる.これをカーネルトリック(Kerneltrick)という.上記の例では◎(a)の計算は比較的に 容易ではあるが,特徴空間が高次元である場合には, ◎(x)の計算は膨大あるいは計算不可能と なる.そのため,カーネル関数を用いて写像関数の計算を回避することば,計算邑計算可能性 の観点から非常にTTi̲要となる.また,カーネルトリックを川いることで,線巧I‑･J.モデルで表される 手法を,計算量を抑えつつ,非線形に拡張することができる.
2.4.3 Mercerカーネル
上述のように,カーネル関数人r(xi,X])は写像関数◎(x)の内積として表現される･このよう なカーネル関数を作成するためには, ⅣIercerの定理と呼ばれる数理条件を満たす必要がある.
6カーネルと略すことが多い.
L 7 J )
I
≦ 川J･'J i
Mercerの起ftI･I.を満たすカーネル関数をMercerカーネルといい,代表的なカーネル例数は以下の 通りである:
線形カーネル:K(xi,諾j)‑打x],
多項式カーネル:h'(xi,諾j)‑ (a諾LTxj+ c)a, ガウシアン(Gaussian)カーネル‥H(xi,a:i)‑ eXP(‑
llxi‑Xjll2
2cT2
シグモイドカーネル‥Ar(xi,a,i)‑ tanh(｢′打x]I 6).
また,ガウシアンカーネルはRBF(Radial Basis Function)カーネルともいう.図2.5にこれらの カーネル関数を用いたときの分位点曲線を例示する.
2.5 カーネル分位点回帰分析
今写像◎は,カーネル関数A'による再生核ヒルベルト空間(RKHS:reproducing kernel Hilbert space)への写像であるとする.カーネルトリックを当てはめることで,式(2.10)は以下のよう に表される:
Tl (7 T(
{T}aa‑云∑∑aiajK(xi,Xj)i‑1 J‑i '∑αiyii‑1
n
s･t･ ∑αi‑0,αi∈[T‑1,T].
i=1
また,式(2,ll)は以下のように表される‥
fT(x)
‑去(皇aiK(xi,X)罰≠室i! +αo),
1
(2･13)
(2･14) 但しn() ‑A/3T()とした,
カーネル関数を持つ分位点tHl帰分析をカーネル分位点回帰分析(KQR:Kernel Quantile Re‑
gression)と呼ぶ.
1, I
. j
.川 Il
第2章 分位点回帰分析
Ago d Ch･hlrEd11nOTT7taLzod)
(a)線形カーネル
入=1.0
O.5 Ap Qr ChlUrw try)rTTldlZ血1)
(c)ガウシアンカーネル (A,a‑)‑ (1･0,1･0)
召
i 2
2
i
旨口
空‑1
葛
･1.5
Ago oI Ch･klren (plmlEZ8d】
(b)多項式カーネル (A,a,c,d)‑ (1.0,110,110,3)
2 ‑0̲5
A白8CT Chlurql (rurnah7d)
(d)シグモイドカーネル (A,↑.♂)‑ (1･0,0･5,2･0) 図 2.5:様々なカーネル関数での95%曲線
13
2.5.1 最適性条件
次に問題(2.13)における最適性条件を導出する.この問題にj引ナるKKT条件7は以下に表さ
れる:
ET+i≧0, ETLi≧0,
77;≧0, T7{≧0, ET+iT7[‑ ET+i(T‑ αi)‑ 0, E三T7{‑ETAi((1‑T)+什i) ‑0･
7付錨B参照.
ノ､ ｣ /､
i∴I･ノl.1 l ′ン‑‑,
ここで, yi > I,(xi)ならば,残差yi‑fT(xi)は正の値であるから7式2･2より, ET+i>ETJi̲> 0で あり, yi < fT(xi)ならば,残差yi‑fT(xi)は負の値であるから7EItL,>E,i;,≧ oだから‥
αi ‑ (711yi> j'T(xi)), αi‑(T‑ 1lyi<fT(xi)).
以上をまとめると,この間題の最適性条件(KKT条件)は‥
αi‑(7‑ lyi >fT(xi)),
αi ∈([7‑‑1,71]Iyi‑fT(xi)), αi‑(7‑‑1 ∫yi<fT(xi)),
云αi‑0u‑il
(2.15a) (2.15b) (2.15c) (2.15d) と表される.
まず,条件(2.15a)は,モデルより上方のデータに対応するラグランジュ乗数αi,最適解におい て正の値丁を持つことを意味する.次に,条件(2.15c)は,モデルより下方のデータに対応するラ グランジュ乗数αi,最適解において負の値71‑ 1を持つことを意味する.また,条件(2.lらb)は7 モデルに一致しているデータに対応するラグランジュ乗数αi,最適解において閉区間【71‑1,71]
のいずれかの値を持つことを意味する.そして,条件(2.15d)は,それらのαiの総和は最適解に おいて0であることを必要としている.
この最適性条件は以下のように考えられる:
モデルより上方のデータにおいては,正の値71を持ち,下方のデータにおいては,負の値7‑‑ 1
を持つ.それらの総和がoとなるようなfT(x)が最適解である.上方と下方のデータのαiの総 和がoとなるとき,学習データ数がNとすると,下方のデータの割合sは:
T(llS)N+(7‑‑1)sN‑0
より,5‑71となる. 71は分位点のオーダーであり,このことは,最適なfT(x)の下方に,7‑の割合 のデータが存在することを意味する.
そしてこれらは,分位点の定義に矛盾しない.
また,条件(2.15b)は,データ数NによってはTNが整数になるとは限らないため,そのとき の整合性を満たすためにあると考えることが出来る.
･ri二人ノ]‑,I:人ノ1t‑'▲∫/,'J;:Lノ､;:fiji･I/J/t:I;:i‑
第3章 適応的カーネル分位点回帰分析
第3章
適応的カーネル分位点回帰分析
15
時系列などの時間とともに変化するデータを解析するときっその時間変化を考慮し,時間ととも
にモデルを更新する必要がある.一般に,式(2.10)の問題を解き,最適解を求めるとき, 0(n3) の計算コストを必要とする.しかし,時系列を扱うとき必要となるモデル更新とは,大量の学習
データに巌新のデータを一つ追加する,あるいは最古のデータを一つ削除する似合を指すこと
が多い.大量のデータに対してデータを追加あるいは削除するためだけに, 0(n3)の計算コスト を必要とするのでは効率化の観点から適切ではない.そのため,モデルを適応的に更新するアル
ゴリズムが必要である.すなわち,ある訓練データがモデルに追加あるいは削除されるときに, 直前の最適解をもとに,新たな最適解へと効率的に更新する必要がある.サポートベクターマシ
ンに代表されるカーネルマシンの適応的な史新については, [3]にて初めて研究され,その後他 のカーネルマシンへ適応された【12].本研究ではそれらのアプローチを分位点回帰問題に適用 する.適応的な処理を実現するカーネル分位点回帰分析手法を適応的(カーネル)分位点回帰分
析(Adaptive Kernel Quantile Regression)と呼ぶ.
3.1 感度
消去,挿入する対象のデータの添字をpとし,データを(xpフyP)と表す1･まず第一に, αpの微
少変動に対する, )ミラメータ(αi)i=0,1,...,nの感度を分析する･ここでパラメータ(αi)i=0,1,...,nの 感度とは,最適条件(2,15a)ないし(2･15c)の下で,)ミラメータをαpの微少変動させたとき, )ミラ
メータ(αi)i=0,1,.‥,nがどれだけ変化するかを表す数値である･またpを含め和制約(2.15d)を満
たしている必要がある･このような制約の下, αpは,微少変動△αpを与えたときαp ‑αp+△αp
となり,それに伴ってフ,i‑0,1,‥.,nについてαi‑αi+△αiとなる.
1明瞭化のために,p≠(1,2,...,n)とする.
･r･:人.‑)l^'')(′､j,':rJ'/;i‑二r1.J､j,I:1T)f･JILH:ごト
準備として次のような添字集合を定義する:
I｡dgf(ilyi‑fT(xi)? T‑1≦αi≦T), I+df(i Iyi>fT(xi), αi‑T), I̲dgf(i lyi<fT(xi), αi‑T‑1).
式(2.15a)と式(2.15c)より,
△αi‑0, ∀i∈I+uI̲
となる.そして,式(2.lらd)を満たすためには,
∑△αi‑ ‑△αp
i∈Io
であることが必要である.また式(2.15b)より,
yi ‑去〈皇(αj+△αj)Kij･(α｡+△α.)),∀ij‑1 ∈ 1.
と表すことが出来る.この式は,式(3.1)を考慮すると,
△αo + ∑△αjKij‑ ‑Kip△αp
jEIo
と表すことが出来る.
式(3.2)と式(3.3)をまとめると,以下のIIol+1変数の連立一次方程式となる2‥
0 1 1 1
1 Kll K12 Klrlor
1 A'lloLI KIIoL2 ･･･ KIIoILIoL
△αo
△α1
左辺行列,左辺ベクトル,右辺ベクトルをそれぞれA, △α, bとすると,
A△α ‑ b△αp
と表される.そして,△αは,
△α ‑ A‑1b△αp
(3･1)
(3･2)
(3･3)
× △αp. (3･4)
(3.5) と表される･このときベクトル△α丁‑ ‡αoフCkl,‑a/II｡l)は,αpの微少変動△αpに対する
(αili∈ Io)の感度(△αili∈Io)を示す感度ベクトルであり,それらは△αpの線形式となること
が分かる.
2以下では,表記を簡L削こするため, 1,2,…,L(o[∈Ioとなるようデータが並び朽えられているものとする.
̀. trT.二人′ゝ1tJ':人′､;!'1,'J;L卜､)I::川J')i:[JE
第3章 適応的カーネル分位点回帰分析 17
3.2 データの挿入
ここでは)新たなデータを挿入するプロセスについて言及する.新たに挿入するデータを
(xp,yp)とする.モデルがn個のデータを保持しているとすれば,新たに挿入するデータを(xp,yp) はn+1個口のデータである.
データの挿入は! (xp,yp)に対応するαpを,最初はモデルf,(x)に影響を与えない,すなわち
α岩‑0であるものとして扱い,これをα芸ptまで変化させることで達成される･ここで,αpoptと
は, (諾p,yp)が挿入された後のαpの最適値である.また7αpを変化させる課程で!他のパラメー
タ(αi)?=oについては,感度(3.13)に従って変化させるため,最適性は保たれる,
最適値α芸ptとは,yp > fT(xp)ならば条件(2･15b)よりT, yp < fT(xp)ならば条件(2･15c)よ り7‑‑1である･また, (xp,yp)がモデルの上に存在し,yp ‑ fT(xp)となることがあれば,条件 (2.15a)より最適性を満たすことになる.表3.1に挿入プロセスの概要を示す.
表 3.1:挿入プロセスの概要
yp>fT(Xp) 0 T + yp<f,(xp) 0 丁‑1
yp‑fT(Xp) 0 [T‑1,T] 0
3.3 データの削除
挿入の場合と同様に,新たに削除するデータを(xp,yp)とする.モデルがn個のデータを保持 しているとすれば,新たに削除するデータを(xp,yp)は,そのn個のデータの内の一つであり,削 除後モデルの保持するデータ数はn1 1となる
データの削除プロセスは,挿入プロセスとは反対の課程により達成される.
すなわち, αpについては,削除開始時には最適条件(2115a)ないし(2･15c)のいずれかを満たし
ているためα呂ptからαg‑oに変化させることによりデータの削除が実現される･また,挿入の
場合と同様に,
αpを変化させる課程で,他のパラメータ(αi)i?=｡については,感度(3113)に従っ
て変化させるため,最適性は保たれる.表3.2に削除プロセスの概要を示す.
Err:人ノ､j:'ノ('1)t･':1,r'J'LF‑ ､]t･I'1JTA)i:I/)i:手I‑
表 3.2:削除プロセスの概要
yp>fT(Xp) 丁 0
yp<fT(Xp) T‑1 0 +
yp‑fT(Xp) [T‑1,T] 0 sign(‑α芸pt)
3.4 イベント
消去ならびに挿入の過程において, αpの値をH的とする値まで単調増加あるいは単調減少さ せる.
また7モデルが保持するデータとモデルとの残差の符号sign(yi‑ fT(xi))は+, 0, ‑のいずれ かの値をとる.式(2.14)からも分かるように, αpの増減に従って,モデルfTも連続的に変化し ていくため,集合Io, I+, I̲の要素が変化する可能性がある.そのため,残差の符号の変化を捉
え,それらを適切に処理する必要がある.残差の符号の変化に従って,集合Io, I+, I̲の要素が 変化することをイベントという.
ここで,イベントを出力イベントと入力イベントに区分する.
3.4.1 出力イベント
出力イベントは,αpの更新時にαi,i∈Ioについて,7‑あるいは7‑‑1となることによって発生 する.つまり,集合I.の要素iについて,αi‑7‑あるいは,αi‑7‑‑1のいずれかになることに
よって,集合I+あるいはI̲の要素に変化することを指す.今,
△αp+聖
∫(a.Tl)Tb>O111111
maX
(ai 1)Tb<0
〈 i
7‑‑αi
(all)Tb
7‑ αi
(all)Tb
),if△αp > 0,
i,if△αp<0 (3'6)
と定義する･ここで(aJl)は,A‑1の(i+1)番目の行ベクトルである･△αp‑△αp'であるとき, Ioのメンバーの一つがI+に移動する.同様に,
△αp‑dgf
I(all)Tb<O111111
maX
(aJl)Tb>0
i
i(all)Tb
if∠1αp> 0,
if△αp < 0.
△αp‑△αp‑であるとき, (oのメンバーの一つがI‑に移動する.
･rT,:人ノ､;'･'人ノ､J‑'二ぎ,'J;t二卜.､1tJ':[T‑)f='たt;こト
(3･7)
第3章 適応的カーネル分位点回帰分析 19
3.4.2 入力イベント
データ(xi,yi),i∈I十UI̲の残差がoになるとき,人力イベントが発生する･つまり,集合I+
あるいはJ̲の要素iについて,データ(xi,yi),i∈I+UI̲の残差がoになることによって,集合 Ioの要素に変化することを指す.集合Ioの要素に変化した直後のαiの値は,直前にiが集合I+
の要素であったならばαi‑Tであり,直前にiが集合IIの要素であったならば(̲ti‑7‑‑1で ある.
(xi,yi),i∈I+uI‑の残差r(xi)は, △αpの線形式として以下で表される‥
r(xi)‑ yi lfT(xi) +△fT(xi))
‑ yi一三(i(αj･△αj)Kidj‑1 ･ (α｡+△α｡))
‑ ,yi‑
fT(xi)一三(f△ajKijjEIo ･ △αpKip ･ △α.)
‑ yi ‑
fT(xi)一三(Kip･c[A‑1b)Aαp･
ここで, ci‑(1,Kli,･･･ ,K(Iori)Tである･
入力イベントが発生するときの△αpの値は,
△αzndf ∫iET.1un(̲(△α芸IAa芸≧0), if△αp '0, iET.aut(△α芸l△瑠≦0), if△αp < 0
(3･8)
で与えられる･ここで, A噌は,データ(a,i,yi)の残差がoになるときの△αpの値であり,次式
で与えられる:
｣.I;::‑ A(yi‑ fT(xi))
Kip +
c[A11b' (3.9)
3.4.3 イベントの同定
式(3･6)ないし式(3.8)をまとめると,イベントは△αpが以下の値を取るときに発生する:
△αzvcntdlf imin(△αp=7△αp+,△αp‑,△α;n),if △αp> 0, max(△αp=,△αp',△αpT,△αtn),if ∠1αp< 0･
ここで, △αp=は,挿入/削除プロセスでのαpの目的とする値3と現在のLtpとの差を示し,この値 が選択されたとき,挿入/削除は適切に達成されたことを示す.
3挿入プロセスならば(ずt,削除プロセスならば(セg‑0
Er･:人ノ､;･':)(ノ､;･':r;t l▲̲J､;::LT)I‑LJ)tトI
また,挿入プロセスにおいて, (xp,yp)の残差がoになったとき,p∈ Ioとなり鼓適性は達成さ れるので,プロセスを終了する.挿入プロセスと削除プロセスの簡単なフローチャートを図3.1
と図3.2に示す.
3.5 適応的分位点回帰分析の計算量
これら一連のプロセスに必要とされる計算葺副ま,感度(3.13)の計算に()(IIol3),出力イベント (3.6),(3.7)の計算に0(IIol2),入力イベント(3･8)の計算に0(n2)である･
感度(3.13)の計算は後述するランクワン更新を用いることで,0(llot2)へ減少することが出来 る.よって,適応的分位点回帰分析を用いて,データの挿入,削除を行う際必要となる計算量は,
0(n2)である.
3.6 Io‑￠時の動作
入力イベントが起こることによって, Ioが空集合￠になる可能性がある. Ioが空集合である とは,モデル上に一致する訓練データが一つもないことを示す.このとき先に示した方法ではう まく動作しないため,モデルfT(x)の切片項αoを変化させることによって,最適性条件を満た した上で,新たなデータをIoに含める.
まず,10‑￠になる畝一つのデータがloにあるときの△αは式(3.4)より‥
(三;:)‑ (Kll二KIp)× Aαp･
注目すべきは△α1の符号である. αpが単調増加する状況においてはα1は単調減少し, α1 ‑ 7‑‑1 の値をもって,1.から出る. (セpが単調減少するときも同様に,α1‑TによってIoから出る.
また, αpが単調増加する状況においての, αoの変化分△αoについて, △αo < 0とすると,直前
にIoから出たデータ(xlast,ylast)は,yl｡st > fT(a,last)かつ,α1ast ‑ T‑ 1となり,最適性条件に矛 盾する･よってαpが単調増加する状況においては△αo>0となるI
同状況において△α｡を変化させたときの残差は次式のとおりである:
yk‑fT(xk)
‑yk一言(皇aiKik･α｡+△α｡).E!当il
各データ(xk,1Jk)に対して残差がoとなる△αokは‥
△nok ‑A(7Jk ‑ fT(xk))･
Fr･.二人ノ､;,I:)(1､;;'[こ';t卜､;:Ii)E'')tL:.料‑
第3章 適応的カーネル分位点回帰分析
図 3.1:挿入プロセスのフローチャート
図 3.2:削除プロセスのフローチャート
Err:)(､;･':)( ̀､;,I:i;I/'[三卜′､i,I:I;)Il一:,tr.T;:ト
21
△αoは次式で与えられる:
△αo ‑mkin(△｡ok[yk･> fT(xk)) △αp > 0･
この式は最小の正の残差を持つデータ((xmin,ymin)とする)がIoに入ることを意味している.〔上o の変化前はαmin ‑ 71であり, αoの変化後に残差がoになるが, αmin ‑ 71は,最適性条件に矛盾
しない.
αpが単調減少するときも同様に, △αo <0となり, ∠1αoは次式となる‥
△αo ‑mkaX(△αoklyk< fT(xk)) △αp '0･
3.7 同時適応的分位点回帰分析
ここまで,カーネル分位点回帰分析に対して,新たなデータを‑つ追加する場合と,データを 一つ削除する場合の最適解の変化について述べてきた.時系列データを解析する際には,新しい データを順次追加し,それに伴って古いデータを削除することでモデルが保持するデータは常 に一定に保つことが多い.適応的分位点回帰分析を用いて,データの追加と削除,それぞれ別の プロセス行うことで,データ数を一定に保つことが可能である.ここでは,一度のプロセスにお いて,データの追加と削除を同時に実現する方法について述べる.データの追加と削除を同時に
実現するような適応的分位点回帰分析を,同時適応的(カーネル)分位点E]帰分析(Simultaneous
Adaptive Kernel Quantile Regression)と呼ぶ.
3.7.1 感度
ここではっ削除するデータの添え字をp,新たに追加するデータの添え字をqとし,データを それぞれ(xp,yp), (xq,yq)とする･
通常の適応的分位点回帰分析の場合と同様に, αp, αqの微少変動に対する, )ミラメータ(α･i)i=0,1,…,n の感度を分析する.式(3.2)と同様に,
∑△αi‑‑(△αp+△αq)
iEIo
であることが必要である.また,式(3,3)と同様にして,
△αo + ∑△αjKij‑ ‑(Kip△αp+ Kiq△αq)
jEIo
巾人ノ､;:メ(メ?''[:I;〔二卜､i;ニ[T)r'たT::!･
(3･10)
(3.ll)
第3章 適応的カーネル分位点回帰分析
と表すことが出来る､
式(3.10)と式(3.ll)をまとめると,以下のIIoJ+1変数の連立一次方程式となる‥
0 1 1 1
1 Kll H12 KIJIoE
1 KIIoII KLIol2 I‑ KIIo[LIol
｣′■..
｣.‑l
‑i] ‑iJ
‑KIp IKIp
‑KIZolp ‑KLIolq
23
(AAa?qp.)(3･12)
左辺行列,左辺ベクトル,右辺行列をそれぞれA, △α, Bとすると,
A△α ‑ B
(三;;)
と表される.
αpの微少変動△αpに対する(αi(i∈ Io)の感度(△αifi∈Io)を示す感度ベクトル
△αは,
･α ‑ A‑1B
(三;;) (3･13)
となり, △αp, △αqの線形式となることが分かる･
しかし,感度ベクトル△αは△αpと△αqの多変室に依存し, △αp, △αqのいずれも単調増加 あるいは単調減少であるが, △αpと△αqとの問には整合性が無いため,その変動は一意に定ま
らないtそこで, △αpと△αqとの間に以下のような線形制約を与える‥
△αq‑ z△αp･
この式を,式(3.12)に代入することで,以下の連立一次方程式を得る:
0 1 1 1
1 1{11 K12 h'1(Ior
1 Ar[Io[I K[Iol2 ･‑ KIIoIIIol
△αo
｣‖1
ー(1+I)
‑(A,1p+ zKIp)
‑(KII.[p+ ZKII.[q)
(3.14)
× △αp･ (3･15)
右辺ベクトルをbとすると, αpの微少変動△αpに対する〈αili∈ Io)の感度(△αili∈ Io)を示
す感度ベクトル△αは
△α ‑ A11b△(土p
となり, △什q‑Z△什pの制約により,単変Ifii△αpの線形式となった･
Fr･:人ノ､;::人ノ､j二:ド′'亡卜J､;':川J)tr.t::!‑
![表 3.2:削除プロセスの概要 yp>fT(Xp) 丁 0 yp<fT(Xp) T‑1 0 + yp‑fT(Xp) [T‑1,T] 0 sign(‑α芸pt) 3.4 イベント 消去ならびに挿入の過程において, αpの値をH的とする値まで単調増加あるいは単調減少さ せる](https://thumb-ap.123doks.com/thumbv2/123deta/5924957.2055712/24.893.288.616.217.386/削除プロセス概要丁+イベント消去ならび挿入過程おいあるい.webp)
