#freeze
* 2005年情報論的学習理論ワークショップ (IBIS2005) [#hed93124]

このページはしましまがIBIS2005に参加してとったメモです.
私の主観や勘違いが含まれていたり,私が全く分かってなかったりしていますので,その点を注意してご覧ください.誤りがあれば,指摘してください.

ホームページ: http://ibisml.org/ibis2005/

----
#contents

* オーガナイズドセッション1「構造化データの機械学習」 [#kbc35db3]

* グラフ構造からの頻出パターンマイニング (チュートリアル講演) [#ad97143c]
猪口 明博

**頻出アイテム集合列挙 [#c3f351d3]

Aprioriアルゴリズムで,特定のアイテムを含むトランザクションで構成されるDBであるprojected DBを作ると,もとのDBにアクセスしなくてすむので高速.

**頻出部分グラフマイニング [#v6e17b06]

グラフの集合から,頻出する部分グラフを列挙.
アイテム集合の場合と違って同一のグラフを重複列挙しないようにする工夫がカギ.

束を構成するときに,頂点を拡張するのと,辺を拡張するものがある.

*** FSG [#s0d1550d]
辺拡張,幅優先探索.
辺拡張なので,k+1個の辺を持つ候補はk個の辺が共通な二つのグラフから候補を生成.
ここで共通な部分を見つけるためにグラフの同型問題を解かないといけないのが難点.

*** AGM [#p262caa6]
頂点拡張,幅優先探索.
グラフに辞書順を定義し,その中で最も前にあり,正準形とよぶものだけを考慮することで高速化.

*** gSpan [#g3d155b2]

辺拡張,深さ優先探索.
GFSコードを使った辞書順を定義して枝狩り.

***GASTON [#q2c3e9d4]
辺拡張,幅優先探索.
パスと根無し木は重複なく列挙可能なので,これを使う.
処理できないcyclicなものだけ,別途処理する.
疎なグラフではcyclicな部分グラフは少ないので高速.

*** どれがいいか? [#v29a4cb0]

疎グラフならGASTON,密グラフではAGM.

** 問題の拡張 [#o355d19d]

*** closed itemset mining [#r0daa35c]

支持度が同じでアイテムに包含関係があるアイテム集合で最も大きなものがclosed pattern.
closed patternがあれば,任意のアイテム集合の支持度が計算できる.

現在の最高速アルゴリズムLCM.
sequence以上複雑な構造に一般化するのは高速化が困難.

*** 汎化パターン [#d8ad299f]

頂点ラベルや辺ラベルに階層構造がある場合.

*** 3次元グラフ [#g219510b]

グラフだと頂点間の距離や鏡像は扱えない.

*** 単一のグラフ内で頻出する部分グラフの列挙 [#d1068165]

支持度を,グラフが大きくなると非増加になるようにするには工夫が必要.
ある部分グラフの埋め込みを考える.埋め込みを頂点とし,その埋め込み位置に共通部分がある場合を表す辺のグラフを考える.このグラフの頂点集合で,互いに隣接しない極大集合を抽出し,その頂点数を支持度とする.

*** その他の応用 [#t1bdea27]

-正例と負例をうまく分類できるような部分グラフをみつけるクラス分類問題.
-全てのグラフを列挙できるわけではない方法.

* グラフカーネルを用いた化学化合物の分類 [#occaf2f9]
Liva Ralaivola,西郷 浩人,Sanjay Swamidass,Pierre Baldi

**finger print [#gbbf30a9]

化合物に含まれる部分構造に対応するビットが1になっているビット列.

全部の部分構造を見つけるのは大変なので,ここでは,ある原子から深さ優先で部分構造を探す.ループがあっても同じ辺は2度通らないようにする.

finger printの類似度はバイナリベクトルの類似度で測る.

化学の分野で一般的なtanimoto係数(Jaccard係数)を表すカーネル.
tanimotoカーネルと類似したMinMaxカーネル.
tanimoto係数と,不一致を考えたときのtanimoto係数の加重平均のカーネル.

* 構造データのラベル付け学習モデルの設計 [#t5057f37]
坪井 祐太,鹿島 久嗣

**構造ラベル付与問題 [#h1ec5392]

構造を持つデータのノードにラベルを付与していく問題.
-自然言語処理での例
--単語列に品詞タグを与える品詞付与タスク
--人名や組織名などの固有表現を抽出するタスク
--単語列ではなく,係り受け解析木にラベルを付与する問題なども

問題の枠組みは教師あり学習.

**生成モデル型:隠れマルコフモデルによる方法 [#u3633d12]

ラベルが状態で,データが出力シンボルとして隠れマルコフモデルで定式化.

モデルが学習できればViterbiアルゴリズムでラベルが付与できる.

モデルの学習は単に頻度の数え上げで可能.

**識別モデル型:多クラスのロジスティック回帰 [#p3cdb4a0]

学習は最尤推定.

**識別モデル型:条件付確率場 [#n07bfdc7]

観測組成(ラベルとデータの対),遷移素性(遷移するラベルの対)に分解.

**構造ラベル付与の損失 [#od43fe4c]
-全損失:ラベル構造全体を正しく学習.一部でも間違うとアウト.
-点損失:点だけについての正しさを評価.

*オーラルセッション1「基礎・理論」 [#f68fc551]

* Generalization Error Estimation under Covariate Shift [#cda1ec53]
Masashi Sugiyama,Klaus-Robert Muller

線形回帰問題で,テスト入力の分布q(x)が訓練の分布 p(x) に従って生じる場合 (共変量シフト).
汎化エラーをテスト入力の分布について考えないといけない.

例:データが内部分を補うデータの外挿・内挿,データの分布を自分で決める能動学習など

*** 最小2乗法 [#k02a1bf4]

モデルが正しいとバイアスは0になるが,正しくない場合は0にならない.
q(x)/p(x)で重み付けするとバイアスは0にできるが,バリアンスは大きくなる.
さらにパラメータを導入するとうまくバランスがとれる.

ラムダの入った予測値と,真の内積をうまく近似計算して,パラメータをうまく推定.

修正赤池情報量(MAIC),subspace ICなどの方法も.

* 長期予測のための階層的状態空間モデル [#sf486473]
中田 貴之,竹内 純一

トレンド,周期,ARを含む時系列の予測

時系列モデル:トレンド,周期,ARの成分が加算になっモデル
これを統一的に扱えるモデルが状態空間モデル.
式(9)と(10)のような潜在変数znを導入したモデルを考え,EMで解く.

* ベイジアンネットワークの構造学習における強一致性について [#y77b8910]
鈴木 譲

ベイジアンネットの構造推定問題.
n個の変数があるとき2^n個のネットが考えられるが,サンプルから適切なものを情報量基準によって選ぶ.
強一致性を満たす情報量基準の罰則項の係数について.

*オーラルセッション2「アルゴリズム」 [#bd2ba911]

*ハイパパラメタを考慮した自然平滑化モデルによるオンラインベイズ学習の高精度化 [#bdde10f9]
若原 牧生,中田 洋平,松本 隆

パラメータの変化のユークリッド距離を使ったガウス分布の代わりに,
Fisher計量に基づく分布を使った平滑化モデル.
パラメータの変化のモデルの変化に与える影響を一定にできるメリット.

*疎な確率モデルによるクラス識別機の適応TAP方程式に基づいたアルゴリズム [#o12d46fb]
宇田 新介,樺島 祥介

平均場近似を用いてパーセプトロン型確率モデルのベイズ学習を効率的に行う.

*自由エネルギー降下原理に基づく平均場方程式の解法 [#e55ee297]
外崎 幸徳,樺島 祥介

* オーガナイズドセッション2「Intelligent Transportation Systems」 [#gd95de95]

* ITS の最新動向と課題 [#ge14a134]
津川 定之,加藤 晋

** 自動車の問題点 [#l6dbee32]
-事故:死者数は減少しているが,事故件数や後遺障害は増えている.
-渋滞:経済損失

解決:高度交通システムによる解消 (ITS)~
安全性,効率化,環境負荷の低減をめざす.~
例:カーナビ,VICS,ETCの実用化,CACS,知能自動車などの研究.

** 最近の動向 [#zd1a2044]
-日本: 現在は導入から展開
-欧: 最近は安全重視 (eSafety政策)
-米: 自動運転から運転支援,犯罪防止や治安確保→低調

全般的にITS通信の利用が発達
-路車間通信: VICSやETCなどでつかう
-車車間通信: ACC(速度や車間距離の確保),各種の警告
--自動運転: 高速で短い車間距離で隊列走行ができる.先頭だけ人間が運転し省力化.
--安全運転支援: 見通しの悪い交差点での警告など

通信により把握できる状況の変化への対応した最適化技術が重要
-自動車交通流の最適化: 信号制御
-車両走行の最適化: 支援のタイミングや,快適さなども考慮した自動運転

** 交通全体の支援 [#m3baf42c]

信号制御システム: 最も確率された交通流最適化の技術
-定時,定周期制御から,交通流に動的に対応した感応制御

経路誘導システム: 迷走,誤走の防止
-静的経路誘導: 車の装置だけで動作
-動的経路誘導: 路車間通信で得た情報も利用

VICSの発展動向: 道路交通情報,駐車場情報
-プローブカー情報: 路上センサーではなく,車両からの情報(速度など)を直接利用

** 車両走行支援 [#d8e7a16e]

運転支援システム
-2秒前に回避行動ができれば多くの事故は防げる
-ラテラル支援・操舵:レーンキープ,駐車
-ロンジチュジナル支援・操作: センシング(車間距離),スライディング支援
-ドライバ適応型の支援: 車の運転状況に適応的な支援

自動運転システム
-自動車運転の安全と効率化の達成
-早期の判断とヒューマンエラーの低減
-道路利用の効率化:
--例:狭いレーンの走行や厳密な停止位置が実現できるバス運転
--例:専用道路では隊列走行,一般道では通常運転

** ITSの課題 [#o9af1496]
-センシング,通信,制御,評価,最適化
-システム普及のための問題点: インフラ整備と車両の個別ごとの整備が共に発展できるようなシナリオ

* 人間の行動予測モデルに基づく認知計算過程のモデル化とリスク評価 [#f701cd98]
水谷 健太郎,大森 隆司,石川 悟

**ASV(先進安全自動車) [#m469652e]
運転支援:追突防止,車線追従システム
→人に応じた支援

**他者の行動の意図推定 [#w95aab49]

-他者の意図推定のモデル化: 外界の予測,他車の意図の予測,さらに助手は運転者の予測も
-コンピュータシステム内にユーザモデルを生成しそのモデルから予測
-車に運転者モデルを作り,周囲からの情報を利用して支援する

**運転行動モデルの例 [#v8da0c54]

視線移動による外界探索とステアリング操作とでモデルを構築

* プローブカー情報を用いた動的経路案内システム「PRONAVI」の開発 [#o6639317]
山本 俊行,三輪 富生,森川 高行

** カーナビ [#e16158e9]

-VICS付きは全体の3/4.
-道路にセンサーを設置.
-センサーの設置コストが高いので幹線道路に限られる.

この問題への対処法
-車や人をプローブにして,プローブセンターにデータを送る
ーー幹線道路だけでなくどの道路でも利用可能
-プローブされる情報: 位置,速度,ワイパー,エンジンの情報,ABS,操舵角
--位置情報の密度から得た渋滞情報
--ワイパー情報からの降雨状況の確認
--ブレーキ,ABSから危険箇所の特定

** PRONAVI [#l4651d85]
コンソーシアム体制での,プローブ情報に基づくナビゲーションの実験システム
-経路検索:時間,料金,距離,CO2排出量などの予測
-名古屋圏で実験
-プローブカー情報に加えVICS,道路工事,事故,気象,交通機関の情報も利用
-プローブ情報をタクシー設置して,携帯電話のアンテナで情報を収集
-データ送信はイベントベース: 車両の発進,停止,300m走行でデータを送信

** リアルタイム情報 [#j6f4beac]
プローブデータが連続ではない
-経路の補完: 地図上の距離と走行距離が一致するように経路を予測
-速度の予測: 観測点間で速度一定の仮定はよくない→交差点の速度変化のモデル化して補正

** プローブデータの蓄積DB [#ye8d6a75]
-保存データなので,より精度の高いデータ補完が必要→VICS情報を補助情報とした高精度化
-気象情報による所用時間の違いの把握.その道路種別による影響の差違の把握.

** 最適経路探索 [#u8697b61]
-リアルタイム情報と蓄積DBによる情報の複合的な利用
-グラフの最短経路探索とは違って,右左折コストを考慮する必要
-平均実走時間は従来のカーナビより若干短く,予測誤差はより高精度だった

* 不確定な交通現象を最適化する需要予測型信号制御システム [#hbf12bce]
宇佐美 勤,小林 雅文

** 信号制御の基礎 [#e380a359]

-役割: 事故防止,交通流の円滑化,騒音・排ガスの減少
-信号現時: だれが通っていいかとう状態
-パラメータ:オフセット(隣接信号間の時間差),サイクル長, スプリット(交差する道路の時間の比率)
-クリアランス時間:信号の切り替え時には時間が多い.黄色や全赤(両方赤)時間の制御

** 現行の信号制御方式 [#y7171891]

-1970 東京で広域信号制御システムが稼働
-1971 パターン選択制御: 事前登録パターンから選択
-1995 MODERATO: 計測した交通情報に基づいて信号制御パラメータを自動制御~
渋滞が28%減少,経済効果1000億円

** MODERATO [#q7a68707]
-スプリット・サイクル長の自動生成→ムダ青時間の発生を抑制
-車両関知器配置: 信号前に重点的に配置.右折検出専用もある.
-待ち行列理論に基づく
-スプリット制御: 付加率(0.5なら待つ車がない)
-オフセット時間: 遅れ,停止時間,事故危険度を最小化する
-問題点→現状に対応するのではなく将来の状態の予測が必要
--計測からパラーメータ変更までに遅れがある
--一定時間ごとの更新なので適応できない場合がある

* オーラルセッション3「応用」 [#xc0f8a0c]

* 経験ベイズ法に基づくスパイク時系列の解釈 [#u4a5af4e]
小山 慎介,篠本 滋

大脳皮質の層の違いによってスパイクパターンは異なるので,逆にパターンから活動している層が予測できるのではないか?
脳のスパイク間隔データをスパイクの系列を分類する.
間隔はγ分布に従い,それが適宜リスケーリングされているモデル.
γ分布のパラメータλは平滑であるとする事前分布を使って,超パラメータをMAP推定する.

* センサーネットにおける観測と通信の統計物理学 [#hb73a922]
村山 立人,ピーター, デイビス

センサーネット: センサーを散布して無線でデータを集める.

センサーネット全体の系についての解析.
計測ノイズへのロバスト性(センサーが多い方がいい)の
データ伝送の省資源性(センサーが少ない方がいい)のトレードオフをレート歪み理論で解析する.

**センサーネット [#j4fe87a2]
-エージェント: 部分情報を取得するセンサー
-マネージャー: エージェントから受信した情報を統合して欲しい情報を得る

マネージャーに対してエージェントは多数なので,通信コストは高い.
⇒ 圧縮して送ろう

トレードオフ: 高品質に圧縮したデータを少数⇔高圧縮率のデータを多数~
結果:高ノイズだと高圧縮&多数が良いが,低ノイズだと低圧縮&少数がよい

* リスク回避型学習 [#qda02202]
鹿島 久嗣

コスト考慮型学習: 入力ベクトル x に対して有限個のアクション y のいずれかをとる.
アクションの結果コスト c(x,y) が生じる.
--択一型アクション: 一度にとれるアクションは一つで,決定関数を最大にするアクションを選択
--資源分散型アクション: 決定関数の値に応じて確率的に全てのアクションを実行できる.
-訓練データ: データ,アクション,コストの組

通常は訓練データに対する平均コストを最小化⇒~
リスク回避型学習:大きなコストが生じる確率を小さくする.

バリュー・アト・リスク:トップ(1-β)%目のコスト~
期待ショートホール: トップ(1-β)%のコストの期待値=バリューアトリスク以上のコストの総計

* 特別講演: Finding the Gobal Optimum using Belief Propagation - New Theoretical Results [#t68dbb0f]
Yair Weiss

グラフィカルモデルのMAP推定をmax-product BPを使って解く

-''グラフィカルモデル'' 
ノード:確率変数,辺:制約,例: マルコフネット,ベイジアンネット

-QMRネットワーク:
医療診断.症状:d1...dN,病名:f1...fk,辺はdからfへの完全2部グラフ.
-パリティチェック:ノードがビット,辺がパリティの制約

**問題 [#c7ca6c27]
-これらのMAPを厳密に解くアルゴリズム
-triangulatedグラフのクリーク数に対して指数計算量
-数値パラメータは独立

** Belief Propagateion [#y6027378]

通常のBP
-グラフが木なら有限時間で収束

Loopy max-product BP
-実データへの性能が良い
-サイクルが一つのグラフについて正しい解を与える
-x*が事後確率の強局所最大値になる

従来のBPと違ってbeliefにタイがある場合について.

* オーガナイズドセッション3「変分ベイズ法」 [#ybe9cd1e]

* 変分ベイズの基礎 [#teaacfe8]
上田 修功

** 変分ベイズ [#k9892bf8]
-ベイズ学習の一手法: 変分近似学習 (MacKay 1994, Attias 1999)
-決定論的な近似解法,EMの拡張
-MCMCと同様の目的だがあらい近似で高速

** 生成モデルアプローチ [#i73bbdcc]
混合分布を考える.
-非ベイズ・アプローチ: パラメータを数学的変数と考える ⇒ 最尤学習
-ベイズ・アプローチ: パラメータを確率変数と考える ⇒ MAP学習

**ベイズ学習 [#l7b8c417]
事後予測分布による推定
 p(x|D)=∫ p(x|θ) p(θ|D) dθ
p(θ|D) をベイズ則で p(D|θ)で書くと積分の計算が大変
-確率的サンプリングでする: MCMC
-変分近似する: 変分ベイズ

** 変分近似 [#j5965af6]
下限値の最大化で近似する方法.
分布qを新たに導入して,Jensenの不等式で下限に変換するのがポイント.
MCMCは単調に振る舞わないが,変分は単調に振る舞う.

**MCMCと変分ベイズ [#u05862f9]
-MCMC: 分布から''確率的に''パラメータをサンプリングしながら更新~
期待値計算は計算機にがんばってもらう
-変分ベイズ: 分布から''確定的に''パラメータを更新~
期待値を解析的に計算しないといけないのが大変~
指数分布族+共役事前分布でないと計算は実際には難しい

* 変分ベイズによる MEG データ解析 [#i7e75095]
佐藤 雅昭,吉岡 琢,山下 宙人,梶原 茂樹,外山 敬介

脳科学で視覚,触覚,聴覚刺激に対する脳の反応を解析
-fMRI: 空間分解能はミリメートルだが,秒単位程度の時間分解能
-MEG: 空間分解能はセンチメートル程度だが,ミリ秒単位の時間分解能

''MEG電流源推定問題'':
観測される地場 B から,脳内の電流分布 J を B=G J+ε の線形モデルを使って解く問題.
Gは物理法則から機知.

Jの事前分布の設計がミソ.
-設計に使える情報: fMRIによる情報,電流源の局在性,空間的滑らかさ.

* 変動する環境下での独立成分分析と変分ベイズ法による解法 [#vb77bfef]
平山 淳一郎,前田 新一,石井 信

** オンライン変分ベイズ法 [#jd0cb57f]
オンライン学習のバッチ学習に対する利点
-データ保持のメモリが少ない
-追加学習がしやすい
-環境変動に追従できる?

実現
-自由エネルギーが時間によって減衰するようにしている.
-さらに環境変動に適応できるように,忘却係数も適応的に定める.

** 独立成分分析 [#r5103aa4]
-信号源の数が未知で時間的に変化
-信号が出ているかどうかを明示的に考える→Switching ICA
-信号のon/offはマルコフ過程でモデル化

* 変分ベイズを用いた音声認識 [#y80db1fe]
渡部 晋治,南 泰浩,中村 篤,上田 修功

**音声認識 [#m3a2f529]
-隠れマルコフやガウス混合のモデルを使って最尤推定
-あとは学習データを集めると推定精度はあがる?
⇒発話や騒音などのノイズに対するロバスト性は解決できていない

モデルと推定方法の改善点のうち,推定法を最尤推定→ベイズ推定して改良を試みる
-事前分布の活用,モデル選択可能,周辺化による頑健な推定

音声認識のパラメータ数は数100万もあって,今までのモデルのパラメータそのままをベイズにするのは無理
⇒音声認識をベイズの枠組みで再定式化

* 変分ベイズ学習理論入門 [#j3a07a34]
渡辺 澄夫,渡辺 一帆,中島 伸一,星野 力

**汎化誤差 [#l2929eb3]
-真の確率分布 q(x) から事例がiid得られたサンプルX^n→パラメータ状の分布p(w)を推定→p(x|w)の平均を求めて予測分布p(x)を求める
-p(x)とq(x)の間の差である汎化誤差を考える

**自由エネルギー [#we66eda7]
ハミルトニアン H(w)に対して p(w)=(1/Z)exp(-H(w)).
平衡状態で取り出すことができるエネルギー F=-log(Z).

**相対エントロピー [#j74e1d50]
二つの確率分布の差を表す
 ∫ q(x) log[ q(x) / p(x) ] dx
KL情報量,平均対数尤度比ともいう

** ベイズ予測の分布 [#of7464ea]
-ベイズ事後分布は一般に複雑⇒変分事後分布では単純.
-よって,ベイズ事後から求めたベイズ予測と,変分事後からもとめた変分予測は違う

** 汎化誤差の違い [#q0534987]
-ベイズ予測似対する汎化誤差Gと自由エネルギーの関係.サンプル数nについてG=F(n+1)-F(n).
-変分ベイズではG*≠F*(n+1)-F*(n) ⇒ では汎化誤差はどうなのか?

-ベイズ法: F(n)=λ log(n),G(n)=λ/n のように同一の係数
-変分ベイズ: F*(n)=F* log(n),G*(n)=λ**/n のように違う

一般にF(n)≦F*(n),事前分布が真ならば G(n)≦G*(n)

** 理論の応用に及ぼす影響 [#i321cc5c]
-変分ベイズそのものの理解の助け
-変分ベイズは超パラメータに影響されるが,その定量的な影響の大きさの評価
-局所解に陥る確率や,局所解になったときの悪さの評価

*オーガナイズドセッション4「音声・言語データコーパスとそれを用いた統計科学的手法による研究」 [#e39fdd59]

* 文書検索・分類のための評価用データ [#b63bf478]
岩山 真

**評価用データ [#c6ae278c]
| |課題|正解|h
|文書検索|検索要求|文書|
|文書分類|文書|カテゴリ|

プーリング: 正解のラベリングのコストを小さくするための評価手法

* タグ付コーパスを用いたテキスト自動要約手法について [#sffa5deb]
奥村 学,平尾 努

-''単一文書要約'':重要文抽出,文短縮
-''複数文書要約'':重要文抽出,冗長性判定,文短縮,生成

-アブストラクト:要約文
-エクストラクト:要約の生成に必要な元の文.一つの要約文について複数ある場合も.

重要文抽出は重要文と非重要文の2値分類で処理する.

* 音声対話システムの運用と尤度に基づく音韻モデルの構築 [#jd95f77b]
鹿野 清宏,Tobias Cincarek,加藤 智之

** 実環境での音声対話システム「たけまるくん」 [#h00d2e2a]
-生駒市の観光案内システム
-3年間の稼働実績
-1万通りの質問に対して500個の応答文がある
-独立語の一致をみる.正解率は70%ぐらいだが,間違えても許してもらえる環境.

-訓練データ収集のコストの低減~
音響尤度基準が一定の部分にあるものにだけラベル付けする方が,ランダムサンプリングよりよい.
-現在は特定のタスクに適合しているので,汎用の音韻モデルを作る.~
発話データを一つずつ使った方が推定精度が上がるかどうか調べて選択.

* コーパスに基づく雑音抑圧手法 [#x77f91b7]
武田 一哉,李 衛鋒,チャン,フィ,ダット

''スペクトル減算法'':
信号とノイズは加算されているだけなので,パワースペクトルも和になっていることを利用.

* 教師あり順序付け ― 手法の比較実験 [#j9cde30c]
神嶌 敏弘(産総研)・賀沢秀人(NTT)・赤穂 昭太郎(産総研)

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS