#freeze
* 第9回 情報論的学習理論と機械学習研究会 [#c67314dd]

このページはしましまが [[第9回電子情報通信学会 情報論的学習理論と機械学習研究会>IBISML#IBISML009]] に参加してとったメモです．私の主観や勘違いが含まれていたり，私が全く分かってなかったりしていますので，その点を注意してご覧ください．誤りがあれば，指摘してください．

* 6月19日 (火) [#a19692da]

** パラメトリック計画法を用いたS^3VMの最適化手法に関する一考察 [#m8b1e48b]
○小川晃平・竹内一郎（名工大）・杉山　将（東工大）

- 半教師あり学習：クラスタ仮定の下，分離曲面を求める
- ラベルなし事例については，分類誤差を小さくするようにラベル自体もパラメータとして目的関数の最小化に含める
- 予測誤差の大きさの影響を決めるパラメータCを徐々に大きくするアニーリングが最適化には有効 → この温度変化の幅と計算時間はトレードオフ
- 変化幅を無限小にしたときの計算を可能に：各Cにおける最適解のパスを計算．次の二つのステップを繰り返す
-- 連続パスステップ：予測ラベルを固定し，C を増加させる
-- 離散パスステップ：C を固定し，予測ラベルを一ずつ反転

** Learning Non-Linear Classifiers with a Sparsity Upper-Bound via Efficient Model Selection [#f7b13174]
○Mathieu Blondel・Kazuhiro Seki・Kuniaki Uehara（Kobe Univ.）

- 求めるパラメータαi の非0要素の数はたかだか B に
- SVMの損失項が [1 - yi β Si, 0]^2，βの非0要素はたかだか B に，Si は事例間の類似度行列の第i行
- coordinate 最適化：各軸＝一つの事例ごとに最適にしてゆく
-- 軸を選ぶ順番にも工夫

** Online Prediction under Submodular Constraints [#ve6ce8a0]
○Daiki Suehiro・Kohei Hatano・Shuji Kijima・Eiji Takimoto（Kyushu Univ.）・Kiyohito Nagano（Tokyo Univ.）

- 順列のオンライン最適化
-- 参加者は時刻 t で係数 ct を出力（毎回揺らぐ）参加者に順列を与えると順列を ct とで決まる損失が出る
-- リグレットが最小になるように順列を決めるには？
- Online Gradient Decent法：projection と decomposition と呼ばれるステップを交互に実行
- 候補になる順列は多すぎる → 劣モジュラ → projection と decomposition が多項式時間で計算できる
-- 一般には n^5 ぐらいだが，劣モジュラ関数が集合の大きさだけに依存すると n^2 のオーダで解ける

** Improving the Variable Setting of Softmax Selection From an Information-Theoretic Viewpoint [#m312d2c5]
○Kazunori Iwata（Hiroshima City Univ.）

- 強化学習の行動選択で，状態価値から行動を決めるときにソフトマックスを使う
-- ソフトマックスで探索-活用のトレードオフを調整するβを大きくするスケジュール
- 時間に対して線形に増加させると傾きのパラメータの調整が難しい
- MDPの典型集合：MDPで生成されるエピソードの集合で，その要素の系列が発生する確率が1-εより大きい ⇔ βの設定に対応する
-- この典型集合が，ちょうど最適報酬を得られるような集合と一致すれば最適

** ［IBISML研究会賞記念講演］単語間論理制約付きトピックモデル [#v986ad7b]
○小林隼人（東芝）セッション

- トピックモデル：単語のクラスタリング
-- [Andrzejewski+ ICML2009] Mustリンク と Cannotリンク の and 表現の実現 → 制約にリンクの or 表現を埋め込む拡張をする
- [Andrzejewski+ ICML2009] の方法
-- MustリンクとCannotリンクでグラフを作り，Mustリンクの推移的平方をまとめて集約
-- Mustリンクの推移的平方で結ばれたものの同じクラスタ内での生成確率は等しく，Cannotリンクで結ばれていると一方のクラスタでは生成確率を0にする
-- この制約をどうやって実現するか？ → ディリクレ森分布
-- ディリクレ木分布：木構造で，中間ノードのところでディリクレ分布に従って子ノードに分かれる分布
-- 最初にCannotリンクを枝分かれさせてしまい，その他への確率の割り当てを強める．次に無関係なノードを枝分かれ，その後，mustリンクのグループごとにまとめた木を最終的に先端に付ける
- ORやNOTを入れた拡張
-- 単語確率を等しくするEqualPrim，確率を0にするZeroPrimのプリミティブを導入
-- 論理式をDNF形式で表現するとプリミティブを使って
- さらに，漸近的に同値になる関係を使い，プリミティブ数を削減して効率化
- ある単語群を一つにまとめる（不要語クラスタなど）とか，ある単語が出たら別の単語も出るという含意関係なども表せる

** ［招待講演］大規模データを対象とした分析処理の高速化に関する取り組み [#m6617b5e]
○鬼塚　真（NTT）

BigData
- BigData：大規模データからの知識発見
-- 類似データ，頻出データ，ネットワーク分析などに取り組む
- BigData分析の問題点
-- 大規模・高速化：分析ロジックと，分散処理システム，データの特性全てについての理解が必要 → 人に依存
- 高速処理可能な分析を短期間に構築できるように
-- 抽象言語から分散プログラムを導出できるように

MapReduce：分散処理のプログラミングモデルであり，システム
- 分散処理の負荷分散や可用性を気にせず丸投げできる
- key値ごとに分散処理するMapと，それらの結果をまとめるReduceの組み合わせ
- 関数型言語の map と reduce のインターフェースを分散環境で実行するもの
- 分散環境としてはやや制約はあるが，シンプルな構成になっている
- 例：標準偏差の計算
-- 1回目でデータ数と平均を，2回目で平均からの二乗偏差を計算 → 2回MapReduce
-- 2次，1次，0次のモーメントを同時に計算すれば → 1回ですむ
- MapReduce関連の研究
-- 高速化：反復数の削減：決定木，グラフ，機械学習，shuffleの削減：MapReduceデザインパターン，HaLoop(変化しないデータはキャッシュ)，データ格納の最適化，複数処理の高速化，JOIN処理：OLAP，行列積の演算
-- 適切なアルゴリズムな選択：宣言的言語，JOINのプラン選択，コストベースのパラメータ最適化

PJoin
- スター型のスキーマ：あるテーブルを中心に，関連するデータを持ったテーブルがたくさんぶら下がっている → ハッシュキーの検索が多い
- 事前にハッシュキーの計算をやっておくことで高速化

K-dash：ランダムウォーク・リスタートの計算
- あるノードからランダムウォークリスタートして定常確率の高い上位k個を出したい
- 反復法で解くのと，固有値問題（LU分解）で解く方法 → 後者の方針
- 類似度検索：定常確率の上限を求めて枝刈り

** 特徴選択に基づくLocality-Sensitive Hashingによる高次元データの高速類似検索方法 [#s4bab070]
○此島真喜子（富士通研）

- 高次元データの類似検索を高速に
- LSH：元の空間における距離の関係が写像後のハミング距離となる
-- バイナリへの変換は行列を掛けてしきい値 0 で切る
- 比較手法
-- ランダム射影：ランダムに平面を決める
-- スペクトラルハッシュ：周波数領域でのハッシュ
-- minimal lossハッシュ：超平面の境界と最近傍の学習データとのマージンを最大化
- 提案手法：特徴選択
-- 最も精度のよい超平面から，目標ビット数になるまで選択
-- 最近傍で同ラベル、異ラベルの距離の比を重要度として高い順から選択
-- 超平面の勾配の学習が難しいデータでも精度は良い
- 提案手法の計算時間は学習データの数に比例（全ての学習データをなめて最近傍を選択するため）

** リアルタイムなレコメンデーションに向けた半教師ありLatent Dirichlet Allocationによるトピック抽出法 [#z87de25f]
○池田泰弘・川原亮一・斎藤　洋（NTT）

- 単純にLDAをMapReduceに載せた以上に高速化したい
- 半教師ありLDA：
-- 文書ごとにDirichlet事前分布のパラメータを設定し，その文書が所属しているとするカテゴリが良く出るように事前分布のパラメータを調整
-- 所属ラベルがない文書についても，その利用者が前に閲覧した文書にラベルがあれば，その影響を残す
- こうした工夫でGibbsサンプリングの収束が速くなる

** 損傷による振動特性の変化に分類アルゴリズムを用いた鋼構造建物の地震被害検知システムの開発 [#k443f57a]
○山口真矢子・倉田真宏（京大）

- 構造物の安全性確認：外見だけからは内部の構造部分の安全性の危険性は分かりにくい → しかし現在は目視
- 構造ヘルスモニタリング：建物に設置したセンサーで建物の状態をモニタリング
-- 1) 損傷の有無，2)損傷のある階・位置，3) 重要性，4)耐久力推定 → 現在は2まで
- モード解析＝建物固有の固有振動数の分析 → 1カ所の損傷があると0〜0.6%程度の変化が生じる
-- システム同定：観測された波形をフーリエ変換で固有周波数を求める．直接線形法，周波数領域分解法
- 決定木で，損傷箇所の数を推定してみた

* 6月20日 (水) [#v1519c94]

** Density Difference Estimation [#m626746a]
○Masashi Sugiyama（Tokyo Inst. of Tech.）・Takafumi Kanamori（Nagoya Univ.）・Taiji Suzuki（Univ. of Tokyo）・Marthinus Christoffel du Plessis・Song Liu（Tokyo Inst. of Tech.）・Ichiro Takeuchi（Nagoya Inst. of Tech.）

- A と B から C を計算するときに，A と B を個別に推定するとそれぞれの誤差が重なって C の誤差が大きくなる場合 → C(A, B) を直接推定した方がいい！
-- 密度比推定：P(A) と P(B) から C: P(A) / P(B) を推定 → 比を直接推定
- 今回は密度差の推定：P(A) - P(B) → L2距離の推定とかに使える
-- 個別に滑らかなモデルに合わせると，密度差は過小評価になる → 直接推定しよう
- LSDD : Least-Squares Density-Difference Estimation
-- 密度差モデル g(x) とサンプル f(x) の正則化付き二乗損失を最小化
-- g(x) はカーネルを使ったモデル
-- 理論的にもいろんな保証
- L2距離の推定
-- 二つの推定法の定式化があるが，それの線形結合を考え，混合比の適切な値を求めた

** On a Non-asymptotic Analysis Using Large Deviation Principles in the Multiarmed Bandit Problem [#e85d130f]
○Junya Honda・Akimichi Takemura（Univ. of Tokyo）

- 多腕バンディット：探索と活用のトレードオフの調整
- 理論限界：期待値最大でない台を選ぶ (係数) log n ぐらいはプレイしてしまう
- 既存の UCB : 効用の上界が大きい台をプレイする戦略
- DMED (Deterministic Minimum Empirical divergence
-- 理論下限の推定値よりプレイ回数が少ない台があればそれをプレイ
- DMED戦略の分析では下限の (係数) の推定値について考える必要
-- Sanovの定理の拡張などを使った解析

** 完全データと不完全データの混合におけるベイズ潜在変数推定の精度 [#zb7b5798]
○山崎啓介（東工大）

- 潜在変数の分布：推定誤差をKLダイバージェンスで評価
-- 一部の潜在変数が与えられる半教師ありの環境を想定
-- 学習モデルは真のモデルを含む，潜在変数の値を観測データから推定できることを知っている
-- 最尤法とベイズ法で推定 → ベイズ法の推定がよい

**［招待講演］医用画像：ニーズとシーズ [#p1fe85d2]
○岡田知久（京大）

- 日本では医工連携が進んでない
- MRI：地場を使って体の内部を撮影
-- 処理によっていろいろな画像を作れる：血流の強調，水分の移動など

診断とは
- 経験則が支配 → 1992年にEvidence-based Medicine
- MRIの大量画像をみて判断するのは大変 → 撮像方法を工夫してより診断し易いように
- 側頭葉てんかん：海馬の左右差で起きる → 患者80+健常28人のSVMで識別したらかなりあたった
- 脳の標準化：脳のデータを標準化して特徴抽出
-- 解剖学的標準化：標準的な脳に合わせる → 組織分画化：組織ごとにわける → 平滑化 → 統計処理
- 慢性疲労症候群：前頭葉の萎縮
- アルツハイマー：海馬萎縮は他の認知症の方が大きい傾向 → 個人差
-- 年に1〜2%が普通だが，アルツハイマーだともっと多い
-- 臨床的に診断が可能なころにはだいぶ進行している
- ADNI:Alzheimer's Disease Neuroimaging Initiative
-- 海馬とそのその近くでは（嗅内野）近くの方が進行が急速 
-- 自動計測 → 91.6-98.2%
-- てんかんでも人が気づかない部分が検出された → 画像処理の可能性を示す

MRI 画像を使った脳の活動の分析
- 顔の認識部位：刺激のありなしを繰り返し，それに対する脳の応答をMRIで見る
-- 独立成分分析を適用し，時系列での変化の傾向をみる
- 複雑な右手運動学習：小脳は学習の過程では働いているが，慣れてくると活動低下
- 脳脊髄液の影響による変動 → ICA でクリーニングできたりする
- 脳のネットワークの分析：部位間の活動・休止の部位の繋がり
-- ネットワークを相関で測ってSVMに入力し判断
-- ページランクを使って中心性を求めた → 部位がうまく特定できた
- 脳内水分子：周りの分子に動きが制約される → 脳内の繊維の向きが分かる (diffusion tractography)
- 大脳視覚野：詳細な分析により1次〜4次の視覚野の区別が付くように
- 解剖学的正規化の精度：しわを広げて合わせるという別の方法を使うとだいぶ違う見え方
- 周波数領域での分析：k空間
- 圧縮センシング：高精度の画像の復元
-- 細い動脈の関連などが分かる：脳梗塞の1/3は細い血管の問題
-- CT ではでるが，MRI だけでも分かるように

心臓
- 止めるわけにはいかないので静止画がとりにくい → 拍動の周期に合わせてとる
- オプティカルフローで動きを観察
- super resolution imaging

** Winning the Kaggle Algorithmic Trading Challenge with the Composition of Many Models and Feature Engineering [#n5e9f549]
○Ildefons Magrans de Abril・Masashi Sugiyama（Tokyo Inst. of Tech.）

- Kaggle で行われたアルゴリズム取引のコンペ
- 証券市場での値動き：注文動向や売り買いの指し値の動きを予測
-- 訓練データに近いところの影響を重視 → 予測に使う区間をあとになるほど広げる．区間の幅も欲張り的なアプローチで最適化
-- 意味のある特徴量を使う → backward eliminationの特徴選択
- 予測はランダムフォレスト

** 多次元パラメータを有する区間定常無記憶情報源に対してのMDL原理に基づく変化検出アルゴリズム [#t933c6af]
○金澤宏紀・山西健司（東大）

- 時系列の変化点検出：MDL原理に基づく
- 2段階符号化：モデルの記述長とそのモデルの下でのデータの符号長の和を最小に
- 時系列の全ての区間で同じパラメトリックモデルを使うが，区間ごとにパラメータセットは異なる → Peasewise Stationary Memory-less Source (PSMS)
- 1次元のものは今までの研究
-- Fisher情報量に応じてパラメータ空間を分割 + 総記述長が小さくなるように動的計画法で適当なパラメータセットの変化を探索
-- Fisher情報量に基づく分割：その区間でのFisher情報量に比例した幅で区切る
-- パラメータの変化にはペナルティがあり，同じパラメータが続き易いように
-- 提案するアルゴリズムの期待冗長度は 定数 + O(√サンプル数)
- 今回は多次元への拡張
-- 一つ目のパラメータで離散化したのち，離散化した各区間をさらに二つ目のパラメータで離散化
-- この方法で分割しても問題が生じない条件：正規分布やガンマ分布あたりは大丈夫
トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS