しましま/IBIS2011
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
* 第14回 情報論的学習理論ワークショップ (IBIS2011) [#f399...
COLOR(#00AA00){このページはしましまが [[IBIS2011>IBIS#IBI...
#contents
* 2011/11/9 (水) [#tb2023a3]
* 大規模最適化およびリスク指向最適化の最新解法 [#j28faa9f]
オーガナイザー: 比戸将平 (IBM)
** 大規模凸最適化問題に対する勾配法 [#vdddff4d]
[[山下信雄>http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/]...
- より広いクラスに導入できるようにBregman距離へ拡張,局所...
構造をもった凸問題
min f(x)=h(x) + P(x)
- hは微分可能な凸関数,P は特殊な構造の凸関数
-- P を L1ノルムとすると L1 正則化問題
-- 単体制約(総和が1)条件付き最大エントロピーモデルやCT...
-- ハードマージンSVM
Bregman距離
- ユークリッド距離,負のエントロピーなどが含まれる
局所的エラーバウンド
- 解の集合を X* とすると,解に入っているときは 0 をとり,...
- 線形システム.Hoffman のエラーバウンド
近接勾配法
- 近接点法 + 勾配法
近接点法:x^{k+1}=argmin[ f(x) + (1/t_k) Bv(x, x^k) ]
- h は普通に勾配法,P には近接点法を適用するのが近接勾配法
** 大規模半正定値計画問題に対するソフトウェアと高速&安定...
[[藤澤克樹>http://blog.goo.ne.jp/opt-lab/]] (中央大学)
半正定値計画問題
- 多項式時間で解ける.枠組みとして広い.非凸でも緩和問題...
- 最大カット問題,ロバスト最適化,SVM
- 定式化
主問題:min C・X s.t. Ap・X=b_p, C は半正定値
内点法
- 実行可能領域の内部を通る方法
- 対数ポテンシャルや対数障壁関数などの最適解に向かう指標
- 数値安定性の問題
主双対内点法
- パス追跡法と双対定理の組み合わせ
- 主双対問題の内点の対数障壁関数の最小展を中心パスを定義...
- 理論的にも実装的にも現在最強
- 探索方向の検索とステップ幅の計算の反復になるが,探索方...
SDPAプロジェクト
- http://sdpa.indsys.chuo-u.ac.jp/
- MPI/pthread の並列計算.コアとノードへの振り分け
- 1996年→2010年:37時間→1秒 になる
-- アーキテクチャにアルゴリズムは依存しているのでハードと...
- 精度の向上:4倍や8倍精度を達成する需要がわずかにある....
- 問題への適用:行列の疎密,行や列の順序の並び替え,Schur...
** 不確実な最適化問題に対するロバスト最適化 [#m2c5c14f]
[[武田朗子>http://www.ae.keio.ac.jp/lab/soc/takeda/takeda...
ロバスト最適化法
- 不確実性を吹くんだい最適化問題
-- 最悪ケースでの損害を限定する
- 需要 u∈U の範囲にあったら min max{u∈U} u_i x_i のような...
- 応用:予測誤差の範囲を考慮,渋滞などを考慮した最短経路...
- Soyster が U が矩形の場合を考えてから長い間注目されてこ...
-- 矩形の場合は頂点だけを考えれば良かったが,Ben-TAl が ...
-- U の形状や,線形性などの制約があれば,扱いやすい問題に...
-- 問題に帰着できる制約の範囲の理論や,サンプリングを使っ...
SVMへの適用
- Caramanisらのグループ
-- 正則化項の最小化はロバスト最適化を適用すると自然に導か...
-- データそれぞれに揺れがある場合のロバスト化を考える
- ロバスト判別モデル (武田,金森)
-- 正例,負例それぞれに不確実性の範囲が決まる場合
** 時間整合的マルコフ決定過程 [#k1b8291b]
[[恐神貴行>http://www.trl.ibm.com/people/osogami/index_j....
経路選択問題
- 期待到着時間を最小化する選択 → 渋滞の時間帯に応じて経路...
- 個人的な要因によって,時間の分布が変わる場合にも対応で...
マルコフ決定過程での定式化
- 時間がかかると指数的に嫌うようなペナルティやEntropic Ri...
- ERMの制限は強く,なかなかうまくユーザのリスク嗜好を反映...
conditional tail expectation
- テール部分の確率がα以上にならないように → 時間的に多段...
- iterated risk measure:各時点での決定を再帰的に考えて求...
* 2011/11/10 (木) [#m9133e91]
* 関係データとテンソル分解 [#n6746a21]
オーガナイザー: 冨岡亮太(東京大学)
** テンソル分解を用いた関係データのモデリングとその応用 [...
[[林浩平>http://hawaii.naist.jp/~kohei-h/index-j.html]] (...
- ユーザ,商品,時間の三つの軸をもつテンソル表現を考える...
- 応用:タグ・ユーザ・アイテムのタグ推薦,人・向き・表情...
テンソル分解
- PARAFAC:次元数個のベクトルの外積をQ個足したもの
-- 特異値分解の拡張として見れるが,テンソルでは,ランクの...
- Tucker分解:コアテンソル×次元数個の行列.コアテンソルが...
-- 2乗誤差の最小化として計算される.一般には凸問題になら...
テンソル分解の確率的解釈
- Tucker分解の2乗誤差の式を考えると,残差のフロベニウスノ...
- コアテンソルの各要素の事前分布を N(0,1) とすると,出力...
-- 行列ガウス分布:行側と列側の共分散行列の外積を分散共分...
レビュー: Kolda & Bader, "Tensor decompositions and appl...
** 非定常な時系列関係データの解析に関する研究 [#m4e37559]
[[石黒勝彦>http://www.kecl.ntt.co.jp/as/members/ishiguro/...
- 関係データ:複数のオブジェクト間の関連で,関係DBの関係...
- この関係データの時系列
-- 応用:SNSの友人関係の時系列変化,顧客-商品の購買行動,...
-- 関係データを行列とすると,その時系列はテンソルになる
Infinite Relational Model (Kemp+ 2006)
- 同様の関係を持つオブジェクトをそれぞれクラスタにまとめ...
- クラスタ間の結合確率が表されたものの混合
- dynamic IRM
-- クラスタの生成事前分布がsticky prior + HDP-HMM(隠れマ...
-- 混合率は前の時間のものに影響を受ける
** Relation Extraction from the Web — Webからエンティティ...
[[ダヌシカ・ボレガラ>http://www.iba.t.u-tokyo.ac.jp/~danu...
- entity が rival_of や chief_of などの関係で結びついてい...
-- 自然言語で書かれた関係なのでノイズ多,矛盾する関係も出...
- 属性類似性(entityの属性が似ている)と関係類似性(entit...
潜在関係検索エンジン
- 日本と富士山の関係ににている,ドイツと?と聞いたときド...
関係の表現:語彙の集合で表現し,同じ関係を表すものを同じ...
- 語彙集合:二つの語でAND検索して得られた文書から抽出
- 関係間の距離は距離学習で求める
* 特別招待講演:Computational Challenges in Graph Mining ...
[[Professor Karsten M. Borgwardt>http://webdav.tuebingen....
グラフマイニング
- 大規模化が進んでいる.カーネルを使うのがトレンド.
- グラフ間の類似性評価:構造の類似と頂点・辺ラベルの類似
-- アプローチ:同形性判定,編集距離,トポロジー,カーネル...
グラフカーネル
- Walks (NIPS 2006c, JMLR 2010),最短パス (ICDM 2005),大...
- Walks:共通のWalkが多いほど類似.積グラフを作ると,その...
-- ナイーブな実装では O(n^6) の計算量だが,Sylvester方程...
-- 他の高速解法:線形方程式+共役勾配法,不動点法,スペク...
- Weisfeiler-Lehmanカーネル (NIPS 2009)
-- ノードに,そのノードに隣接するノードのラベルを集める....
-- 辺数とノード数の積のオーダーで解ける
- 遺伝学:遺伝子型から表現型を予測できる?
-- 遺伝子型も表現型も多くのデータが集まるようになった
- 現在のモデルは,SNPs 間の影響,環境の影響,祖先の影響な...
- 表現型:相関が最も強い表現型の対を探し出す
-- lightbulbアルゴリズム:高い確率で最良の解を発見できる
* 次世代DNAシーケンサ技術が求める知的情報処理技術 [#uce34...
オーガナイザー: 大羽成征(京都大学)
** 次世代シーケンサ解析で新たに求められる機械学習 [#k8238...
[[瀬々潤>http://www.se-se.jp/]](東京工業大学)
- 次世代シーケンサ:サンガー法 96本×500bp (00年代前半,誤...
** 医学研究における次世代シーケンサ技術の活用 [#e76be143]
久木田洋児(大阪成人病センター)
- 次世代シーケンサの使途:全ゲノム相関,単遺伝子疾患原因...
- 突然変異(病的影響を及ぼす)と多型(病的な影響はなく,...
-- 種類:SNP,〜数10bp(マイクロサテライト,VNTR)逆位
- SNP:Haplotype(SNP を含む系列)
- 全ゲノム相関解析 (genome-wide association study):疾患...
-- はっきりと不利な遺伝子を持つ人の特徴が分かったが,そう...
- 肺がんの遺伝子分析
-- 肺がんの多い家系について調査.200個以上の特異な変異が...
-- ホモ接合領域:父母からの遺伝子が同じパターン → 先祖に...
- 個別化医療
-- 肺癌:日本だと1/4には活性化突然変異がみつかり,その場...
-- 血液中遊離DNA:血液中に流れているDNAの断片 → 半導体シ...
** 網羅的なRNAの同定、定量、ネットワーク解析における計算...
川路 英哉(理化学研究所)
- シーケンサ:一人当たりのシーケンシングの費用が非常に下...
-- エラーはまちまち,スループットは単純に向上,配列長は一...
- 調査課題:どのRNAが転写されるか?どれくらい?制御の様子...
- Heliscope:RNAが転写される先頭の部分を読み出すシーケンサ
-- 文字列比較:95%ぐらいの精度なので,読み出したのがDNAの...
-- シグナル同定:正確な転写開始点はどこか?系列ごとにズレ...
-- シグナルの定量:観測数(?)から本当の転写量を予測する
- 転写モデル
-- 転写開始点の予測:モチーフの出現を特徴とする線形モデル
* 2011/11/11 (金) [#k2557b0c]
* 物理計測とベイズ的方法 [#p5593d7c]
オーガナイザー: 池田思朗(統計数理研究所)
** 意思決定の脳科学におけるベイズ的モデルの有用性 [#g0c83...
[[春野雅彦>http://www.bmi.jst.go.jp/researcher_3.html#har...
- なぜ脳科学でベイズ?
-- データ⇔表現 の双方向処理.尤度と事前分布に分けることに...
-- 各行動に対応するモジュールがあったとして,適切な行動は...
- 筋の冗長性:霊長類には運動制御に必要な筋肉よりもずっと...
- 手首の等尺性の制御をMRIで観察
腕の上と下の筋肉,トルクを一致させることと,二つの筋肉の...
- トルクと等筋力の調整と休憩を繰り返させると,その通りの...
- 筋活動の強さと同期するような脳活動が観測されるか? → 1...
- 筋肉の活動に関連する脳の領域を見つける → 脳の領域の数は...
- SVR/RVM ではうまくいかず,lasso正則化を使った回帰が良か...
情動の強化学習への影響
- 黒質:情動系と線条体:強化学習
-- 怖い顔・普通の顔のあとに,普通の強化学習の枠組みのタス...
-- 怖い顔にの影響を強化学習パラメータに組み込む → 最尤推...
** 人工衛星データとベイズ統計 [#s6cc858e]
[[中野慎也>http://www.ism.ac.jp/souran/kenkyusya/nakano_s...
地球磁気圏
- 地球の磁場は太陽風で吹き流された形状をしている
- その中でも歪んだ部分ではなく,地球にごく近い静止衛星な...
- 多数の人工衛星で観測しているが点での観測にしかならない ...
- 極端紫外光:プラズマ中のHe+イオンの光,エネルギーの低い...
- 高速中性粒子:地場に捕らわれている荷電粒子が電子を拾っ...
データ同化
- シミュレーション:初期条件や境界条件によっていろいろな...
- データ同化:数値シミュレーションと観測データを組み合わ...
- システムモデル:v_k はシステムで説明できない分
x_k=f(x{k-1}) + v_k
- 観測モデル
y_k=h_k(x_k) + w_k
- 基本的には状態空間モデルと同じ形だが,状態は数万〜数億...
- ベイズの定理を使って p(x_k | y_k) を求め,現在の状態を...
- 確率分布の近似:モンテカルロ近似→粒子フィルタ,ガウス分...
-- モンテカルロ+線形の折衷や,粒子生成の工夫で実際には問...
** 宇宙物理とベイズ統計 [#e1921b74]
[[植村誠>http://home.hiroshima-u.ac.jp/~uemuram/]] (広島...
- 宇宙物理学:あまりに遠くて点源にしか見えない,物理的に...
-- 手がかりは光だけ:光子の数,光子のエネルギー分布,時間...
- 変光星:単純に周期的に変わるものだけではない.昼間は欠...
- フォワードモデリングの例:ブラックホール降着流
-- 磁気流体の方程式 + 輻射輸送 → この二つの相互効果や一般...
--- 流体シミュレーションの結果から観測される光が計算でき...
- バックワードモデリング:ベイズでバックワードで予測しよう
- バックサードモデリングの例:スペクトルから銀河の距離の...
-- 銀河が遠いとスペクトルが暗くて撮れない → 銀河の色だけ...
-- 尤度:あるタイプの銀河をある距離においたときの色,事前...
- 降着円盤:恒星と並ぶ宇宙の基本構成要素の一つ
-- 重力エネルギーを解放しつつ光る.中心の天体にじわじわ落...
-- 円盤のふくれの位置をベイズモデルで推定
-- 円盤の歪みのモデルは,潮汐やレゾナンスモデルなどが提案...
- ジェット
-- 相対論的ジェット:ブラックホールの中心から吹き出ている...
-- 非常に細く絞られている:地場にプラズマが捉えられている?
-- ジェットと偏光:シンクロトロン放射なので非常に偏光が強い
-- 偏光の時間変動は法則性が全く見えない!相関があるときも...
-- 仮説:長期成分と短期成分があって混ざっているからランダ...
--- ベイズを使って成分分離に使った
** 単タンパク分子のX線回折と位相復元 [#ffa08816]
[[池田思朗>http://www.ism.ac.jp/~shiro/]] (統計数理研究所)
- タンパク分子の構造解析
- X-ray Crystalography:分子を結晶化させてX線をあてて観測...
-- タンパク質とかは40%ぐらいは結晶が作れない
- X線自由電子レーザー:波長の短いX線ではcoherentなレーザ...
-- X線回折画像から単分子タンパクの構造解析をする
-- 自由落下させながら撮る:いろいろな方向から多数の画像,...
-- 観測されるのは複素数のパワーだけなので,位相成分を復元...
-- SPR法:ベイズ系の方法で,欠測があってもOKになった
* オンライン予測 [#d6c2c038]
オーガナイザー: 畑埜晃平(九州大学)
** 組み合わせ論的オンライン予測問題 [#l88a6023]
[[瀧本英二>http://www.i.kyushu-u.ac.jp/~eiji/]] (九州大学)
- オンライン資源配分(乱択版)
-- 確率的にエキスパート i_t を選ぶ → Hedgeアルゴリズム
- オンライン最短路問題:全てのパスをエキスパートと思ってH...
** バンディットの理論と応用 [#q777a37e]
[[中村篤祥>http://prml.main.ist.hokudai.ac.jp/~atsu/]] (...
バンディット問題
- 多腕バンディット:1952年に論文があるが,1930年代からと...
-- k 台のスロットマシンから1台のスロットマシン i_t を選ぶ...
-- 割引期待報酬を最大化
- 毎回確率θiでxi(t)を得るとすると
-- 割引率γで無限界繰り返すのと,有限回 T で打ち切るのと
- exploration-expectation トレードオフの調整が必要
- 選んだアーム以外の情報も分かる場合はエキスパート統合だ...
- 訓練とテストの分離がされていると能動学習,分かれていな...
- 応用:クリニックトライアル(患者への治療)推薦,ネット...
stableな確率のバンディット問題
- スロットからの報酬 xi(t)〜Fi(x|θi) → 期待報酬μi が分か...
-- ベイズ最適な戦略と期待リグレットの最小化戦略とがある
ベイズ最適:無限界試行
- 1-armed-bandit:2台で1台の報酬は既知 p
-- 次のマシン1の Gittins Index が p より大きければアーム1...
Λ(t)=sup_N E[Σ γ^{t-1} x1(t - 1 + s)) / [(1 - γ^N) / (1...
- k-armed bandit のときは,Gittins Index が最大のものを選...
- 成功回数と失敗回数の関数を考えて動的計画法と近似で計算...
有限回 T の試行
- upper confidence index [Lai+ 1985, Aggrawal 1995]
- ε-Greedy:εの確率でexploration.達成リグレット (T))
- UCB1:報酬の上界を使う.達成リグレット (log(T))
敵対的バンディット
- 報酬の生成が,こちらのアルゴリズムを知っていて,最悪の...
- 期待リグレット:一番ましな戦略からどれだけ損が拡大したか
- Exp3アルゴリズム:Hedgeと似ているが,EEトレードオフと,...
- 達成リグレットは O(√{T}) になる
拡張
- multiple play設定:同時に複数のアームを選べる.ャッピン...
- combinatorial bandit問題 [Cesa-Bianki+ 2009]
-- 選んだ k本のアームの和のみが観測できる.経路の総和とか...
- online linear optimization 「McMahan+ 2004]
- Gaussian Process バンディット [Dorand+ 2009]
-- アーム間の相関を考える.相関はカーネルで表されて,違う...
応用
- ゲームの探索木,ニュース記事の推薦,ログデータを使った...
** オンライン凸最適化と線形識別モデル学習の最前線 [#dfcf9...
[[岡野原大輔>http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbi...
線形識別モデル
- f(x; w)=sign(w^T x) の符号で識別
オンライン学習
- 訓練系列 (x^(i), y^(i)) に対して予測を行い,その結果に...
- 学習例が冗長だと収束が早い,訓練例をその場で捨てられる...
- 基本形:訓練例を受け取り,識別が正しいかどうかを調べ,...
w{i+1}=w_i + (y α A x)^T x:αはスカラー,Aは半正定値行列
- 更新後の分類結果は y w{i+1}^T x=y w_i^T x + α x^T A x ...
オンライン学習手法
- パーセプトロン
w{i+1} = w_i + y x
-- 線形分離可能なら,有限回で収束する
- Passive Aggressive [Crammer JMLR 06]
-- w{i+1}=argmin_w[w - w_i]^2 / 2 + ヒンジ損失
- Confidence Weighted Algorithm (CW) [Crammer+ EMNLP 09]
argmin{μ,Σ} D_KL(N(μ,Σ)‖N(μ,Σi)) s.t. Pr{w〜N(μ,Σ)}[y - ...
- Adaptive Regularization of Weight Vectors (AROW) [NIPS ...
-- CW はノイズに弱いというのを改善
argmin{μ,Σ} D_KL(N(μ,Σ)‖N(μ,Σi))+λ1 L(x,y,μ) + λ2 x^T Σ x
- NHERD [Crammer+ NIPS 2010]
-- 重みベクトル w がガウス分布 N(μ,Σ) に従って分布してい...
オンライン凸最適化
- 確率的勾配降下法で解く
w=w - τ ∂L(x, y, w)
- 正則化があるときは FOBOS というのを導入
- リグレットが o(T) より小さければ最適的点に近づく
- regularized follow the leader (RTFL):正則化付きの最小化
-- リグレット O(T^{1/2})
- Online Gradient Descent
-- コスト関数が強凸である場合に適用可能
線形より高速な学習
- 入力より高速にするのは無理?
- SIMBA [Hazan+ NIPS 2011]
-- SVMをsub-linear時間で学習.Pegasos [ICML 2007] 100倍は...
-- メモリ上にサンプルを保持できることが前提,primal-dual...
** CV/PRで独自の進化を遂げる学習・最適化技術 [#s96c034c]
オーガナイザー: 木村 昭悟(NTT)
** 画像認識検索における特徴量表現 [#v182f57e]
[[原田達也>http://www.isi.t.u-tokyo.ac.jp/~harada/]] (東...
画像認識
- 特定物体認識(DB内の入力画像とのマッチ)⇔一般物体認識(...
- 難しさ:ラベル付けの曖昧さ,文脈の考慮,センマンティッ...
- 一般画像認識 (image annotation)
-- 昔はセグメンテーションとラベル付けを分けていた(Blob to...
-- 画素ごとにラベル付け (pixel to label) 2007
-- 画像にラベル付け Image Instance to Label 2004/2008
-- 潜在空間にラベル付け Concept to Label 2003/2006/1992
- Concept Learning
-- 画像を近さに応じて空間中に配置.画像のラベルを利用して...
-- 新規の画像がconcept空間のどこに配置されるかでラベル付...
- ARISTA:20億枚の画像データを利用した画像認識
- ImageNet:画像のオントロジー
-- コンテスト: http://www.image-net.org/challenges/LSVRC...
- 単語による理解で十分? → 説明文で作ったcencept空間
画像特徴
- 局所記述子→順局所特徴→空間的ピラミッド→画像特徴→カテゴリ
- 局所線形制約符号化と多符号化の比較
-- BoF → GMM → Sparse Coding (疎にする) → LCC (局所性を意...
- コードブック(局所記述子を多様体に変換してマッチ)と局...
** メモリベースパーティクルフィルタ: 状態履歴に基づく事...
[[三上弾>http://www.brl.ntt.co.jp/people/dan/]] (NTT)
オブジェクト追跡
- ビデオ中で動く物体の位置と姿勢の推定:急激な変化や遮蔽...
- 粒子フィルタが多用される → ナイーブにやると頑健にならない
- 頑健にするには? → 事前分布の改良
- 状態空間:同じ位置にあると思うモデルや,等速運動を仮定...
-- 短期の運動ではなく長期の動きに基づく状態遷移予測
-- 過去のデータを時間方向にランダムにサンプリングしてスム...
--- 滞留性(そこに留まる性質)と軌跡類似性(同じ軌道を通...
- 姿勢追跡:粒子フィルタ + 疎テンプレート照合
-- 疎テンプレート:3次元の顔テンプレートを利用
終了行:
* 第14回 情報論的学習理論ワークショップ (IBIS2011) [#f399...
COLOR(#00AA00){このページはしましまが [[IBIS2011>IBIS#IBI...
#contents
* 2011/11/9 (水) [#tb2023a3]
* 大規模最適化およびリスク指向最適化の最新解法 [#j28faa9f]
オーガナイザー: 比戸将平 (IBM)
** 大規模凸最適化問題に対する勾配法 [#vdddff4d]
[[山下信雄>http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/]...
- より広いクラスに導入できるようにBregman距離へ拡張,局所...
構造をもった凸問題
min f(x)=h(x) + P(x)
- hは微分可能な凸関数,P は特殊な構造の凸関数
-- P を L1ノルムとすると L1 正則化問題
-- 単体制約(総和が1)条件付き最大エントロピーモデルやCT...
-- ハードマージンSVM
Bregman距離
- ユークリッド距離,負のエントロピーなどが含まれる
局所的エラーバウンド
- 解の集合を X* とすると,解に入っているときは 0 をとり,...
- 線形システム.Hoffman のエラーバウンド
近接勾配法
- 近接点法 + 勾配法
近接点法:x^{k+1}=argmin[ f(x) + (1/t_k) Bv(x, x^k) ]
- h は普通に勾配法,P には近接点法を適用するのが近接勾配法
** 大規模半正定値計画問題に対するソフトウェアと高速&安定...
[[藤澤克樹>http://blog.goo.ne.jp/opt-lab/]] (中央大学)
半正定値計画問題
- 多項式時間で解ける.枠組みとして広い.非凸でも緩和問題...
- 最大カット問題,ロバスト最適化,SVM
- 定式化
主問題:min C・X s.t. Ap・X=b_p, C は半正定値
内点法
- 実行可能領域の内部を通る方法
- 対数ポテンシャルや対数障壁関数などの最適解に向かう指標
- 数値安定性の問題
主双対内点法
- パス追跡法と双対定理の組み合わせ
- 主双対問題の内点の対数障壁関数の最小展を中心パスを定義...
- 理論的にも実装的にも現在最強
- 探索方向の検索とステップ幅の計算の反復になるが,探索方...
SDPAプロジェクト
- http://sdpa.indsys.chuo-u.ac.jp/
- MPI/pthread の並列計算.コアとノードへの振り分け
- 1996年→2010年:37時間→1秒 になる
-- アーキテクチャにアルゴリズムは依存しているのでハードと...
- 精度の向上:4倍や8倍精度を達成する需要がわずかにある....
- 問題への適用:行列の疎密,行や列の順序の並び替え,Schur...
** 不確実な最適化問題に対するロバスト最適化 [#m2c5c14f]
[[武田朗子>http://www.ae.keio.ac.jp/lab/soc/takeda/takeda...
ロバスト最適化法
- 不確実性を吹くんだい最適化問題
-- 最悪ケースでの損害を限定する
- 需要 u∈U の範囲にあったら min max{u∈U} u_i x_i のような...
- 応用:予測誤差の範囲を考慮,渋滞などを考慮した最短経路...
- Soyster が U が矩形の場合を考えてから長い間注目されてこ...
-- 矩形の場合は頂点だけを考えれば良かったが,Ben-TAl が ...
-- U の形状や,線形性などの制約があれば,扱いやすい問題に...
-- 問題に帰着できる制約の範囲の理論や,サンプリングを使っ...
SVMへの適用
- Caramanisらのグループ
-- 正則化項の最小化はロバスト最適化を適用すると自然に導か...
-- データそれぞれに揺れがある場合のロバスト化を考える
- ロバスト判別モデル (武田,金森)
-- 正例,負例それぞれに不確実性の範囲が決まる場合
** 時間整合的マルコフ決定過程 [#k1b8291b]
[[恐神貴行>http://www.trl.ibm.com/people/osogami/index_j....
経路選択問題
- 期待到着時間を最小化する選択 → 渋滞の時間帯に応じて経路...
- 個人的な要因によって,時間の分布が変わる場合にも対応で...
マルコフ決定過程での定式化
- 時間がかかると指数的に嫌うようなペナルティやEntropic Ri...
- ERMの制限は強く,なかなかうまくユーザのリスク嗜好を反映...
conditional tail expectation
- テール部分の確率がα以上にならないように → 時間的に多段...
- iterated risk measure:各時点での決定を再帰的に考えて求...
* 2011/11/10 (木) [#m9133e91]
* 関係データとテンソル分解 [#n6746a21]
オーガナイザー: 冨岡亮太(東京大学)
** テンソル分解を用いた関係データのモデリングとその応用 [...
[[林浩平>http://hawaii.naist.jp/~kohei-h/index-j.html]] (...
- ユーザ,商品,時間の三つの軸をもつテンソル表現を考える...
- 応用:タグ・ユーザ・アイテムのタグ推薦,人・向き・表情...
テンソル分解
- PARAFAC:次元数個のベクトルの外積をQ個足したもの
-- 特異値分解の拡張として見れるが,テンソルでは,ランクの...
- Tucker分解:コアテンソル×次元数個の行列.コアテンソルが...
-- 2乗誤差の最小化として計算される.一般には凸問題になら...
テンソル分解の確率的解釈
- Tucker分解の2乗誤差の式を考えると,残差のフロベニウスノ...
- コアテンソルの各要素の事前分布を N(0,1) とすると,出力...
-- 行列ガウス分布:行側と列側の共分散行列の外積を分散共分...
レビュー: Kolda & Bader, "Tensor decompositions and appl...
** 非定常な時系列関係データの解析に関する研究 [#m4e37559]
[[石黒勝彦>http://www.kecl.ntt.co.jp/as/members/ishiguro/...
- 関係データ:複数のオブジェクト間の関連で,関係DBの関係...
- この関係データの時系列
-- 応用:SNSの友人関係の時系列変化,顧客-商品の購買行動,...
-- 関係データを行列とすると,その時系列はテンソルになる
Infinite Relational Model (Kemp+ 2006)
- 同様の関係を持つオブジェクトをそれぞれクラスタにまとめ...
- クラスタ間の結合確率が表されたものの混合
- dynamic IRM
-- クラスタの生成事前分布がsticky prior + HDP-HMM(隠れマ...
-- 混合率は前の時間のものに影響を受ける
** Relation Extraction from the Web — Webからエンティティ...
[[ダヌシカ・ボレガラ>http://www.iba.t.u-tokyo.ac.jp/~danu...
- entity が rival_of や chief_of などの関係で結びついてい...
-- 自然言語で書かれた関係なのでノイズ多,矛盾する関係も出...
- 属性類似性(entityの属性が似ている)と関係類似性(entit...
潜在関係検索エンジン
- 日本と富士山の関係ににている,ドイツと?と聞いたときド...
関係の表現:語彙の集合で表現し,同じ関係を表すものを同じ...
- 語彙集合:二つの語でAND検索して得られた文書から抽出
- 関係間の距離は距離学習で求める
* 特別招待講演:Computational Challenges in Graph Mining ...
[[Professor Karsten M. Borgwardt>http://webdav.tuebingen....
グラフマイニング
- 大規模化が進んでいる.カーネルを使うのがトレンド.
- グラフ間の類似性評価:構造の類似と頂点・辺ラベルの類似
-- アプローチ:同形性判定,編集距離,トポロジー,カーネル...
グラフカーネル
- Walks (NIPS 2006c, JMLR 2010),最短パス (ICDM 2005),大...
- Walks:共通のWalkが多いほど類似.積グラフを作ると,その...
-- ナイーブな実装では O(n^6) の計算量だが,Sylvester方程...
-- 他の高速解法:線形方程式+共役勾配法,不動点法,スペク...
- Weisfeiler-Lehmanカーネル (NIPS 2009)
-- ノードに,そのノードに隣接するノードのラベルを集める....
-- 辺数とノード数の積のオーダーで解ける
- 遺伝学:遺伝子型から表現型を予測できる?
-- 遺伝子型も表現型も多くのデータが集まるようになった
- 現在のモデルは,SNPs 間の影響,環境の影響,祖先の影響な...
- 表現型:相関が最も強い表現型の対を探し出す
-- lightbulbアルゴリズム:高い確率で最良の解を発見できる
* 次世代DNAシーケンサ技術が求める知的情報処理技術 [#uce34...
オーガナイザー: 大羽成征(京都大学)
** 次世代シーケンサ解析で新たに求められる機械学習 [#k8238...
[[瀬々潤>http://www.se-se.jp/]](東京工業大学)
- 次世代シーケンサ:サンガー法 96本×500bp (00年代前半,誤...
** 医学研究における次世代シーケンサ技術の活用 [#e76be143]
久木田洋児(大阪成人病センター)
- 次世代シーケンサの使途:全ゲノム相関,単遺伝子疾患原因...
- 突然変異(病的影響を及ぼす)と多型(病的な影響はなく,...
-- 種類:SNP,〜数10bp(マイクロサテライト,VNTR)逆位
- SNP:Haplotype(SNP を含む系列)
- 全ゲノム相関解析 (genome-wide association study):疾患...
-- はっきりと不利な遺伝子を持つ人の特徴が分かったが,そう...
- 肺がんの遺伝子分析
-- 肺がんの多い家系について調査.200個以上の特異な変異が...
-- ホモ接合領域:父母からの遺伝子が同じパターン → 先祖に...
- 個別化医療
-- 肺癌:日本だと1/4には活性化突然変異がみつかり,その場...
-- 血液中遊離DNA:血液中に流れているDNAの断片 → 半導体シ...
** 網羅的なRNAの同定、定量、ネットワーク解析における計算...
川路 英哉(理化学研究所)
- シーケンサ:一人当たりのシーケンシングの費用が非常に下...
-- エラーはまちまち,スループットは単純に向上,配列長は一...
- 調査課題:どのRNAが転写されるか?どれくらい?制御の様子...
- Heliscope:RNAが転写される先頭の部分を読み出すシーケンサ
-- 文字列比較:95%ぐらいの精度なので,読み出したのがDNAの...
-- シグナル同定:正確な転写開始点はどこか?系列ごとにズレ...
-- シグナルの定量:観測数(?)から本当の転写量を予測する
- 転写モデル
-- 転写開始点の予測:モチーフの出現を特徴とする線形モデル
* 2011/11/11 (金) [#k2557b0c]
* 物理計測とベイズ的方法 [#p5593d7c]
オーガナイザー: 池田思朗(統計数理研究所)
** 意思決定の脳科学におけるベイズ的モデルの有用性 [#g0c83...
[[春野雅彦>http://www.bmi.jst.go.jp/researcher_3.html#har...
- なぜ脳科学でベイズ?
-- データ⇔表現 の双方向処理.尤度と事前分布に分けることに...
-- 各行動に対応するモジュールがあったとして,適切な行動は...
- 筋の冗長性:霊長類には運動制御に必要な筋肉よりもずっと...
- 手首の等尺性の制御をMRIで観察
腕の上と下の筋肉,トルクを一致させることと,二つの筋肉の...
- トルクと等筋力の調整と休憩を繰り返させると,その通りの...
- 筋活動の強さと同期するような脳活動が観測されるか? → 1...
- 筋肉の活動に関連する脳の領域を見つける → 脳の領域の数は...
- SVR/RVM ではうまくいかず,lasso正則化を使った回帰が良か...
情動の強化学習への影響
- 黒質:情動系と線条体:強化学習
-- 怖い顔・普通の顔のあとに,普通の強化学習の枠組みのタス...
-- 怖い顔にの影響を強化学習パラメータに組み込む → 最尤推...
** 人工衛星データとベイズ統計 [#s6cc858e]
[[中野慎也>http://www.ism.ac.jp/souran/kenkyusya/nakano_s...
地球磁気圏
- 地球の磁場は太陽風で吹き流された形状をしている
- その中でも歪んだ部分ではなく,地球にごく近い静止衛星な...
- 多数の人工衛星で観測しているが点での観測にしかならない ...
- 極端紫外光:プラズマ中のHe+イオンの光,エネルギーの低い...
- 高速中性粒子:地場に捕らわれている荷電粒子が電子を拾っ...
データ同化
- シミュレーション:初期条件や境界条件によっていろいろな...
- データ同化:数値シミュレーションと観測データを組み合わ...
- システムモデル:v_k はシステムで説明できない分
x_k=f(x{k-1}) + v_k
- 観測モデル
y_k=h_k(x_k) + w_k
- 基本的には状態空間モデルと同じ形だが,状態は数万〜数億...
- ベイズの定理を使って p(x_k | y_k) を求め,現在の状態を...
- 確率分布の近似:モンテカルロ近似→粒子フィルタ,ガウス分...
-- モンテカルロ+線形の折衷や,粒子生成の工夫で実際には問...
** 宇宙物理とベイズ統計 [#e1921b74]
[[植村誠>http://home.hiroshima-u.ac.jp/~uemuram/]] (広島...
- 宇宙物理学:あまりに遠くて点源にしか見えない,物理的に...
-- 手がかりは光だけ:光子の数,光子のエネルギー分布,時間...
- 変光星:単純に周期的に変わるものだけではない.昼間は欠...
- フォワードモデリングの例:ブラックホール降着流
-- 磁気流体の方程式 + 輻射輸送 → この二つの相互効果や一般...
--- 流体シミュレーションの結果から観測される光が計算でき...
- バックワードモデリング:ベイズでバックワードで予測しよう
- バックサードモデリングの例:スペクトルから銀河の距離の...
-- 銀河が遠いとスペクトルが暗くて撮れない → 銀河の色だけ...
-- 尤度:あるタイプの銀河をある距離においたときの色,事前...
- 降着円盤:恒星と並ぶ宇宙の基本構成要素の一つ
-- 重力エネルギーを解放しつつ光る.中心の天体にじわじわ落...
-- 円盤のふくれの位置をベイズモデルで推定
-- 円盤の歪みのモデルは,潮汐やレゾナンスモデルなどが提案...
- ジェット
-- 相対論的ジェット:ブラックホールの中心から吹き出ている...
-- 非常に細く絞られている:地場にプラズマが捉えられている?
-- ジェットと偏光:シンクロトロン放射なので非常に偏光が強い
-- 偏光の時間変動は法則性が全く見えない!相関があるときも...
-- 仮説:長期成分と短期成分があって混ざっているからランダ...
--- ベイズを使って成分分離に使った
** 単タンパク分子のX線回折と位相復元 [#ffa08816]
[[池田思朗>http://www.ism.ac.jp/~shiro/]] (統計数理研究所)
- タンパク分子の構造解析
- X-ray Crystalography:分子を結晶化させてX線をあてて観測...
-- タンパク質とかは40%ぐらいは結晶が作れない
- X線自由電子レーザー:波長の短いX線ではcoherentなレーザ...
-- X線回折画像から単分子タンパクの構造解析をする
-- 自由落下させながら撮る:いろいろな方向から多数の画像,...
-- 観測されるのは複素数のパワーだけなので,位相成分を復元...
-- SPR法:ベイズ系の方法で,欠測があってもOKになった
* オンライン予測 [#d6c2c038]
オーガナイザー: 畑埜晃平(九州大学)
** 組み合わせ論的オンライン予測問題 [#l88a6023]
[[瀧本英二>http://www.i.kyushu-u.ac.jp/~eiji/]] (九州大学)
- オンライン資源配分(乱択版)
-- 確率的にエキスパート i_t を選ぶ → Hedgeアルゴリズム
- オンライン最短路問題:全てのパスをエキスパートと思ってH...
** バンディットの理論と応用 [#q777a37e]
[[中村篤祥>http://prml.main.ist.hokudai.ac.jp/~atsu/]] (...
バンディット問題
- 多腕バンディット:1952年に論文があるが,1930年代からと...
-- k 台のスロットマシンから1台のスロットマシン i_t を選ぶ...
-- 割引期待報酬を最大化
- 毎回確率θiでxi(t)を得るとすると
-- 割引率γで無限界繰り返すのと,有限回 T で打ち切るのと
- exploration-expectation トレードオフの調整が必要
- 選んだアーム以外の情報も分かる場合はエキスパート統合だ...
- 訓練とテストの分離がされていると能動学習,分かれていな...
- 応用:クリニックトライアル(患者への治療)推薦,ネット...
stableな確率のバンディット問題
- スロットからの報酬 xi(t)〜Fi(x|θi) → 期待報酬μi が分か...
-- ベイズ最適な戦略と期待リグレットの最小化戦略とがある
ベイズ最適:無限界試行
- 1-armed-bandit:2台で1台の報酬は既知 p
-- 次のマシン1の Gittins Index が p より大きければアーム1...
Λ(t)=sup_N E[Σ γ^{t-1} x1(t - 1 + s)) / [(1 - γ^N) / (1...
- k-armed bandit のときは,Gittins Index が最大のものを選...
- 成功回数と失敗回数の関数を考えて動的計画法と近似で計算...
有限回 T の試行
- upper confidence index [Lai+ 1985, Aggrawal 1995]
- ε-Greedy:εの確率でexploration.達成リグレット (T))
- UCB1:報酬の上界を使う.達成リグレット (log(T))
敵対的バンディット
- 報酬の生成が,こちらのアルゴリズムを知っていて,最悪の...
- 期待リグレット:一番ましな戦略からどれだけ損が拡大したか
- Exp3アルゴリズム:Hedgeと似ているが,EEトレードオフと,...
- 達成リグレットは O(√{T}) になる
拡張
- multiple play設定:同時に複数のアームを選べる.ャッピン...
- combinatorial bandit問題 [Cesa-Bianki+ 2009]
-- 選んだ k本のアームの和のみが観測できる.経路の総和とか...
- online linear optimization 「McMahan+ 2004]
- Gaussian Process バンディット [Dorand+ 2009]
-- アーム間の相関を考える.相関はカーネルで表されて,違う...
応用
- ゲームの探索木,ニュース記事の推薦,ログデータを使った...
** オンライン凸最適化と線形識別モデル学習の最前線 [#dfcf9...
[[岡野原大輔>http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbi...
線形識別モデル
- f(x; w)=sign(w^T x) の符号で識別
オンライン学習
- 訓練系列 (x^(i), y^(i)) に対して予測を行い,その結果に...
- 学習例が冗長だと収束が早い,訓練例をその場で捨てられる...
- 基本形:訓練例を受け取り,識別が正しいかどうかを調べ,...
w{i+1}=w_i + (y α A x)^T x:αはスカラー,Aは半正定値行列
- 更新後の分類結果は y w{i+1}^T x=y w_i^T x + α x^T A x ...
オンライン学習手法
- パーセプトロン
w{i+1} = w_i + y x
-- 線形分離可能なら,有限回で収束する
- Passive Aggressive [Crammer JMLR 06]
-- w{i+1}=argmin_w[w - w_i]^2 / 2 + ヒンジ損失
- Confidence Weighted Algorithm (CW) [Crammer+ EMNLP 09]
argmin{μ,Σ} D_KL(N(μ,Σ)‖N(μ,Σi)) s.t. Pr{w〜N(μ,Σ)}[y - ...
- Adaptive Regularization of Weight Vectors (AROW) [NIPS ...
-- CW はノイズに弱いというのを改善
argmin{μ,Σ} D_KL(N(μ,Σ)‖N(μ,Σi))+λ1 L(x,y,μ) + λ2 x^T Σ x
- NHERD [Crammer+ NIPS 2010]
-- 重みベクトル w がガウス分布 N(μ,Σ) に従って分布してい...
オンライン凸最適化
- 確率的勾配降下法で解く
w=w - τ ∂L(x, y, w)
- 正則化があるときは FOBOS というのを導入
- リグレットが o(T) より小さければ最適的点に近づく
- regularized follow the leader (RTFL):正則化付きの最小化
-- リグレット O(T^{1/2})
- Online Gradient Descent
-- コスト関数が強凸である場合に適用可能
線形より高速な学習
- 入力より高速にするのは無理?
- SIMBA [Hazan+ NIPS 2011]
-- SVMをsub-linear時間で学習.Pegasos [ICML 2007] 100倍は...
-- メモリ上にサンプルを保持できることが前提,primal-dual...
** CV/PRで独自の進化を遂げる学習・最適化技術 [#s96c034c]
オーガナイザー: 木村 昭悟(NTT)
** 画像認識検索における特徴量表現 [#v182f57e]
[[原田達也>http://www.isi.t.u-tokyo.ac.jp/~harada/]] (東...
画像認識
- 特定物体認識(DB内の入力画像とのマッチ)⇔一般物体認識(...
- 難しさ:ラベル付けの曖昧さ,文脈の考慮,センマンティッ...
- 一般画像認識 (image annotation)
-- 昔はセグメンテーションとラベル付けを分けていた(Blob to...
-- 画素ごとにラベル付け (pixel to label) 2007
-- 画像にラベル付け Image Instance to Label 2004/2008
-- 潜在空間にラベル付け Concept to Label 2003/2006/1992
- Concept Learning
-- 画像を近さに応じて空間中に配置.画像のラベルを利用して...
-- 新規の画像がconcept空間のどこに配置されるかでラベル付...
- ARISTA:20億枚の画像データを利用した画像認識
- ImageNet:画像のオントロジー
-- コンテスト: http://www.image-net.org/challenges/LSVRC...
- 単語による理解で十分? → 説明文で作ったcencept空間
画像特徴
- 局所記述子→順局所特徴→空間的ピラミッド→画像特徴→カテゴリ
- 局所線形制約符号化と多符号化の比較
-- BoF → GMM → Sparse Coding (疎にする) → LCC (局所性を意...
- コードブック(局所記述子を多様体に変換してマッチ)と局...
** メモリベースパーティクルフィルタ: 状態履歴に基づく事...
[[三上弾>http://www.brl.ntt.co.jp/people/dan/]] (NTT)
オブジェクト追跡
- ビデオ中で動く物体の位置と姿勢の推定:急激な変化や遮蔽...
- 粒子フィルタが多用される → ナイーブにやると頑健にならない
- 頑健にするには? → 事前分布の改良
- 状態空間:同じ位置にあると思うモデルや,等速運動を仮定...
-- 短期の運動ではなく長期の動きに基づく状態遷移予測
-- 過去のデータを時間方向にランダムにサンプリングしてスム...
--- 滞留性(そこに留まる性質)と軌跡類似性(同じ軌道を通...
- 姿勢追跡:粒子フィルタ + 疎テンプレート照合
-- 疎テンプレート:3次元の顔テンプレートを利用
ページ名: