第10回 情報論的学習理論ワークショップ (IBIS2007)

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

オーガナイズドセッション "Distance Metric Learning" (座長 門馬道也)

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

Masashi Sugiyama, Tsuyoshi Ide, Shinichi Nakajima, Jun Sese

  • d次元をr次元に縮約する
  • 主成分分析
    • 標本の最良近似.射影したデータを元のデータに近づける.標本の散らばりを最大化することと等価
  • 局所保存射影(LPP)
    • 近くにある標本の類似度は大きく,遠くにある標本の類似度は小さい.クラスタ構造が保存される
  • Fisher判別分析(FDA)
    • 教師ありの場合.同じクラスの標本は近くに,違うクラスの標本は遠くにする.最大でもrは(クラス数-1)にしかできない.クラス内データに多峰性があると困る.
  • 局所フィッシャー判別分析(LFDA)
    • クラス内の事例に多峰性がある場合に対応.同じクラスの近くの標本は近づけるが,同じクラスの遠くの標本は近づけない.異なるクラスの標本は遠くに埋め込む.クラス内はLPPで,クラス間はFDA.
  • 半教師あり次元削減(Semi-Supervised LFDA; SELF)
    • ラベルあり・なしの混在データ.少数のデータについて教師ありの FDA や LFDA を適用すると過学習になりやすい.
    • LFDAとPCAを混ぜ合わせたような手法にする.これらは同じ固有値問題を解いているので,これらを重みβを使った線形結合にする.できあがった関数は正則化した分散になる,
    • βが0や1以外なら,ロバストにだいたい同じ結果が得られる.
  • 次元削減と計量学習
    • 距離行列 M の階数が落ちていると M^{1/2} は次元削減とみなせる
    • 次元削減は削減する次元に制約があり,M は凸になるとは限らない

リンク不可例題からの距離学習とオブジェクト識別

小山聡

  • (x^m - x^n)^T A (x^m - x^n) の距離行列 A を求める
  • 例題の例
    • must/cannotリンク 同じクラスタ・違うクラスタになるべきデータの対
    • must の集合がS,cannotの集合をDとして,D中の点間の距離が1以上+Aが半正定値の制約の下,S内の点の距離を最小化する (Xingらの手法)
  • 提案手法:同じクラスタに入らない例は比較的容易に見つけられる.例:reference matchingなら,明らかに違う名前は分かる.
    • そこでcannot リンクだけを使って
      min (1/2)‖A‖F ,subject to A≧0,d_A^2(x^m,x^n)≧1,(x^m,x^n)∈D
      半正定値性の制約は無視しても勝手に充足される
  • これは双対問題を考えるとカーネルも利用できる.

サイド情報を用いた計量学習の効率化

Michinari Momma, Tiji De Bie, Nello Cristianini

  • 機械学習はデータの表現がカギ
  • side-information:ペア間の部分的な教師情報用いる
  • Xingらの方法は半正定値計画問題を解くので計算量が O(d^6) と大きい
    • もしラベルが全部得られていたなら:LDAで最適化でき,これはCCAと等価
    • CCAを修正してside情報を使ったバージョンを考える
  • CCA:データとラベルの相関を最大化
  • 修正して:リンク情報から同じラベルがつくようなデータをまとめて,それからCCAをかける
  • 一般化固有値問題として解けるので O(d^3) 程度で計算できる.

L1正則化付Log-Linear Model の双対化

岡野原大輔,辻井潤一

指数型分布族の部分空間上での変分ベイズクラスタリング

渡辺一帆,赤穂昭太郎,岡田真人

隠れ変数モデルに基づく同時検定用統計量最適化

大羽成征,石井信

  • 症例に影響を与える遺伝子を見つける方法
  • 発現量の平均値に差があるかどうかの検定
  • 同時に多重の検定をするので,それを利用して検出力を上げる
  • True-Posieive の期待値 ETP,False-Posietiveの期待値を考え,ETPを大きく,EFPを小さくするのがODP(optimal discovery procedure)
  • 帰無仮説が成立する部分にクラスタ構造があるときに検出力が高くなるHODPの提案(?)

