#freeze
* 第14回 情報論的学習理論ワークショップ (IBIS2011) [#f3990102]
COLOR(#00AA00){このページはしましまが [[IBIS2011>IBIS#IBIS2011]] に参加してとったメモです．私の主観や勘違いが含まれていたり，私が全く分かってなかったりしていますので，その点を注意してご覧ください．誤りがあれば，指摘してください．}
#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の画像復元．制約を満たすとき0でそれ以外は∞になるような指示関数を導入して解く
-- ハードマージンSVM
Bregman距離
- ユークリッド距離，負のエントロピーなどが含まれる
局所的エラーバウンド
- 解の集合を X* とすると，解に入っているときは 0 をとり，そうでないときは上界となるような関数 ρ(x) を局所的エラーバウンドという
- 線形システム．Hoffman のエラーバウンド
近接勾配法
- 近接点法 + 勾配法
近接点法：x^{k+1}＝argmin[ f(x) + (1/t_k) Bv(x, x^k) ]
- h は普通に勾配法，P には近接点法を適用するのが近接勾配法
** 大規模半正定値計画問題に対するソフトウェアと高速＆安定計算による解決 --理論からスパコンまで-- [#b7c71f67]
[[藤澤克樹>http://blog.goo.ne.jp/opt-lab/]] (中央大学)
半正定値計画問題
- 多項式時間で解ける．枠組みとして広い．非凸でも緩和問題にしてSDPで解くと精度がいい．ソフトの整備が進んでいる．
- 最大カット問題，ロバスト最適化，SVM
- 定式化
主問題：min C・X s.t. Ap・X＝b_p, C は半正定値
内点法
- 実行可能領域の内部を通る方法
- 対数ポテンシャルや対数障壁関数などの最適解に向かう指標
- 数値安定性の問題
主双対内点法
- パス追跡法と双対定理の組み合わせ
- 主双対問題の内点の対数障壁関数の最小展を中心パスを定義して，Newton法でパスを追跡
- 理論的にも実装的にも現在最強
- 探索方向の検索とステップ幅の計算の反復になるが，探索方向の検索にほとんどの時間を使う
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/index.html]] (慶応大学)
ロバスト最適化法
- 不確実性を吹くんだい最適化問題
-- 最悪ケースでの損害を限定する
- 需要 u∈U の範囲にあったら min max{u∈U} u_i x_i のような目的関数と，制約の下限値 d にも範囲 d∈[d1,d2] のような範囲を考える
- 応用：予測誤差の範囲を考慮，渋滞などを考慮した最短経路問題
- Soyster が U が矩形の場合を考えてから長い間注目されてこなかった．
-- 矩形の場合は頂点だけを考えれば良かったが，Ben-TAl が 楕円に拡張してからは自明な問題ではなくなった
-- U の形状や，線形性などの制約があれば，扱いやすい問題に帰着できる
-- 問題に帰着できる制約の範囲の理論や，サンプリングを使った確率的な解法で制約を緩める方向に研究が進む
SVMへの適用
- Caramanisらのグループ
-- 正則化項の最小化はロバスト最適化を適用すると自然に導かれる結果
-- データそれぞれに揺れがある場合のロバスト化を考える
- ロバスト判別モデル (武田，金森）
-- 正例，負例それぞれに不確実性の範囲が決まる場合
** 時間整合的マルコフ決定過程 [#k1b8291b]
[[恐神貴行>http://www.trl.ibm.com/people/osogami/index_j.htm]] (IBM)
経路選択問題
- 期待到着時間を最小化する選択 → 渋滞の時間帯に応じて経路選択を動的に決めることにするともっと短時間で着けることも
- 個人的な要因によって，時間の分布が変わる場合にも対応できない
マルコフ決定過程での定式化
- 時間がかかると指数的に嫌うようなペナルティやEntropic Risk Measureなどが利用できる
- ERMの制限は強く，なかなかうまくユーザのリスク嗜好を反映できない
conditional tail expectation
- テール部分の確率がα以上にならないように → 時間的に多段階の決定をする場合を考えるとダメにになる
- iterated risk measure：各時点での決定を再帰的に考えて求める → これでやるとうまくいく
* 2011/11/10 (木) [#m9133e91]
* 関係データとテンソル分解 [#n6746a21]
オーガナイザー: 冨岡亮太（東京大学）
** テンソル分解を用いた関係データのモデリングとその応用 [#k7dd1755]
[[林浩平>http://hawaii.naist.jp/~kohei-h/index-j.html]] (NAIST)
- ユーザ，商品，時間の三つの軸をもつテンソル表現を考えるとセル数が多すぎて非常に疎になってしまう
- 応用：タグ・ユーザ・アイテムのタグ推薦，人・向き・表情・照明の顔画像，隣接行列・時間の時変なネットワーク
テンソル分解
- PARAFAC：次元数個のベクトルの外積をQ個足したもの
-- 特異値分解の拡張として見れるが，テンソルでは，ランクの計算がNP困難，軸の大きさの最小値と同じ個数の規定では完全復元できない場合が存在
- Tucker分解：コアテンソル×次元数個の行列．コアテンソルが対角の場合PARAFACと一致
-- 2乗誤差の最小化として計算される．一般には凸問題にならない．
テンソル分解の確率的解釈
- Tucker分解の2乗誤差の式を考えると，残差のフロベニウスノルム + 誤差項の和と解釈できる
- コアテンソルの各要素の事前分布を N(0,1) とすると，出力の周辺分布は行列ガウス分布になる
-- 行列ガウス分布：行側と列側の共分散行列の外積を分散共分散行列とする
レビュー： Kolda & Bader, "Tensor decompositions and applications", SIAM Review, 2009
** 非定常な時系列関係データの解析に関する研究 [#m4e37559]
[[石黒勝彦>http://www.kecl.ntt.co.jp/as/members/ishiguro/index-j.html]] (NTT)
- 関係データ：複数のオブジェクト間の関連で，関係DBの関係の意味ではない
- この関係データの時系列
-- 応用：SNSの友人関係の時系列変化，顧客-商品の購買行動，共著関係は異動で変わる
-- 関係データを行列とすると，その時系列はテンソルになる
Infinite Relational Model (Kemp+ 2006)
- 同様の関係を持つオブジェクトをそれぞれクラスタにまとめる共クラスタリング
- クラスタ間の結合確率が表されたものの混合
- dynamic IRM
-- クラスタの生成事前分布がsticky prior + HDP-HMM（隠れマルコフでときどき大きな変化を許す）で時系列化
-- 混合率は前の時間のものに影響を受ける
** Relation Extraction from the Web — Webからエンティティ間の意味的関係抽出に関する研究 [#s1776f9b]
[[ダヌシカ・ボレガラ>http://www.iba.t.u-tokyo.ac.jp/~danushka/index_ja.html]] (東京大学)
- entity が rival_of や chief_of などの関係で結びついている場合
-- 自然言語で書かれた関係なのでノイズ多，矛盾する関係も出てくる，同意語・多義語の問題
- 属性類似性（entityの属性が似ている）と関係類似性（entity間の関係の属性が似ている）
潜在関係検索エンジン
- 日本と富士山の関係ににている，ドイツと？と聞いたときドイツの最高峰を返す
関係の表現：語彙の集合で表現し，同じ関係を表すものを同じクラスタにまとめる
- 語彙集合：二つの語でAND検索して得られた文書から抽出
- 関係間の距離は距離学習で求める
* 特別招待講演：Computational Challenges in Graph Mining [#k7daf0d5]
[[Professor Karsten M. Borgwardt>http://webdav.tuebingen.mpg.de/u/karsten/]] (Machine Learning & Computational Biology Research Group Max Planck Institute for Developmental Biology and Max Planck Institute for Intelligent Systems, Tubingen)
グラフマイニング
- 大規模化が進んでいる．カーネルを使うのがトレンド．
- グラフ間の類似性評価：構造の類似と頂点・辺ラベルの類似
-- アプローチ：同形性判定，編集距離，トポロジー，カーネル（多項式時間，スケーラビリティ，属性付きラベル対応）
グラフカーネル
- Walks (NIPS 2006c, JMLR 2010)，最短パス (ICDM 2005)，大きさkまでの部分グラフ (AISTATS 200)，群論に基づく (ICML 2008, 2009)
- Walks：共通のWalkが多いほど類似．積グラフを作ると，その上でのWalksは二つのグラフに共通するWalkになる．
-- ナイーブな実装では O(n^6) の計算量だが，Sylvester方程式を使うと O(n^3) で厳密に計算可能
-- 他の高速解法：線形方程式+共役勾配法，不動点法，スペクトル分解など
- Weisfeiler-Lehmanカーネル (NIPS 2009)
-- ノードに，そのノードに隣接するノードのラベルを集める．元のラベルと集めたラベル値にハッシュ値を与える．ハッシュ値をノードラベルとするグラフで同形性を調べる．
-- 辺数とノード数の積のオーダーで解ける
- 遺伝学：遺伝子型から表現型を予測できる？
-- 遺伝子型も表現型も多くのデータが集まるようになった
- 現在のモデルは，SNPs 間の影響，環境の影響，祖先の影響などを無視していて改善の余地
- 表現型：相関が最も強い表現型の対を探し出す
-- lightbulbアルゴリズム：高い確率で最良の解を発見できる
* 次世代DNAシーケンサ技術が求める知的情報処理技術 [#uce34bda]
オーガナイザー: 大羽成征（京都大学）
** 次世代シーケンサ解析で新たに求められる機械学習 [#k823804b]
[[瀬々潤>http://www.se-se.jp/]]（東京工業大学）
- 次世代シーケンサ：サンガー法 96本×500bp (00年代前半,誤り<1%) → 第2世代 (2005〜,60億本×100bp,誤り1%) → 第3世代 (7万本×2000bp,誤り80%)
** 医学研究における次世代シーケンサ技術の活用 [#e76be143]
久木田洋児（大阪成人病センター）
- 次世代シーケンサの使途：全ゲノム相関，単遺伝子疾患原因遺伝子探索
- 突然変異（病的影響を及ぼす）と多型（病的な影響はなく，薬品への反応の違いなど）
-- 種類：SNP，〜数10bp（マイクロサテライト，VNTR）逆位
- SNP：Haplotype(SNP を含む系列)
- 全ゲノム相関解析 (genome-wide association study)：疾患の有無の群で頻度が異なるSNPs
-- はっきりと不利な遺伝子を持つ人の特徴が分かったが，そうした人の遺伝子は残りにくいため，GWASの成果は小さかった → 大規模化してより微妙な変動について調査が始まる
- 肺がんの遺伝子分析
-- 肺がんの多い家系について調査．200個以上の特異な変異が見つかった．
-- ホモ接合領域：父母からの遺伝子が同じパターン → 先祖に近親婚
- 個別化医療
-- 肺癌：日本だと1/4には活性化突然変異がみつかり，その場合に有効な薬剤が知られている
-- 血液中遊離DNA：血液中に流れているDNAの断片 → 半導体シーケンサで検出
** 網羅的なRNAの同定、定量、ネットワーク解析における計算機解析 [#k6b6137a]
川路 英哉（理化学研究所）
- シーケンサ：一人当たりのシーケンシングの費用が非常に下がった
-- エラーはまちまち，スループットは単純に向上，配列長は一度下がったがその後は向上，検査に必要な細胞数は減少
- 調査課題：どのRNAが転写されるか？どれくらい？制御の様子は？役割は？
- Heliscope：RNAが転写される先頭の部分を読み出すシーケンサ
-- 文字列比較：95%ぐらいの精度なので，読み出したのがDNAのどの部分であるのかを特定するのも，DPが必要で計算量が多い
-- シグナル同定：正確な転写開始点はどこか？系列ごとにズレがある
-- シグナルの定量：観測数(?)から本当の転写量を予測する
- 転写モデル
-- 転写開始点の予測：モチーフの出現を特徴とする線形モデル
* 2011/11/11 (金) [#k2557b0c]
* 物理計測とベイズ的方法 [#p5593d7c]
オーガナイザー: 池田思朗（統計数理研究所）
** 意思決定の脳科学におけるベイズ的モデルの有用性 [#g0c832f0]
[[春野雅彦>http://www.bmi.jst.go.jp/researcher_3.html#haruno]] (NICT)
- なぜ脳科学でベイズ？
-- データ⇔表現 の双方向処理．尤度と事前分布に分けることによる複数モダリティの統合，事前分布を導入した脳活動・行動解析
-- 各行動に対応するモジュールがあったとして，適切な行動はどうやって選ぶ？→予測される結果と目標の近さで選ぶが，その予測をベイズ風にモデル化
- 筋の冗長性：霊長類には運動制御に必要な筋肉よりもずっと多い筋肉がある
- 手首の等尺性の制御をMRIで観察
腕の上と下の筋肉，トルクを一致させることと，二つの筋肉の力を等しくする．
- トルクと等筋力の調整と休憩を繰り返させると，その通りの筋活動が見られた
- 筋活動の強さと同期するような脳活動が観測されるか？ → 1次運動野：共通に活動，背側運動前野：トルク，等筋力：腹側運動前野
- 筋肉の活動に関連する脳の領域を見つける → 脳の領域の数は膨大なので高次元の特徴でのあてはめ問題に
- SVR/RVM ではうまくいかず，lasso正則化を使った回帰が良かった
情動の強化学習への影響
- 黒質：情動系と線条体：強化学習
-- 怖い顔・普通の顔のあとに，普通の強化学習の枠組みのタスク → 怖い顔では悪い
-- 怖い顔にの影響を強化学習パラメータに組み込む → 最尤推定だと分散が大きい → ベイズの導入
** 人工衛星データとベイズ統計 [#s6cc858e]
[[中野慎也>http://www.ism.ac.jp/souran/kenkyusya/nakano_shinya.html]] (統計数理研究所)
地球磁気圏
- 地球の磁場は太陽風で吹き流された形状をしている
- その中でも歪んだ部分ではなく，地球にごく近い静止衛星などが飛んでいる領域
- 多数の人工衛星で観測しているが点での観測にしかならない → 極端紫外光観測（低温プラズマ）や高速中性粒子観測（高エネ荷電粒子）などを撮像観測し全体を把握
- 極端紫外光：プラズマ中の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/]] (広島大学)
- 宇宙物理学：あまりに遠くて点源にしか見えない，物理的に実験できない
-- 手がかりは光だけ：光子の数，光子のエネルギー分布，時間変化，偏光
- 変光星：単純に周期的に変わるものだけではない．昼間は欠測する．
- フォワードモデリングの例：ブラックホール降着流
-- 磁気流体の方程式 + 輻射輸送 → この二つの相互効果や一般相対論効果の考慮 → 流体シミュレーションの結果 ⇔ 観測結果と比較
--- 流体シミュレーションの結果から観測される光が計算できない！ → 比較できない！
- バックワードモデリング：ベイズでバックワードで予測しよう
- バックサードモデリングの例：スペクトルから銀河の距離の予測
-- 銀河が遠いとスペクトルが暗くて撮れない → 銀河の色だけから距離を推定
-- 尤度：あるタイプの銀河をある距離においたときの色，事前分布：ある投球を与えたときの距離・タイプ
- 降着円盤：恒星と並ぶ宇宙の基本構成要素の一つ
-- 重力エネルギーを解放しつつ光る．中心の天体にじわじわ落ちてくる．外側は波長の長い低エネルギー，内側は波長が短い高エネルギーを解放．クエイサー，白色矮星，銀河中心などの天体の周り
-- 円盤のふくれの位置をベイズモデルで推定
-- 円盤の歪みのモデルは，潮汐やレゾナンスモデルなどが提案されているがが，潮汐モデルが支持されそう
- ジェット
-- 相対論的ジェット：ブラックホールの中心から吹き出ている（光速の99%）
-- 非常に細く絞られている：地場にプラズマが捉えられている？
-- ジェットと偏光：シンクロトロン放射なので非常に偏光が強い
-- 偏光の時間変動は法則性が全く見えない！相関があるときも，逆相関のときも，でたらめなときも…
-- 仮説：長期成分と短期成分があって混ざっているからランダムに見える
--- ベイズを使って成分分離に使った
** 単タンパク分子のX線回折と位相復元 [#ffa08816]
[[池田思朗>http://www.ism.ac.jp/~shiro/]] (統計数理研究所)
- タンパク分子の構造解析
- X-ray Crystalography：分子を結晶化させてX線をあてて観測される周期性から電子密度を求め，分子構造を見いだす
-- タンパク質とかは40%ぐらいは結晶が作れない
- X線自由電子レーザー：波長の短いX線ではcoherentなレーザー光を作れなかった → 最近成功（SACLA：Sprng-8 の横にある)
-- X線回折画像から単分子タンパクの構造解析をする
-- 自由落下させながら撮る：いろいろな方向から多数の画像，分子の大きさの選択 → いろいろ難しい
-- 観測されるのは複素数のパワーだけなので，位相成分を復元する：HIO法というのがスタンダード
-- SPR法：ベイズ系の方法で，欠測があってもOKになった
* オンライン予測 [#d6c2c038]
オーガナイザー: 畑埜晃平（九州大学）
** 組み合わせ論的オンライン予測問題 [#l88a6023]
[[瀧本英二>http://www.i.kyushu-u.ac.jp/~eiji/]] (九州大学)
- オンライン資源配分（乱択版）
-- 確率的にエキスパート i_t を選ぶ → Hedgeアルゴリズム
- オンライン最短路問題：全てのパスをエキスパートと思ってHedgeアルゴリズムを適用 → 可能なパスは指数個あるのでダメ → 辺ごとに分けて決定(?)
** バンディットの理論と応用 [#q777a37e]
[[中村篤祥>http://prml.main.ist.hokudai.ac.jp/~atsu/]] (北海道大学)
バンディット問題
- 多腕バンディット：1952年に論文があるが，1930年代からとも言われる
-- k 台のスロットマシンから1台のスロットマシン i_t を選ぶ，選ばれたマシンから報酬 X{i_t}(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本のアームの和のみが観測できる．経路の総和とか．ComBandアルゴリズム．
- online linear optimization 「McMahan+ 2004]
- Gaussian Process バンディット [Dorand+ 2009]
-- アーム間の相関を考える．相関はカーネルで表されて，違うアームの情報も利用．
応用
- ゲームの探索木，ニュース記事の推薦，ログデータを使った評価方法
** オンライン凸最適化と線形識別モデル学習の最前線 [#dfcf9f8c]
[[岡野原大輔>http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/atlab-j.html]] (PFI)
線形識別モデル
- 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 - w^T x]≧η
- Adaptive Regularization of Weight Vectors (AROW) [NIPS 09]
-- 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内の入力画像とのマッチ）⇔一般物体認識（DBに存在しない入力画像のカテゴリを予測）
- 難しさ：ラベル付けの曖昧さ，文脈の考慮，センマンティックギャップ（特徴量と意味の差異が大きい），スケーラビリティ
- 一般画像認識 (image annotation)
-- 昔はセグメンテーションとラベル付けを分けていた(Blob to Label) 2002/2003
-- 画素ごとにラベル付け (pixel to label) 2007
-- 画像にラベル付け Image Instance to Label 2004/2008
-- 潜在空間にラベル付け Concept to Label 2003/2006/1992
- Concept Learning
-- 画像を近さに応じて空間中に配置．画像のラベルを利用してconcept空間を作る (正準相関分析を使う）
-- 新規の画像がconcept空間のどこに配置されるかでラベル付けができる
- ARISTA：20億枚の画像データを利用した画像認識
- ImageNet：画像のオントロジー
-- コンテスト： http://www.image-net.org/challenges/LSVRC/2010/index
- 単語による理解で十分？ → 説明文で作ったcencept空間
画像特徴
- 局所記述子→順局所特徴→空間的ピラミッド→画像特徴→カテゴリ
- 局所線形制約符号化と多符号化の比較
-- BoF → GMM → Sparse Coding (疎にする) → LCC (局所性を意識)
- コードブック（局所記述子を多様体に変換してマッチ）と局所記述子のマッチング（局所記述子を直接マッチ）
** メモリベースパーティクルフィルタ： 状態履歴に基づく事前分布予測と対象追跡 [#fc64f77e]
[[三上弾>http://www.brl.ntt.co.jp/people/dan/]] (NTT)
オブジェクト追跡
- ビデオ中で動く物体の位置と姿勢の推定：急激な変化や遮蔽にも頑健
- 粒子フィルタが多用される → ナイーブにやると頑健にならない
- 頑健にするには？ → 事前分布の改良
- 状態空間：同じ位置にあると思うモデルや，等速運動を仮定するモデルなど
-- 短期の運動ではなく長期の動きに基づく状態遷移予測
-- 過去のデータを時間方向にランダムにサンプリングしてスムージング
--- 滞留性（そこに留まる性質）と軌跡類似性（同じ軌道を通りやすい）の二つの粒子群
- 姿勢追跡：粒子フィルタ + 疎テンプレート照合
-- 疎テンプレート：3次元の顔テンプレートを利用
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
