このページはしましまがIBIS2008に参加してとったメモです．私の主観や勘違いが含まれていたり，私が全く分かってなかったりしていますので，その点を注意してご覧ください．誤りがあれば，指摘してください．
持橋大地（NTT）
ノンパラメトリックベイズとは
- モデルをデータの複雑さに応じて複雑にする生成モデル
- 理論的には加算無限個まで増やせる
- 例：ガウス混合モデル
- 普通は K 個のガウス分布を混合
- ノンパラベイズでは，はずれ値が現れたとき，新たな要素分布を加える
- ガウスの中心位置は分布 G0 から無限個サンプルし，その高さは stick breaking課程(SBP)で決める
- SBP
- wk〜Beta(1,α)，k=1...無限大．p(k)＝wk Πi^{k-1} (1-wi)
- 長さ1のスティックを w1 の位置で折る．残ったスティックの中で w2 の位置で折る．これをずっと続ける．p(k) になる確率は，k 回目に折ったスティックの長さ．
- Beta(1-α,β+kα) で折る位置を決めると
- 階層的ディリクレ課程：H → G0 を作り，G0 を測度として使って G1, G2... を作る
- ノンパラベイズ：測度論による定義，CRP などの実装・MCMC，SBP (機械学習)
- SBP で棒を切るβ分布のパラメータが変わる
- infinite stochastic tree：根から離れると生じる確率が小さくなる無限に深い木
- Mondrian課程：階層的に領域を分割する，ポアソン課程を階層化したもの
- infinite HMM：隠れ状態が無限個のHMM．有限の場合と同様に，動的計画法で解ける．
- Indian Buffet課程：複数の隠れ素性を複数もつバイナリ行列の生成過程．Beta課程と等しいことが知られる．
- ノンパラベイズは対象に合わせたモデル化が必要なので，パッケージを手軽に利用しても結果は出せない
- チュートリアル
上田修功（NTT）
- ラベルなしデータは，予め決められたクラスのいずれかに属す
→想定外データに対する新クラスを作る
- モデル
- 学習法：2段の無限混合分布で，Gibbsサンプリングでは計算は大変
栗原賢一（Google）
松本裕治（奈良先端大）
言語処理における問題
- 曖昧性：どの段階にも曖昧性があり，一意な解を得にくい
- 係り先が複数考えられるとか，and/orなどの並列構造の扱い
- 頑健性：例外的処理が多すぎる → 分かるところはルール・残りはコーパスから学習
機械学習を使った統語解析の問題
- 構造全体の最適化をすべきところだが，局所的な情報のみ
- 対処法：局所特徴+大域最適化；逐次的にN-bestを選ぶ，競合対象の直接比較
- 異なる処理階層がパイプライン的に処理する：同時にやるのは組み合わせ爆発に
脇隼人（電通大）
- 多項式最適化問題 (POP)
- n 変数多項式で記述された制約式 + n 変数多項式の最小化
- 凸性や単峰性は仮定しない
- 2次最適化問題や組み合わせ問題もPOPで記述でき，汎用的な問題設定
- 半正定値計画問題(SDP)
- 主双対内点法で，行列サイズ n の多項式オーダーの反復数で解ける
- ソフト：SDPA(C++), SeDuMi(matlab), SDPT3(matlab), CSDP(C)...
- 半正定値計画緩和 Lasserre[2001]
- POP を SDP に変形して解く
- POPの最小値≧SDPの最小値 が得られる → 解きたい問題の下限が分かる
- 二つの最小値の差を小さくしたい：理論的には小さく，実用的には0になる場合も
- Lasserreの方法：概要
- レベルの違う無限個の SDP の列を作る
- 下位の SDP の最小値は，上位のSDPの最小値より小さい→POPの最小値に収束
- しかし，高レベルのSDPの問題規模は大きいので，実際に解くには限界がある
- Lasserreの方法：詳細
- 発展
- Lasserreの方法は大規模なSDPになりやすい
- 疎構造(制約部分に使われている変数が疎)を利用して実用的に解く方法
- 得られるSDPは誤差に弱いので，数値解を求める方法に工夫が必要
ミニマックス確率マシンとその拡張について†
北原知就（東工大）
- min-max確率マシン
- 2クラス判別，線形判別，2クラスの平均と分散共分散行列は既知
- 各クラスの最大誤判別率大きい方を最小化するような線形判別関数を求める
- 確率の上限値は平均μから凸領域 T へのある種の距離で決まる (Marshal & Okkin, 1960)
→ 凸領域が境界を含まない半空間なら上限は陽に解け，これを使って2次錐計画問題に帰着できる
- 2次判別や凸判別の場合にも拡張できる
岡本吉央（東工大）
効率よくとける離散最適化問題
- 背後に木構造を持っている←こっちを話す
- 背後に凸構造をもつ(マトロイドと劣モジュラ)
グラフの木分解
- ジャンクションツリー：モラル化(無向グラフに)，ジャンクションツリー構成，信念伝播で解く
- グラフマイナー定理：元はWagner予想
木分解(グラフ理論)＝ジャンクションツリー(機械学習)
- 木分解して，木幅が小さいときは効率的に解ける
木：閉路を含まない連結グラフ
グラフの木分解 T：グラフのもつ「木らしさ」を表現
- T の接点はグラフG=(V,E)の部分グラフ
- G の各頂点と各辺はTの節点が必ず含む
- G の各頂点を含む T の節点は T 上で連結
- 便利な木分解→Tの節点中の頂点数が少ない
- T 木幅：Tの節点中の(最大超点数 - 1)
- G の木幅：いろいろな T の中での最小値
- G の木幅=1⇔Gが木
- 木幅が小さいときは効率的に解ける
- 木幅は一般に小さい：化合物はだいたい3ぐらいまで，gotoなしのプログラムは6以下
独立集合問題
- 無向グラフ G と自然数 k について，G が頂点数 k の独立集合(互いに頂点が隣接しない)を見つける
- 最大独立集合問題：最大の k を見つける
- NP完全，近似するのも難しい
- 頂点数 n，木幅が w のとき O(2^w w n) で解ける←木分解はすばらしい
![[bigsmile]](image/face/bigsmile.png)
- 木に対する独立集合問題
- 根を独立集合に入れると，次の階層の節点は入れられない．その次の階層の節点は独立集合に加えられてといった具合に，1段おきの階層で構成される．根を含むのと，ふくまないのと大きい方を選べばよい．
- 含められない階層の節点を取り除くと，部分木が残るので，部分木の独立集合を求める問題になる → 再帰的に解ける問題
- 木分解したグラフの場合への拡張
- 木分解の上位節点に含まれる G の節点に隣接する節点を除外する必要
- しかし，うまく工夫をすると，このあたりを独立に計算できて，再帰計算が可能になる
Courcelleの定理
- 単項二階論理(MSOL)で表現できる問題はどれも，木幅が定数のグラフに対して多項式時間で解ける
- しかし，木幅を求めるのはNP困難
- 最小次数法：だいたいうまくいく木分解の方法
- 隣接節点数が最小の頂点を v を次々に選ぶ
- {v}∪N(v) (vの隣接節点集合) を木分解の節点にする
- v を取り除き，N(v) を元の辺で連結して，木分解の節点は完成
- 元の構造に基づいて，木分解の節点を繋ぐ
「密度比推定の手法と応用」（杉山）†
密度比の応用
密度比の推定
- 密度比
w(x)＝p'(x) / p(x)
- p'(x) と p(x) それぞれから iid なサンプルがある
- 単純には p'(x) と p(x) を個別に求めてその比を計算する ← 余分に難しい問題を解いているのであまりよくない
- Kullback-Leiber Importance Estimation Procedure (KLIEP)
- Least-Squares Importance Fitting (LSIF)
- 線形の密度比モデル．KL損失ではなく，二乗損失を使う → 凸二次計画問題で解きやすく，最適解は疎
- 正則化パス追跡：解は正則化パラメータλについて区分線形 → 全てのλに対する解が効率的に計算可能
- LOO交差確認の誤差が解析的に解けるので便利
- その他： Kernel mean matching (KMM)，logistic regression method (LogReg)
参考図書
- Dataset Shift in Machine Learning (Neural Information Processing)
&amazon(0262170051);
- 強くなるロボティック・ゲームプレイヤーの作り方
&amazon(4839927413);
「学習と制御：ロボットへの応用」（森本，矢入）†
ハミルトン系の変分対称性と学習制御†
藤本健治（名大）
学習制御≒ある程度構造が分かっている状況で，データからパラメータを最適化
森本淳（ATR）
- 最適制御問題
環境：x{t+1}＝f(Xt,ut) + nt
- 報酬を最大化するための特徴抽出：x{t-1}, xt, yt に依存して rt が得られる
- 回帰問題の次元削減を利用して適切な特徴を選ぶ
内発的報酬と外部報酬による強化学習†
内部英治（沖縄先端大）
- 強化学習：平均報酬の最大化
- 報酬はタスク依存，少数の場合を除いて得られる報酬は0 → 学習に時間がかかる
- 内発的な報酬：新奇性，予測のしやすさ，探査ボーナス，ボトルネック状態への補助
→タスクに依存しない，ほとんどの状態で報酬は非0
- 長所：外部報酬への効率のよい誘導，自立的な発達学習 ⇔ 短所：学習結果が設計者の意図に合わない
- 制約を導入することで，設計者の意図に適合した内発的報酬
- 方策の勾配に制約を加える + 個体間で内発的報酬の共有
- 制約の導入
- 報酬の平均の最大化問題に，期待報酬に対する不等式の制約を加える
- 制約で生じる実行可能領域を使って，内発的報酬の勾配を変更する
- 内発的報酬の共有
- ロボットが出会ったとき，自分と相手の状態を比較，遺伝的アルゴリズムのように変更
- 良ければ現状を維持する方向，悪ければランダムに変更
センサデータの次元削減による地図作成と自己位置推定†
矢入健久（東大）
移動ロボットの自己位置・地図推定
- 古典的：自己位置推定(Kalmanフィルタなど)と地図推定問題(三角測量)を個別に解いていた
- 最近：SLAM(Simultaneous Localization and Mapping) → 同時に行う
- 観測方程式，状態(遷移)方程式，観測量 yt が得られたとき，位置 x{1:N} と地図 m を推定（ut はロボットの制御量)
観測方程式 yt＝g(xt,m) + wt → p(xt|x{t-1},u{t-1},m)
状態遷移方程式 xt＝f(x{t-1},u{t-1},m) + vt → p(yt|xt,m)
- 確率表現にすると状態空間モデルになるので，これを解く
- バイブル本： Thrun, Probabilistic ROBOTICS &amazon(0262201623);
- 問題点：移動や観測は正しいことが前提，人間などの認知過程を反映していない
次元削減による自己位置・地図推定
- 自己位置推定：高次元センサーデータから，低次の自己位置パラメータの空間
- 地図作成：高次元の実世界データから，低次のデカルト座標の情報などの空間
ヒューマノイドロボット間の対話に基づく感覚運動パターンの抽象化空間の適応的獲得†
稲邑哲也（NII）
目標：人間の簡単な指示で，迅速に活動できるロボット
- 経験の蓄積と抽象化，シンボル化による再利用
- ヒューマノイドの動作の空間を，その動作を表す語と対応付ける
- 各動作を隠れマルコフモデルで表現し，モデル間の類似度を求め，多次元尺度法でマッピング
- 複数のシンボルを組み合わせ，HMMのパラメータの内挿・外挿をして，新しい行動パターンを作り出す
「複雑ネットワークと機械学習」（鹿島，加藤，猪口，小山）†
複雑ネットワーク入門，および，院内感染のネットワーク†
増田直紀（東大）
複雑ネットワーク
- Power-law(scale-freeと呼ばれる): ノードの度数ごとの頻度を数えると指数的関係がある
- 平均次数よりずっと大きな次数をもつノード(hub)が存在
- クラスタ性：ランダムにつなぐよりも，三角形が高頻度で存在
生成モデル
- スモールワールドネットワーク：丸くノードを並べて，両隣と一個飛びでつなぐ．その辺をランダムにつなぎ変える
- Preferential Attachment (BA)モデル：ノードをつなぎ替えるときに，ハブに高い確率で繋げる
院内感染のネットワーク
ペストのような感染モデル
- SIRモデル：S(susceptible)→I(infected)→R(recovered)
- SISモデル：S→I→Sモデル (2回以上同じ病気になる可能性)
- 周囲にいる感染者の数に比例して感染率が上がる
- SISモデルの相転移：病気の生存が急激に増える点が存在
スケールフリーの方が感染は広がりやすい
- 平均次数が同じとき，均一度数とスケールフリーを比較
- 直感的に，ハブは感染しやすく，かつ，感染させやすい → 2乗で効いてくる
実際のネットワークには階層性，コミュニティ構造がある
- 社会では，個人は複数のコミュニティに所属．コミュニティ内ではリンクは密だが，コミュニティ間では疎．
- 院内ネットワーク
- 要素(ノード)：患者，看護師，医師
- 辺：カルテ：患者と担当看護師・医師 + 同室の患者 + 同棟の看護師 + 医師のチーム
- 病棟や部屋といったコミュニティが存在し，階層性のあるネットワーク
- SIRモデルで最終的な R の割合で評価
- コミュニティ間をつなぐ医師の移動を制限することで，感染を抑制できる
- ワクチンはハブを中心に行うと効果的
mixiにおけるソーシャルネットワーク分析†
加藤幹生（mixi）
mixi：日記とコミュニティを中心としたSNS
- クローズドな世界：検索エンジンで検索できない
- 友人とのコミュニケーション：友人のコンテンツを見やすい
- ユーザ数15000k，アクティブ率55%，月刊PV 136.7億，男女比 48:52，30未満が2/3
- リンク数327000k，平均マイミク数 22.02人，クラスタ係数 0.196(割と密)
- 距離6で，95.7，距離7で98.2%に到達可能 → スケールフリー性
- 2割のユーザが65%のリンクを保持
- コミュニティ：承認制・そうでないものとがあり，一人は1000個まで
- ノード数 200万，リンク数32000k，平均コミュニティ数 20.31，最大コミュニティ 43万
- 2割ユーザが80%を保持
サービス
- おすすめマイミクシィ
- Admic/Adar: マイミクが少ないほど付き合いが深い．自分のマイミクの中の人について，その人のマイミク数 n に対して Σ1/n で推薦
- コミュニティブラウザ
- 参考にした文献
無限関係モデルとその周辺†
山田武士（NTT）
2部や3部グラフをブロック化するモデルとネットワーク研究との関連
- Newmanのnetwork modularity: モジュール度を最大＝コミュニティ内では密に，コミュニティ間ではリンクを疎に分割
- 利点
- コミュニティ数は自然に決まり，パラメータはない → 使い勝手はよい
- クラスタ外へのリンクの張り方は似ていなくてもよい
- 問題点
- 確率モデルではなく，ノイズを無視
- resolution limit：明らかに望ましいコミュニティの方がmodularityが小さいときがある
- 混合モデルによるノードクラスタリング：混合多項分布を使う
- assortative: コミュニティ内で密，間で疎
- disassortative: コミュニティ間のリンクの張り方が似ていて密だが，内は疎
- 混合モデルを DP を使って拡張
- CRPだと，Preferential Attachment と似た考え方．自然淘汰がない進化の中立進化説との関連
- collapsed Gibbs sampling
- 現在の分割から一人をクラスタから割り当てを外す
- 新しい K+1 個目のクラスタへの割り当ておも想定しつつ，クラスタの事後分布に従って再割り当て
- 割り当て後のモデルを更新．更新が差分だけでできるところがミソ
- ブロックモデルにおける関係生成モデル
- 2ドメインの場合：各ドメインで確率的にクラスに所属すると共に，各ドメイン内のクラスを確率的にリンクする
- 二つのドメインを次元圧縮しているとも見なせる
- IRM(無限関係モデル) DPを導入して無限の場合に対応させた
- collapsed GS で解くが，二つのドメインで交互に行う
- 二つのドメインが同じ T1＝T2 のとき，ネットワークのクラスタリングとみなせる
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