15:20-17:30 ポスタープレビュー(座長 竹内純一)+ポスターセッション

  • Tsuyoshi Kato,Hisashi Kashima,Masashi Sugiyama 「Probabilistic Label Propagation on Multiple Networks」
  • Liwei Wang,Masashi Sugiyama 「Equilibrium Margin」
  • 新里隆,樺島祥介 「ランダム直交パターンに関するイジングパーセプトロンの容量」
  • 磯崎隆司,加藤典司 「自由エネルギー最小原理と "データ温度" によるベイジアンネットワークのロバストなパラメータ学習」
  • 井川数志,大橋弘忠 「人工免疫系によるパターン識別とノイズ影響の緩和」
  • 小林正樹 「位相ニューラルネットワークのパラメータの冗長性」
  • 白石友一,福水健次 「多値判別における二値判別機の組み合わせ法の学習について」
  • 鈴木譲 「MarkovネットワークとBayesian ネットワークの表現能力について」
  • 袖林和広,大羽成征,石井信 「二方向因子分析による行列データの欠損予測」
  • 孫汝軒,井之上直矢,山下幸彦 「ベクトル空間上のMahalanobis 計量のNewton-Raphson 法による数値解法」
  • 永田賢二,渡辺澄夫 「交換モンテカルロ法の温度範囲の設定について」
  • 野村真樹,Yoshio Sakurai,Toshio Aoyagi 「文字列カーネルを応用した多次元時系列データ解析」
  • 三好誠司,上江洌達也,岡田真人 「パーシャルアニーリングのレプリカ解析 -2体ソーラス符号の場合-」
  • 山崎啓介,渡辺澄夫 「可変長記号列における確率文脈自由文法のBayes汎化誤差
  • 吉野紘和,山下幸彦 「カーネルウィナーフィルタによるパターン認識
  • 力徳正輝 「トピック共起カーネルを利用した多重トピック文書分類」
  • 渡辺有祐,福水健次 「ループ展開による分配関数の解析と近似」

将棋における局面評価の機械学習〜探索結果の最適制御〜

保木邦仁

  • オセロ (10^60) やチェス (10^120) では全幅探索+簡単な評価関数で人間より強くなる

Bonanza

  • 全幅探索:全幅探索,広く浅い読み,ゲームの知識に基づく戦略の選択はしない
    • min-max だと,1局面 80 手なので,(80)^n
    • min-max + beta-cut + null move pruing & hash cut + Futility pruing:(1/4)(2.23)^n
    • 1秒に50万局面探索 → 1秒で18手先まで読める → 実際には序盤で 3^n 終盤で 5^n 程度
  • 局面評価の機械学習
    • 最適制御理論を応用して評価関数の獲得:人間の手に合わせる.
    • 最適制御理論
      J=∫0^T l(x,u,t) dt
      x(t):系の状態,u:制御変数
  • 将棋では
    J(P0....P_N-1,v)=Σi^N-1 l(Pt,v)
    Pi:局面,v:特徴ベクトル,l:全合法手の評価値の違いを測る
    l(P,ν)=Σm^M T[ ξ(pm,v) - ξ(Pm=0,v) ]
    • T はシグモイド風の関数
    • m=0: は実際に強い人が指した手
    • pm: 合法手mを指したときの局面
    • T の滑らかさは,手の散らばりに相当
    • さらに 駒割(駒の価値の交換値)になる関数が一定になる制約条件
      • 持ち駒の数,動けるマスの数に応じたボーナスなどが加わるようになっている
    • 特徴ベクトル v の大きさを,生じる頻度の高い特徴ほど大きな重みを与えた荷重L2ノルムの正則化項を加える

評価関数の最適化

  • 近傍は一定
  • 目的関数が滑らかではない → 勾配の正負だけを考えるようなおおまかな勾配降下法で最適化
  • 特徴量:約10000万:駒割,王との位置関係,王と王に隣接した味方の駒とその他の味方の3駒の関係……
  • サンプルデータ:プロ棋士3万局,ネット将棋3万局
  • 強化学習のような自己対戦はできない

オーガナイズドセッション``Massive Data Analysis'' (座長 上田修功)

大規模データ下での統計的学習研究展望

上田修功

大規模化

  • Data reduction:データスカッシング …… スケールダウン
  • One-pass algorithms:逐次モンテカルロ O(N) …… 集団で並列化
  • randomized algorithm:LSH(locality sensitive hashing) O(1) …… 近似近傍探索

one-pass SMC

  • メモリ上のD1で学習して,ディスクにD2をoneパススキャンして尤度を求める → 良くない
    • 実際には D1 にないサンプルを重視すべきだが,D1と一致したものが重視されているから

LSH

  • ハッシュが一致する確率は,距離に対して単調減少.こうしたハッシュを幾つか作る.

分散コーディングに基づく大規模データの高速探索技術とパターン認識への応用

小林卓夫

S中のベクトルxがある,離散ベクトル集合Qh

  • Qhに第k位に近い x の点
  • Qのk近傍 = Qのボロノイ分割 = ボロノイ領域に割り当てたハッシュ
  • xを,Qh に含まれるかどうかの1/0ベクトルで表す
  • 2点間の距離が遠くなると,2点のハッシュが一致する確率は急激低下
  • 精度がよく,高速に計算できるハッシュを考えるのが目標

