このページはしましまが人工知能学会 第1回データマイニングと統計数理研究会 に参加してとったメモです.私の主観や勘違いが含まれていたり,私が全く分かってなかったりしていますので,その点を注意してご覧ください.誤りがあれば,指摘してください.
「知識基盤形成のための大規模半構造データからの超高速パターン発見」†
有村 博紀(北海道大学大学院情報科学研究科)
半構造データ (semi-structured data;SSD):大規模,ヘテロな集団,弱く構造化されたデータ
- 高速で頑健なSSD用のマイニング:既存手法は直接的にはSSDに適用できない.
- efficient(多項式時間で計算)や頑健(仮説への多少のずれはOK)
→ 実用的には効率も頑健性も不十分なレベル
- ABC*DEF のような,gapを含むパターンへのマッチを考える.
- impurity関数(エントロピーやGini)を考えて,正例と負例の含有率について,その関数を最大化するようなものを選ぶ.
- suffix arrayを利用したヒューリスティックなアルゴリズム
- グラフや木への拡張
「統計的因果推論と因果探索」†
狩野 裕、宮村 理(大阪大学大学院基礎工学研究科)
無作為化実験†
- 例:「喫煙 ⇒ 肺ガン」
- 動物実験:強制喫煙群と喫煙なし群をつくる→後に肺ガンになったかどうか調べる
- 2群への割り当てをランダムにすることで,過去の履歴を確率的にバランス化
- 人間では倫理的に問題→観察研究たよらなくてはならない
観察(or 相関的)研究†
- 観察研究の方法
- 問題点
- 未観測の状況が生じる
- サンプルセレクション
- 測定誤差
第3変数とその役割†
- X→Y の関係以外の第3の変数
- 交絡変数(二つの枝がでる),合流点(二つの枝が入る),中間点(通過)
因果探索†
- 可能な因果のモデルを,指標(統計量)で比較して,良いものを選ぶ
- 同値(統計量が同じ)になるモデルが出てしまう
- 統計的問題(サンプルの問題や測定誤差)
- 変数には何を用いるべきか
- アルゴリズム上の問題(線形・非線型など)
因果の方向を決める†
- 第3変数との関わりで決める
- 自然に決まる場合と,能動的に研究者が選ぶ(操作変数(instrumental var.)場合
- 線形モデル+非正規誤差 / 非線形モデル + 正規誤差
- 相関係数では因果の方向は決まらない
- 同値モデルの問題から考えると…
X→Y と Y→X が同じ統計量
- 第3変数 Z の導入
- Z→X&Y→X と Z→X→Y を考えて,それぞれの因果の相関を見ることで,X→Y と Y→X の一方を選択する.
- x=B e: 未観測の誤差 e だが,独立性の仮定をおいてBを推定する
- ICAと使うか,高次モーメントを使う方法
- XからYを導くモデルと,YからXを導くモデルを二つ作り,それぞれでICA
- うまく分解されたら独立なので,独立でない方の因果関係があると考える
X1=β X2 + γ X2^2 + e1 VS X2=β X1 + γ X1^2 + e2
- 正規に近い方のモデルを良しとする(前者が良ければ X2→X1)
交絡変数†
- 交絡変数:原因と因果の両方の原因になる第3変数
- 交絡変数の問題点
- 因果によって相関が生じるのではなく,交絡変数によって相関が生じると考えると,因果を考えることができない
- 交絡変数の入れ方によって,結論が変わったりする
- 個体内変動と個体間変動:
勉強時間と成績に正相関があるとき→成績悪&時間短の個体と成績良&時間長の個体は違うので,勉強を長くしたからといって成績がよくなるとは限らない
サンプルセレクション†
- 標本がランダムサンプルではない:Yが非ランダムとXが非ランダムの場合がある
- 対象群を分ける基準によって結果が変わったりする
因果分析には相関を使うべきか,偏相関を使うか?†
- 昔は偏相関は値が小さすぎて使いにくいと言われていた
- どの変数で条件付けするかを考えることができる
- DAG (有向非循環グラフ)
- 有向分離
- d-separation:XとYを結ぶ各パスにおいて次のどちらかが成立
- 合流点があるとき……
- (かけなかった)
- DAGの制約:偏相関は存在しない→ancentral graph;AG (一部は両方向の辺)
- AG
- 辺がない場合:条件付独立になる.DAGのよい性質を引き継ぐ
- 変数のどんな部分集合も条件付独立にはならない場合が生じてしまい,この場合は役にたたない
- AGにおける代数的制約 (bi-partial covariance)(わかんなかった)
bi-partial covariance=0 ⇔ AGで条件付独立
「教師あり順序付けのための次元縮約」†
神嶌 敏弘、赤穂 昭太郎(産業技術総合研究所)
質疑応答
- 正準相関分析との関連は?
サンプル順序が同じ対象で構成されていないので,そのあたりが難しいと思う
「大規模な半教師付学習に対する最適化アプローチ」†
矢島 安敏(東京工業大学)
- 線形関数で判別する問題を凸2次問題として定式化→カーネルを用いた非線形判別
- One-class SVM:クラスと原点を分離するような分離平面を求める.
- グラフのカーネルを使って準教師あり学習をする.
「シーケンスを節点とする木構造データマイニングのための半構造マイニング手法FREQTの改良」†
佐藤 一誠、中川 裕志(東京大学)
- 木構造を行きがけ順にノードを並べて,シーケンシャルマイニングに問題を変換し,Prefix Spanなどを適用する.
- constraint based prefix span:頻度以外にも,ギャップ長などの制約もある.
- 設定数が多い場合にも対応可能
「ARXモデルの次数探索決定方法の検討」†
深田 健太、鷲尾 隆(大阪大学産業科学研究所)
- 外部入力付自己回帰モデル(ARX):その自身の過去の時系列と他の外部入力変数の過去の時系列から予測
- 従来手法:変数選択はAICを利用→測定誤差のためAICが最小値になる部分がよくわからない.
- ΔAIC* は,パラメータを一つ減らしたモデルとのAICの差を考える→
単純化によって,少なくとも誤差オーダーを超えて大きく精度が失われる可能性の高い,最も単純なモデル次数パラメータの組み合わせを発見する.(?)
「遺伝子相互作用を理解するためにMicroArrayデータからDAGパターン発見」†
ターミエ アレックサンドル(1)、玉田 嘉紀(1)、井元 清哉(2)、鷲尾 隆(3)、樋口 知之(1) (1)統計数理研究所、(2)東京大学医科学研究所、 (3)大阪大学産業科学研究所
頻出な木を見つけることで,高速にDAGパターンを発見.
「テキストマイニング技術の応用によるメタデータ自動獲得機能の実現」†
嶋津 恵子(1)、齋藤 功(1)、有澤 達也(1)、吉永 早織(2)、古川 康一(2) (1) 慶應義塾大学デジタルメディア・コンテンツ統合研究機構 (2) 慶應義塾大学大学院政策・メディア研究科
- 大学の部を横断したマルチメディアCMS:http://context.dmc.keio.ac.jp/
- 個々にデジタル化された内容にはメタデータが付与されていない→メタデータに該当するものを自動で付与
- 付与するメタデータのカテゴリには,5W1Hとコスト を用いた → 検索結果をメタデータによって絞り込めた.
福水 健次(統計数理研究所)
- 線形分離できないデータを,高次元に射影して線形分離可能にする.
- 高次元に射影するための道具:正定値カーネル
- 集合Ω上の正定値カーネル→Ω上の関数からなるヒルベルト空間 Hk (無限次元かもしれないベクトル空間)(RKHS)が定まる.
- k(・,x)∈Hk,
- 有原和 f=Σci k(・,x) の形の源はHkで稠密
- 再生性 f(x)=<f,k(・,x)> ∀f∈Hk x∈Ω,関数の値が内積で与えられる
- 高次元に変換する関数をΦとすると <Φ(x),Φ(y)>=k(x,y) と内積計算ができる -- カーネルトリック
- 線形だと max Var[ a^T X] → 非線形 max Var[ f(X) ]
→ f を再生核ヒルベルト空間から探すと再生性を使って:max Var[<f,Φ(X)>]→高次元空間での線形問題になる
高次元に写すのにカーネルを使う利点†
- カーネルによる非線形化は多くの場合 データで張られているものだけを考えればOK (レプリゼンタ定理)
- 条件が整えば,連続で微分可能
- 関数の値が定まる
- 内積の計算が容易
- 基底を考えるより,計算が楽
- 次元数が多くてもOK (データが多いと困る)
- 非ベクトルデータ (グラフ,ツリー,ヒストグラム) でもOK
- XとYが独立:E_EX[f(X) g(Y)] = EX[f(X)] EY[g(Y)] というふうにいえる?
- 定理[Bach&Jordan 2002]:ガウスカーネルを使うと独立性をいえる
- 条件付独立の場合に拡張
- 通常のガウスの場合 Var[a^T Y|X]=a^T [V_YY - V_YX V_XX^{-1} V_XY ) a
- カーネル化は自然にできる.このあたりが[福水ら2004]の定理
- 応用:回帰問題における次元削減
上田 修功(NTTコミュニケーション科学基礎研究所)
- ベイズ的アプローチ:予測を分布として求める ∫ p(x|θ) p(θ|D) dθ
- 非ベイズ:パラメータは一つで,そこからデータを作っている
- ベイズ:パラメータはいくつも分布の形存在し,それらがそれぞれデータを生成
Dirichlet分布:Dir(π1...πK; α0 φ1 ... α0 φK)†
- 期待値:E{πl}=α0 φl / [Σj α0 φj ]
- 事後分布の共役性:多変量分布の事前分布がDirchlet分布にすると事後分布も形は同じ
- 事後予測分布:N個のシンボルが与えられたときに次のシンボルを観測する確率は,事前分布から生じる要素とデータから生じる要素の混合分布になる
Dirichlet過程:Dirichlet分布を無限の要素がある場合に拡張したもの†
分割G=P(A1)...P(AK)が生じる確率がDir(G; α0 G0(A1)....G0(AK)) になる.
- Dirichelt過程の性質
- 期待値 E{G}=G0
- 共役性:
- 事後予測分布:[α0/α0+N] G0 + [1/α0/α0+N] Σ δ_θi:第1項はG0に由来,第2項は今までのデータ
- Dirichlet分布とは,分割が明示的には与えられていない点が違って,分割が求まる.
- Chinese Restaurant Process (CRP)
- k個テーブルに客が座っている状態.次の客は,k個のテーブルに座っている客数に比例する確率で座るか,k+1番目の新たなテーブルに座る.
- DPの構成定理
- G〜DP(α,G0)は,θ〜G0及びπk≧0,Σk^∞ πk=1 を用いて,以下の無限和で表せる:
G(θ)=Σk^∞ (かけなかった)
- stick breaking:
- de Finettiの表現定理
関係のマイニング(Infinite Relational Model)†
- 二つのサンプル集合の各要素の間の関係を行列で表し,それをブロック化するクラスタリング
- 各ブロックの関係を表す0/1が,パラメータθに従うベルヌーイ分布.θはβ分布,さらに,分割はCRPに従う.
おすすめチュートリアル:Dirichlet processes, Chinese restaurant processes and all that. M. I. Jordan. Tutorial presentation at the NIPS Conference, 2005.