???

  • LSH:軸に平行
  • E^2LSH (Exact Euclidean LSH):ランダムな方向
  • 一様ランダムな直交行列の利用:S を当面積の領域に,直交変換を使って分割する.

統計モデルを用いた大規模データの分類,変換,そして知識発見

樋口知之

  • 事前のノイズ処理は大切 … どれだけ捨てるかが難しい
  • 情報縮約(不可逆変換)の加減 … どれくらい縮約するかが難しい
  • これらをちゃんとやらないとよい結果はでない

オンライン処理が必要

  • Chain Structure Graphical Model
    • 状態ベクトル xt: 観測できない,ytは観測できる
    • 状態ベクトルのマルコフ性と,xt から yt が生成されるモデル
  • 過去+現在 と 現在+将来 の情報が xt に集約されている
  • 異常値処理 → xt から yt へのリンクを切るモデル
  • 欠損値 → 状態を表す潜在変数を使って扱う
  • 現在の機械学習にはモデリングの職人芸が必要
  • 経験ベイズを使ったハイパーパラメータの決定は必要
  • fixed-lag smoother: 固定区間平滑化
  • 非ガウス処理:ガウスより裾の長い分布にする / 離れた値異常値用の分布との混合モデル
    • 関数形で表すのではなく,数値のままで表現

オーガナイズドセッション``長期記憶時系列'' (座長 森永聡)

非常にゆっくりにしか変化しない時系列

長期記憶時系列その統計的推測理論と応用

矢島美寛

時系列解析

  • 時系列データを確率過程の実現値とみなしてモデルを構築
  • 予測・制御・因果関係の検出が目的

長期記憶を持つデータ

  • 乱流(Kolmogorov),経済学 ー 低周波が優勢な時系列(Granger),河川学 ー 河川の流量
  • 大きい・小さい値をとる期間が長期に継続
  • 局所的には確率的に見えるが,大域的には周期的に見える

定常過程

  • Xt: 確率過程で,E[ Xt ]=0
  • 分散(Xt,Xs) は時間差 t-s のみに依存
    自己共分散関数 γ(h)=Cov(X_t+h,Xt),自己相関 ρ(h)=γ(h)/γ(0)
  • フーリエ表現が可能
  • 短期記憶 自己相関関数の無限和が有限なら短期記憶:
    Σ{h=0}^∞ |ρ(h)|<∞
  • 長期記憶
    Σ{h=0}^∞ |ρ(h)|=∞
  • 短期評価モデルの例:ARMA
    • {Ut} は互いに無相関 Cov(t.s)=0 で,分散が一定のとき
      Xt - φ1 X_t-1 - … - φp X_t-p=Ut - θ1 U_t-1 - … - θq U_t-q
      後退作用素 B Xt=X_t-1 とし
      φ(B)=1 - φ1 - … - φp B^p,θ(B)=1 - θ1 - … - θq B^q
      とすると,次式で書ける
      φ(B) Xt=θ(B) Ut
  • 長期評価モデルの例:ARFIMA
    • 差分作用素 ∇ は,∇Xt=Xt - X_t-1=(1-B)Xt
    • d階差分作用素 ∇^d=(1-B)^d
    • 差分要素を実数化
      ∇^d=Σj^∞ Comb(d,j)(-B)^j
      このとき
      φ(B) ∇^d Xt=θ(B) Ut
      d<1/2 なら定常過程となる
  • 長期評価モデルの例:Fractional Gaussian Noise

長期記憶時系列の金融・経済分野への応用

片山直也

長期性・季節性・構造変化

  • 自己相関関数(ACF)プロット:ラグhの自己相関(ACF) ρ(h)=Cov(yt,y_t+h) / Var(yt) が縦軸,横軸はラグ(lag) h
  • 短期記憶だとACFプロットは急速に0に収束するが,長期だとそうはならない
    • 長期性:ファイナンス,マーケティングのデータ
  • 季節性=周期性:自然の影響や,税制など社会活動の周期性
  • 長期性+季節性:従属性が強く(ACFがゆっくり),周期的に(波を打つ)
  • 構造変化:mean break, trend break (一定が上昇に変化したり), variance break, memory break
    • ほとんどの場合考える必要
  • 長期性の検証がおこなわれた具体例
    • マクロ計量分析,資産評価モデル,株価収益率,為替レート,利子率

構造変化 or 長期性?の例

  • pt 物価,yt 名目GDP,wt 名目賃金,rt 10年
  • それぞれACFプロットを求めると,長期性は pt, yt, wt にはありそうだが,rtにはない
  • 1階差分 〜 εt ならI(t),d階差分 〜 FI(d)過程
  • dが大きくなるとACFの減衰はゆるやかになる
  • Δpt,Δyt Δwt はI(1)ではなく,d<0.5 の FI(d) 過程のようだ.
  • 構造変化をみるため,70年代までのデータを削除して解析すると長期記憶の影響が弱まる → pt, yt, wt は I(0) + 構造変化の可能性もある

季節性 + 長期性の例

  • 季節性と長期性をもつ時系列モデル:SARFIMA
    (1-L)^d0 (1-L^s)^ds yt=εt
    sは偶数で周期,(1-L^s)^ds は長期的な周期性を表す
  • 月次のデータを月次でACFプロットすると周期性があるが,ラグを年次にとると長期性が見える
  • 大口電力需要データ http://www.fepc.or.jp/
    • 10社のうち3社のデータが主,景気を反映する
  • SARIMA と SARIFIMA で検証する

長期記憶時系列の生理学・医学分野への応用

山本義春

  • 長期にとれるデータ:心拍変動,身体活動

心拍変動

  • 脳が副交感神経を通じて変動させている
  • 1ヶ月で300万拍ぐらい
  • 心拍数と揺らぎ(DFAスケール)をみると,健常なら線形に変化
  • Waveletで解析して可視化するとやはり違いが見れる
  • 生理学的なモデルを作って検証

身体活動

  • 腕時計につけた加速度センサー
  • 健常者とそう鬱の人を比べると,前者の方が明らかに周期的
  • 平均以下に連続して下回ると休息,上回ると活動
  • 躁鬱の人は,日中でも休息状態の期間が見られる

インターネットトラフィックの長期依存性と性能に与える影響」

阿部俊二

インターネットトラフィックの自己相似性と長期依存性

  • Web中心の閲覧だと,ファイル長分布がheavy-tailになる
    heavy-tailなトラフィックを多重すると長期依存性を有する
  • 動画像ファイルには,そもそも長期依存性がある
  • 学術SINET:トラフィックは昼に多く,夜に少ない
  • トラフィックが多い時間帯で定常的な部分を解析
  • 自己相関と区間ごとの分散を調べる → 長期依存性がみてとれる
  • 画像ファイルも自己相関をみるとおおむね長期依存性がありそう

自己相似性・長期依存性がネットワーク性能に与える影響

  • ルータ:バッファリングでコリジョンを回避
    • Poissonと長期依存性がある場合を比較:長期依存性があると大きなバッファが必要で,遅延が大きくなりやすい
  • パラメータの違う Fractional Brownian Motion モデルを組み合わせてモデル化 → バッファ長の設定などに利用

部分時系列クラスタリングの周波数解析

藤巻遼平,広瀬俊亮,中田貴之

部分時系列クラスタリング

  • sliding窓で得たデータをクラスタリングして,平均ベクトルをパターンと満たす
  • 起こる理由:固有値解析に基づく (Ide 2006)
  • 回避する方法:前処理 と 距離の定義を変える

起こる理由別バージョン

  • フーリエ変換
    • 線形フィルタで変換したときに,周波数領域の重みは変わるが,この変化を記述したのがtransfer関数
  • ノイズ部分とパターン部分とが交互に現れるとする
  • sliding窓を使うと,位相がずれたパターンがでる
  • すると,元の系列は,パターン由来の成分とノイズ由来の成分を,位相の違いを考えて足し合わせるとクラスタ中心が出る
  • このときの三つのtransfer関数が出る
    • パターン由来の項:特定の位相周波数だけが残る櫛形
    • 残りの項は:真ん中の周波数成分だけ残る
  • すると,特定の周波数しか残らなくなり,正弦波になる.
  • 位相がちょっとずつずれて現れるのが問題

上記の問題を回避するためは

  • クラスタリングの前に位相をそろえる
  • 最大周波数成分に注目して,その位相が揃うように,サンプルを循環シフトする

時系列の分野からコメント

  • 線形変換で高周波成分をとばしているので自明な結果では?
  • stacking というテクニックと似ている

分布が変化するデータにおけるモデル学習法

岩田具治,田中利幸,山田武士,上田修功

  • 時刻情報付のデータ {(xn,yn,tn)} から,最新データを予測
  • 購買データ:入力=過去の購入アイテム,出力=買ったアイテム,時刻=購入日
  • 最新時刻の予測に役立つサンプルに重み付して学習する
  • 誤差関数(損失関数):最新時刻 T での損失を考える → 経験誤差を最小にして学習
    • Σx,y P(x,y|T) J(x,y; M)
  • 誤差関数は時刻で重み付 Σn w(tn) J(xn,yn; M) … 重みは最新時刻の分布を,各時刻tの分布の混合分布うまく近似するように重みを決める.

トップ   編集 凍結解除 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:16 (2494d)