しましま/IBIS2015

第18回 情報論的学習理論ワークショップ (IBIS2015)†

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

11月25日 (水) ：ワークショップ 第1日†

オープニング†

佐久間 淳 （筑波大）

• IBISの役割：理論的基盤と社会応用の両面から先導 → 「このビックウェーブを導こう」
• ポスター発表件数 135 （うち学生発表 70）
• 参加登録者数 約350 + 当日参加

企画セッション1：学習理論†

大規模機械学習のための事例と特徴のセーフスクリーニング†

竹内 一郎（名工大）

• スパースモデリング：線形モデルの重みパラメータやカーネルモデルの事例パラメータが 0 になる
  • lasso：L1正則化項を用いる
  • SVM：損失関数にヒンジ損失関数を利用した場合
• スパース学習の計算コスト
  • 学習後の最適解において，どのパラメータが 0 になるか分からない → スパースでないモデルと計算量は変わらない → スクリーニングによる高速化
• スクリーニング：学習前にどうにか 0 になりそうなパラメータを探す
  • ヒューリスティクス：0 になりそうなもの推測して取り除きあとで最適性を確認
  • 安全スクリーニング：0 になることが保証されている

SVMの安全事例スクリーニング

• SVMのマージンの上下界を求める
  • 真の解を含む球を見つければ，その両端が上界・下界になる → マージンの外にあると分かればサポートベクトルにならないので，その事例の重みパラメータは 0 になる

高次交互作用モデルの安全事例スクリーニング

• lassoの安全特徴スクリーニング
  • lassoの双対問題を考える → 双対問題での最適解を含む領域を求める → 同様に重みパラメータのスクリーニングができる
• z1 〜 z1 z2 〜 z1 z2 z3 といった交互作用項が増えていくような構造を考える → 上位の構造が不要になっていれば，下位の構造はチェックすることなく不要と分かる

安全スクリーニング技術の応用

• 感度分析
  • 分類についても，最適パラメータを含む球だけ分かれば，パラメータ自体が分からなくても分類できる事例がある
  • 事例を追加しながら学習するとき，追加前の最適パラメータを使って，追加後の最適パラメータを含む球を計算 → 大部分（99%は）の事例は分類できた，ただし，残りを分類するにはまじめに計算する必要
• モデル選択：精度保証付きの交差確認による正則化パラメータの設定ができる ← 探索するパラメータの値をまびくことができて高速化

Fast Computation of Wasserstein Distances and Applications to Parameter Estimation†

Marco Cuturi（京大）

• 最適輸送 → 確率分布を比較する距離に使える
  • 最適輸送：Wasserstein距離 (数学系の呼び名) / earth mover 距離 (CV系の呼び名)
• 確率分布 pθ → pθ' に，「確率」を最小距離で最小の量だけ移動させる
  • 三つ以上になっても同様に，三つの分布からの最適輸送を考えれば重心のようなことができる
• 経験的な距離
  • 確率分布をヒストグラムのように離散化して，そのビンの中身を移動させるようにして定義 → 線形計画問題として計算できる
  • O( n^3 log(n) ) と計算できる．解は一意ではない．
• 正則化最適輸送
  • エントロピーによる正則化による緩和問題 → 交互最適化を用いた高速解法
  • ルジャンドル変換による双対問題
• 変分Wasseerstein問題
  • k-means はデータ点から，k個の中心を持つ混合分布までの Wasserstein 距離最小化とみなせる
  • 2個の場合は線形計画問題として定式化できる
• 正則化最適輸送：KL距離最小化の射影を繰り返す問題とみなせる （情報幾何的視点 ?）
• 画像への応用：立体モデルの中間的な状態を作れる → モーフィングのようなことができる

非スパース性と高次元データの分類†

青嶋 誠（筑波大）

• 数理統計学での判別分析：高次元でスパース性を利用し実質的に低次元での解法を実現していた → 実際のデータは非スパースじゃないか？
• 非スパース性：共分散行列の固有値や，平均・分散の差が発散する事実 → スパース性は一般には成立しない
• 以下，2クラス分類で，クラスごとの共分散が等しいとの仮定はしない，2次の無相関性を仮定
• ガウスの場合で，共分散が等しい場合は，ベイズ誤差の限界を達成できる
  • 単純に実行しようとすると共分散行列の逆行列が高次元空間では計算できない → パラメータ推定は無理
  • 小さな固有値を捨てる → スパース性を仮定している方法
• ある条件の下で分類基準を提案 → 完全な分類ができる

招待講演1：Data analytics in industrial research: a personal retrospective†

安倍 直樹（IBMワトソン研）

• 確率的木文法を用いたタンパク質の二次構造予測（with 馬見塚）
• 2項関係（推薦の利用者-アイテムみたいな）のオンライン学習（with ）
• Tax Collector Optimizer (TACOS)
  • 税金の徴収プロセスを再構築する → 作り込んだモデルではなく，マルコフ決定過程を用いた枠組みで方策の最適化を行う
  • 実際のプロセスでは，状態数は100〜200の実数ベクトルで表された状態があり，それを離散化して強化学習を適用
  • 2010年からニューヨーク州に導入し，8.22% の増収．半分ほどはこのシステムの導入によるものと推測されている
  • 強制的な手段での徴収の割合をも減らした
• Smarter Planet
  • 二酸化炭素と気候変動の関連をグレンジャー因果モデルで分析 → この前提では二酸化炭素が最も大きな要因
  • 過去の y で回帰したときとより，因子 x も加えたときに，有意に差が生じるかで因果を識別する
  • 同じ手法を，遺伝子の時系列的因果効果やTwitterのインフルーエンサーの分析にも適用
• Smarter Agriculture
  • 人口増加比率に穀物の生産が追随していない
  • 耕作地の特徴量と，穀物の遺伝情報ととを考慮することで，耕作地に適した作物を予測する
  • 実験農場から自動でデータを集めてくる飛行型・走行型のドローン
• メッセージ
  • 長期的なビジョンを持ちつつ，柔軟であれ
    • 長期戦略は重要だが，ボトムアップにやっていってそのうち形が見えてくるというのも
  • 研究者としては10年単位ぐらいで考えよう

招待講演2：Modeling-based dataset retrieval†

Samuel Kaski (Aalto University)

• http://research.ics.aalto.fi/pml

• 遺伝子データは2012年で200TBに届きそうな勢い
• 以前の生物学では論文をたくさん読んで，現状の実験を過去の成果と結び付けていた → 過去の成果をより容易に検索できるように
• 内容ベース検索
  • 各アイテム x についてモデル Mx を作り，クエリ p(q | Mx) を最大にするモデルを検索結果にする
  • x のデータが少ないので，共通モデル M と潜在変数 z を用い ∫ p(q|z) p(z|Mx) dz を計算
  • クエリはランキング学習のような比較にしている
• クエリが集合になっている場合：白血病の女性など → 考え方は同じ
• 全モデルの学習
  • マルチタスク学習をする → 大規模過ぎる・個別のデータに対する専門知識が反映されない
  • 基底になる分布を導入し，その混合モデルにモデルを制限することで対処

企画セッション2：博士課程学生招待講演†

整数格子点上の劣モジュラ被覆に対する高速アルゴリズム（NIPS2015採択論文）†

相馬 輔（東大）

• 整数格子点上の関数
  • 集合だと集合に入れるかどうかの2値しか扱えない → 整数格子点上なら多値を扱える
  • 小さい方の格子点に何かを追加したときの関数の増加分が小さいという劣モジュラ性の定義
• 欲張り法：増分 / コスト が最大の追加分を加える → 1歩ずつしか探索できないので遅い
• 提案手法：二分探索できるような，新たな評価関数を提案

能動学習による多関係データセットの構築（WWW2015採択論文）†

梶野 洸 (東大)

• 多関係データの能動学習
• 多関係データ：センマンティックWebの三つ組のような感じのデータ
• アノテーションの数を減らしたいので，能動学習によって，アノテーションしてもらうデータを選ぶ

11月26日 (木) ：ワークショップ 第2日†

企画セッション3：データ駆動型科学†

• データ分析を科学発見に活かす．

マテリアルズインフォマティクスの現状と将来展望†

田中 功（京大）

• 専門は材料工学で，情報系の利用についてどのようなことを考えているか話す．
• マテリアルズインフォマティクス：材料科学の人が頭の中でやってたことを，情報技術を用いて加速する
  • 米：オバマ大統領の Materials Genome Initiative で 製造業の復活をめざす．で注目される
  • 欧：Novel Materials Discovery，Materials' Revolution
  • 日本は世界の動向から2〜3年は出遅れ，新学術領域『ナノ構造情報』
• マテリアルズインフォマティクス
  • 材料科学：特性（合成実験の結果でたもの）→ 解析（解析実験で構造を調べる）→理論計算（物理法則などに基づく理論）→ 最適化（第1原理計算でのシミュレーション）
  • プロセス探索，構造探索，物理法則探索，材料探索 などを効率化- 結晶性物質（アルミ，塩化ナトリウムなど）を，原子を組合せて作る
  • 4原子で10億ぐらいの組合せがあるが，実質 5.5K種の化合物の構造しか分かっていない
  • 第1原理計算に基づくシミュレーション：結晶が主．単位セルの構造情報などを入れて，量子力学の理論に基づく計算．性質によって計算時間が違い，熱伝導などの計算はPCで1週間ぐらいかかり，1年ぐらいいる性質も
  • アメリカの計算結果の公開データベース https://materialsproject.org
• 研究目標：熱伝導 (W/m K)：今は 0.6 ぐらいだが，0.1 ぐらいのものを現状のDBを活用して探したい → 熱電変換素子でエネルギー効率向上など
  • 熱は格子の振動 → 振動が調和してないと衝突しして，振動の波が遅くなる
• 計算時間がかかるのでスクリーニング（過去の計算結果から計算する見込みのある候補を見つけ出す，ベイズ最適化を使う）
  • 予測に使う記述子（物理量）は簡単に計算できるものしか使えない + 物理系の人は使わない原子の基本特徴 → 特異的なふるまいをする物質でもいいスクリーニングができるようになった
  • スクリーニングのスコア順と第1原理計算の順位が一致するわけではないが，上位のものは上位にある

創薬分野における機械学習応用と情報科学への期待†

奥野 恭史（京大）

• 製薬：1品目つくるのに1000億，10年かかる
  • 新しい薬品が作りにくくなり，開発費がかかる → 無駄な実験を避けるのに情報技術を
• 創薬プロセス：活性化合物 が 疾患の原因 となる標的タンパクに作用し易いように最適化 → 臨床試験
  • 活性化合物 10^60 種，標的タンパク：10^3，結合情報：5×10^6 など多くの組合せ
• 相互作用の予測
  • 記述子：炭素の数とか，分子量とか1000種ぐらい → 既知のデータベースの作用するかどうかを SVM で予測
  • 相互作用があったものは論文になっているが，なかったものの実験結果は出てこないので，負例が少ない
• 400万件ほどの事例があるが，12万件ぐらいのデータしか現状では扱えない → 深層学習によるオンライン学習
  • Intel China と共同でCPUに最適化した Theano で GPGPU より高速に
  • SVM の 91.4% → 50万件で 92.9% → 4Mデータ + 8.8日 98.1%
• 次世代インシリコ創薬：既存の化合物について調べるのではなく，結合する化学構造自体を計算機に見つけ出させる
  • 化合物をブロックに分解して，その組合せを調べる → 10^21 種 あるので 数100の候補に絞り込む
  • ランダム生成から始めて，計算した活性スコアを高くするような化合物を探す
  • 5%ぐらいしかヒット率が60%〜70%に上がった
• 構造に基づく分子シミュレーション → 計算結果に基づくデータもどんどん生成されている

産業連関分析が環境・資源政策に果たす役割†

加河 茂美（九大）

• 気候変動に関するパネル IPCC：温室効果ガス問題，特に二酸化炭素
  • 日本では，排出量は 2009 年のリーマンショックで大きく減ったが，それ以降は伸びている
• 排出責任の考え方：消費者責任原則 ⇔ 生産者責任原則（材料などの上流産業 ⇔ 自動車産業）→ どのように責任を分担するか？
• ライフサイクル分析：一つのものを作るときに，原料の採掘から組み立てなどに至るまでをたどって排出量を計算．ISO 14001 取得には義務付け
  • 現実にはたどりきるのは難しい → 推計の部分が生じるが統一的な計測手法がない
• 産業連関表：上流 i → 下流 j にどのくらいの部品が流れたかを示したもの
  • ある製品を作るのに関係の強いグループを見つけることができる → これについて精度良く排出量を計測すれば高精度の推定ができる
• 排出移転問題：消費者が使っている排出量を他国で生産
  • 日本の生産品を排出制限義務のない国で作る場合：生産者責任だとこのようなインセンティブが働く
  • 世界多地域産業連関表：多国間にわたる貿易を含んだ産業連関表

招待講演3：理論研究とアルゴリズム・機械学習・AI†

河原林 健一（国立情報学研究所）

• 専門領域
  • Theory World：チューリング賞を多く出している．米とイスラエルが強い．
  • グラフの着色問題： n^0.2049 (2013) → n^0.1999 (2013) この差に大きな労力が払われている
  • グラフカット： O(m log^3 n) 確率的 → O(m log^5 n) 確定的
  • この分野は，講演を頼まれると，すごく専門的な話題か，ごく一般的な話題しかお話できない
• プロ野球日程をグラフ理論で計算した
  • 某球団のオーナーに反対されて採用されなかったが，そのことが某球団と対立する新聞に掲載された
• ERATOのプロジェクト：2〜3年に一度に情報系から選ばれて，6回目

• ビッグデータ・AI時代の理論研究
  • コンピュータの性能よりデータの増加が大きいので，理論・アルゴリズム
  • 巨大IT企業は強力な理論研究グループをもつ → 外に出てる研究成果，とくにうまくいかなかったノウハウが得られることが企業にとって大きい
  • 3〜5割はインド人：数学 + プログラミング ができる → 基礎力のある人の奪い合い
• スーパーエリート：数学・プログラミング・問題解決 みんなできる
  • シリコンバレーからスーパーエリートに 研究課題，データ，資金 を提供
  • 日本このスーパーエリートの育成に立ち後れている
• 理論研究者の活躍
  • Akamai を企業したのは数学者
  • Kleinberg など機械学習分野で活躍
  • NIPS / ICML の15%は理論研究者が入っている
• 理論研究者が参加するメリット
  • 最適化問題を解ける
  • 実問題から生じた抽象問題を効率的に解ける近似問題に変換するセンスがある
  • 理論のみの貢献なので，主著者にならない
• 理論研究者が参加するメリット
  • 実装とかしたくない．数学の道具を使える．自身の研究を広めることができる．
• CS のトップ会議の俯瞰：アルゴリズム・理論の人は，他の分野にもどこにでも出せるが，他の分野からアルゴリズム系には出せない
• AI系の日本のトップ会議でのvisibility：応用も理論も 2〜3 %でほとんどない
• ERATO を始めるにあたって：トップ会議に論文を出せるスーパーエリートを日本からも，理論ベースのアプローチ
  • 博士課程でトップ会議に 3〜5 本あることがあたりまえにしたい
  • 組合せ最適化の若手は強い + プログラミングコンテストなどの上位にいる → このあたりを活かしたい
  • 研究室には多様な分野の人を集めた．トップコーダーなどの人が参加してくれた．
  • 若い人が入ってこないところはダメ．35歳までに活躍できないとダメ．

成果

• 理論的にはたいしたことはないが，うまく組み合わせることで問題解決をできた
  • シリコンバレーであるような「研究課題」の供給エコシステム
• ネットワークの構造利用 → PageRank の計算を高速化
  • LU分解 ⇔ 反復法：どちらが早いかをネットワークの構造で調べる
  • LU分解などはランダムグラフであるほどおそい
  • 反復法はランダムグラフが早く，木構造などは苦手
  • コアの部分はランダム構造なので反復法を，それ以外はLU分解で
• 13〜15：トップ会議に全体で70本，STOC/FOCS/SODAといった理論以外でも40本
• 日本のvisibilityはちょっとだけ 0.5% ぐらいは貢献
  • 理論ベースの研究が世界のトップへの近道
  • アルゴリズムの理解・最適化の理解 ← トップコーダーの本当のすごさ
• 改善点：リジェクト理由
  • 現実的な動機が不明（うちは弱い）現状のトップ研究との比較，実験データが適切ではない・そもそもない
  • 現実的な動機のある問題を企業から得たい．ML/AI の研究者とのコラボ

• 大学院生・PDが主導．理論ベースアプローチ（どう役立つか分からないから身がはいらないが，役立つと分かったときにはもう手遅れなので，学生さんを教育する必要）→ 数学を重視すべき

産業界へのお願い → シリコンバレーであるようなエコシステムを作るために

• 企業の中で社内戦略ということで消さないで，問題を投げてもらうほうがいい
• 10個に1個ぐらいは面白いのでやらせて欲しい

11月27日 (金) ：ワークショップ 第3日†

企画セッション4：機械学習と組合せ最適化†

グラフカット：2次劣モジュラ関数最小化でどこまでやれるか†

石川 博（早大）

• 2値ノイズの除去：隣接する画素について，同じ輝度の画素は本来はよく隣接するが，違う輝度のものはあまりない
  • 隣接する画素の間に辺を作り，元の画像とあまり変化しないという項と，その辺の両端で画素ができるだけ変化しないという項との和で目的関数を設定
  • これを一般に，前者を単一画素に依存する項 g と，後者を画素の対に依存する項 h との和で定義されるエネルギー関数とし，これを最小化
• グラフの最小切断：辺を切断してグラフを分離する．各辺の切断にはコストがあり，そのコストの総和 → コストが非負なら最大流問題と等しい
• グラフの最小切断はエネルギー最小化と対応する
  • 画素の他に，s と t のノードを作り，s から各画素，各画素からtに有向グラフを作る．前者の辺のコストは画素が1のときの g の値，後者は0のときの値とする．s と t が分離されるような最小コストのグラフカットになる
  • 辺の重みは画素間に辺を作り，その辺の h を考えればよい
• 辺の重みについて制約を加えるとエネルギー関数に劣モジュラ性があるようにできる．
  • 2値画素：劣モなら大域最適だが，一般には部分会
  • 多値画素：画素のラベルに順序があれば劣モで大域最適，一般には近似のみ
- 1階2値（1階：隣の画素と連結している場合，MRFのクリークの大きさが1）
  • 劣モでなくても，一部の画素は最適解の一部と分かる部分解
  • 逆の値を持つ画素に対応するノードを導入したグラフを考える
• 多値で画素ラベルに順序：順序で隣接する画素間にも辺を考える，劣モでない場合でもラベルの範囲という形の部分解は得られる
• 多値一般での近似：各点ごとに今のままか，ある値αに変えるかという「移動」のみをゆるすα拡張でエネルギー関数を欲張り的に最適化する．
  • 任意の提案ラベル付けに変えるかどうかを選ぶ融合移動 → 提案ラベルでできた画像である「提案配置」を他の有力なアルゴリズムで作ることで効率化
• 画素の四つ組みの項 k を考える（3階のエネルギー）
  • 追加の仮想的な画素を導入することで1階のエネルギーに変換できる

劣モジュラ関数最大化とその機械学習への応用†

垣村 尚徳（東大）

• http://submodularity.org/ :劣モのソルバーポータル

• 膨大な離散データを効率的に捉える：文章要約問題，センサーの効率的配置
• 広告の予算配分：複数の広告メディアがあり，各消費者ごとにいろいろメディアを参照する．このとき，広告メディアを最適化して，消費者へのアピールを最大化 → 劣モになるようにモデル化
• 広告を見る人数の最大化：各メディア1回まで，合計 k 回広告が出せる．消費者ごとに視るメディアの部分集合は異なる．
  • 最大被覆問題：消費者が視聴している2部グラフについての最大被覆問題
• 貪欲法：一番視ている人が多いメディアを選び，そのメディアを視ている消費者を取り除くというステップを k 回反復する
  • 実用的には最適値に非常に近い ← 劣モなので最適値に対する下限という理論基盤も
• 劣モ視点の最大被覆問題．max f(X) s.t. |X|≦k
  • 単調性：広告メディアを増やすと消費者数は単調非減少
  • 劣モ：限界効用逓減性 → 関数の集合 X⊆Y なら f(X+e) - f(X) ≧ f(Y+e) - f(Y)
  • 単調で劣モな関数の最大化は最適解の (1 - 1/e)≒0.632 倍を保証 (Nemhauser-Wolsey-Fisher 78)
• source-side モデル
  • メディアごとにある確率で消費者に影響．複数回の広告が可能で，各回ごとにメディアが影響を与える確率は毎回独立に決まる → 影響される消費者数の期待値を最大化
  • 総広告回数と各メディアごとの広告回数に制限
  • 部分列挙 + 貪欲法で (1 - 1/e) 近似解を達成
  • source-side モデルの劣モとしての解釈 → 整数格子上に拡張した劣モ
• target-side モデル
  • 影響されるまでの影響力のしきい値を各消費者に設定．各メディアは固有の影響力があり，影響力の総和がしきい値を超えたら影響される．総広告数，各メディアの広告数に上限がある．
  • しきい値が全て 1 なら最大被覆だが，一般には劣モではない
  • しきい値が一様ランダムなら貪欲法がよいが，それ以外ではよくないが，対応できる方法を提案した．

劣モジュラ関数による構造と学習の橋渡し：構造正則化，確率的劣モジュラ†

河原 吉伸（阪大）

• 集合関数 ＝ {0,1}^d 上の実数値関数
• MRF の MAP推定 → エネルギー関数の最小化問題
  • 一般にはNP困難．1階MRFの辺の重みに制限があれば劣モ．
• 構造化正則化項：グラフ構造や階層構造の制約を加える → グループ lasso など
  • 劣モジュラ関数の連続緩和になっている
• 例
  • 一般化結合：グラフの辺が近くなるように
  • グループ lasso：グループ単位で 0 になる → 被覆関数の緩和
  • グラフのスケールフリー正則化
• 劣モで考えると汎用的な枠組みでの議論ができる
  • 近接演算子 (proximity operator) の反復計算に帰着できる
    • ロヴァース拡張で表される → 最小ノルム点アルゴリズム
    • 一般のLpノルムの場合など

11月28日 (土) ：チュートリアル†

確率的最適化から始める機械学習入門†

鈴木 大慈

• 機械学習：Field of study that gives computers the ability to learn without being explicitly programmed by A. Samuel (1959)
• 教師学習：入力と教師ラベルの組 → 未観測の入力に対するラベルを推定
• 教師なし学習：ラベルなしの入力 → 似たもの同士をまとめる（クラスタリング）
• 特徴抽出：画像などの対象を何らかの方法で数値ベクトルに変換
  • 数値ベクトルに変換してしまえば汎用的な手法を適用できる
• 般化誤差を最小化したいが，代わりに経験誤差を最小化する
• 損失関数：二乗損失，τ分位点損失，ε感度損失 -- 回帰
• 過学習 → 避けるために正則化・ベイズ推定
• 汎化誤差の漸近論：データ数 n→∞ 真と経験分布差KLダイバージェーンス → o(1/n)
  • 次元数を p とすると o(p / n) → 次元数 p が大きいと誤差が小さくならない → AIC では自由度を対数尤度に加えてこれを補正する
• AIC の最小化は L0 ノルムのペナルティを付けた最適化問題 → L0ノルムの計算は大変なので凸緩和
  • lasso：L1ノルムを用いて凸緩和 → 最適化が簡単になる
  • スパース性の恩恵：実質的次元数を d とするとパラメータの収束は d log(p) / n となり p / n よりずっと小さい
• グループ正則化：特徴のグループ（重複を許す）グループごとに0になる
• トレースノルム正則化：特異値の和＝特異値のL1正則化 → 特異値がスパース
• 凸集合：集合内の任意の2点を結ぶ線分上の点が全て集合内にある
• 凸関数：関数上の2点を結ぶ線分上の点は，全て関数値以上である
• L1のような不連続関数で使える勾配 → 劣勾配：部分不可能な点で接して，関数とは重ならない直線の勾配
• 平滑性：勾配の変化がリンプシッツ連続（2点を射影してもノルムがたかだかL倍）
• 強凸性：最小点がある
• 近接勾配法：f(x) + ψ(x) の最小化で，勾配を計算するとき f(x) だけ勾配を使った勾配法，更新則には近接写像を用いる．

確率的最適化：大規模データを扱うために用いられることが多い

• 分類：バッチ型（訓練データはまとめて与えられ何度でも使える）とオンライン型（訓練データが一つずつ与えられ1度ずつ用いる）
• オンラインが多手法：x_t ← x_t - g_t (g_t はデータ一つを用いた勾配・劣勾配)
  • 勾配の大きさの期待値の上界 G と初期値と最適解の差の上界 D から期待誤差の上界は 2 G D / √{T} → 強凸ならさらによい収束
• 確率的双対平均化法 (SDA)：過去の劣勾配の平均を用いる
• 確率的最適化は O(log(n)) だけ勾配法より速い
• バッチ型の確率的最適化
  • データは固定で，1回の更新で1データのみを利用
• 確率的分散縮小勾配法 (SAG)：十分に近い参照点の勾配を使い勾配の分散を縮小する

劣モジュラ最適化に基づく特徴選択と構造正則化入門†

河原 吉伸

• 劣モジュラ構造を用いて，組合せ的な L0 正則化とデータ構造を利用した L1 正則化の最適化
• d個要素の集合 V のべき集合： 2^V は {0, 1}^d のd次元の格子上の点に対応する
• 集合関数：単調性＝大きな集合の方が大きな値をとる．対称性＝S と全集合からSを引いた集合とで同じ値
  • 特徴選択は，集合関数を経験誤差とし，それを最大化する特徴の部分集合を選ぶ問題といえる
• 劣モジュラ性：F(S) + F(T) ≧ F(S∪T) + F(S∩T)，∀S,T ⊆ V
• べき集合は格子点で表されるので，集合関数は格子点上に実数軸をとった関数となる
  • ロヴァース(Lovász)拡張：この関数を格子点以外の値で補完して実数緩和する方法 → その関数が凸関数になっている
  • 逓減性：F(S + i) - F(S) ≧ F(T + i) - F(T)，S⊆T⊆V, i∈V＼T
  • 劣モジュラ関数の例：被覆関数，エントロピー，カット関数
  • 最適化：最小化→厳密なアルゴリズム，最大化→精度保証付きの近似アルゴリズム

特徴選択と劣モジュラ

• 特徴選択：非0要素の数がk個以下での誤差関数の最小化
  • 特徴に対し，誤差関数小さくなると大きくなる集合関数を定義すると劣モジュラ性を備えるように設計できる
  • たかだかk個の変数を使う → 集合の大きさの制約下での劣モジュラ関数の最大化
• 貪欲法：(1 - 1/e)近似
  • 空集合から始めて，関数値を最大にする要素を追加するステップを反復

劣モジュラ関数を用いた構造正則化

• 劣モジュラ関数最小化： O(|V|^5 M + |V|^6) … M の評価関数呼び出し
  • 対称性があると O(|V|^3)，グラフ表現可能な関数はさらに小さい
• 構造のある制約問題：グラフ構造，階層構造，グループ構造
  • 画像の背景抽出：近傍などがまとめて変化を受ける構造を組み込むと精度が向上
• 結合正則化 (fused regularization) → グラフ上で隣接する要素のパラメータが近い値＝カット関数のl∞ノルムによるロヴァース拡張になっている

深層学習入門†

岡谷 貴之

順伝播型NN

• ユニット：線形関数 + 活性化関数 → 多層にして構成する → 確率的勾配降下で最適化
  • 昔からある活性化関数 ソフトマックス・シグモイド → 深層学習で利用される活性化関数 ReLU，pReLU，MaxOut
• 多層関数の鞍点 [Pascanu-Dauphin+ 14] をクリアできれば大域解に
• 勾配消失問題：層をたどるごとに勾配の大きさが小さくなってしまう
• モメンタム：前回修正量の 0.5〜0.9 倍を今回の勾配更新に活かす
• 重み減衰：重みの発散を防ぐために重みの2乗

自己符号化器

• 砂時計型のネットワークで特徴表現を得る
• スパース正則化：中間層が入力数より大きければ恒等写像になってしまう
  • Σj D_KL(ρ‖^ρj) ← 平均活性度 ρ を小さくする

畳み込みネット

• 画像分野では，現在は20層もめずらしくない
• 一般画像認識：画像をカテゴリに分類する → 非常によい性能を示して注目された → 現在は人間の認識精度を超える
  • 畳み込みネットはそれ以前にも顔認識に有効であることは知られていた
• 最大プーリングは情報の損失が大きすぎるとHinton先生は述べているが，実用上は最も有効な方法
• CNNでは勾配消失問題が生じにくいが，結合が疎であることが影響しているからではと予測されている．
• 最終段の全結合層は全体が95%のパラメータを占めるが計算量での占有量は10%ぐらい
• Alexnet [Krizhevsky+ 2012]:63M → VGGNet [Simonyan+14]：パラメータ数140M, GoogLeNet パラメータ数 6.8M
  • GoogLeNet のパラメータ数が少ないのは全結合層の簡略化によるものだが，プログラムとしては複雑になっている
• CNNの改良：Hexagonalカーネル（フィルターの形を変えて層ごとに向きを変える）Network-in-Network, Deeply-supervised-net, Recurrent CNN
• 転移学習：大規模データで学習したCNNの最終層だけを入れ換えることで，他のタスクに特徴を使い回すことができる

再帰NN

• 再帰結合 → 時間方向に展開すると時間方向の順伝播ネット
  • 深層学習のかかえる勾配消失問題に昔から直面していた → LSTM

応用

• 画像記述：画像についての説明文を生成する → まだまだ変な文章が生成され発展途上
  • CNNで獲得した画像特徴ろ，言語生成用の回帰NNに入力する
• 画像生成：CNNが何を学習しているかの分析にも繋がる
  • Deep Dream：banana などのラベルを最も活性化させる
  • 画家のスタイルを再現：学習済みのCNNに，絵画と写真を入れたときの活性状態を利用して生成

Take Home Message

• 自分の問題に適用したい → 茨の道を覚悟されたし！（パラメータ，モデル，サンプルどれも巨大）
• 決まったタスクならライブラリを使う，pretrainedモデル，転移学習などを使おう

多重検定法入門†

瀬々 潤

• 機械学習の問題として，結論の因果関係が分かりにくい
  • 科学分野では再現性の向上が問題となっている
• データが増えてくると，普遍性のある現象以外にも，偶発的に生じた現象もよく観測されるように
  • 統計的有意性：まれにしか生じない現象であることを確認する
  • ホールドアウトデータ：独立したデータを使って確からしさを確認する
  • 目的の問題を解くのに入力がどれも役に立たない場合などは特に問題
• 新規の発見 ← 予め定めた有意水準以下の発生率であった場合
  • 複数の検定を行う場合 → いずれかの検定で「まれな」状況が生じるのは「まれではなくなる」 → 多重検定の補正
• 補正の規準：
  • Family-Wise Error Rate (FWER)：複数回検定をしても，1回も偽正が生じない確率をα以下に
  • False Discovery Ratio (FDR)：有意と判定された検定のうち，偽正がα以下になるようにする．FWER より緩い規準．

FWERに基づく補正

• Bonferroni法：FWERをα以下にする．有意水準を α/検定数 に補正．簡潔でよく利用される．
  • P[いずれか1個の偽正] ≦ Σi P[検定iが偽正]
  • 検定数に依存して有意水準を変更するので，検定数が増えると有意だったものが，有意でなくなったりする
• Holm法：棄却された仮説はもう帰無仮説に従わない → 棄却されたものを取り除きつつBonferroni法で有意水準を変更することを繰り返す．
• Westfall-Young法：Bonferroni/Holm の理論的な上界は緩いという問題
  • モンテカルロ検定を用いて，仮説間の従属性を扱える
  • データの並べ替えとp値の最小値を求めることを繰り返すことでFWERの分布を経験的に求めて検定に用いる
• Tarone法：偽正にならない検定はBonferroniの補正項から除外可能なことを利用

FDRに基づく補正

• 帰無仮説に従っているにもかかわらず棄却された検定の，棄却された検定に対する割合を制御．q値とも呼ばれる．
• Benjamini-Hochberg法 (BH法)：仮説の p 値は [0,1] に一様分布と仮定 → p値の小さい方から k 番目のFDRの期待値は α k / M なので，p値が小さい方から並べたとき，このFDR値を超えるまでの検定を有意と考える
• Storey and Tibshriani法 (ST法)：BH法のp値が一様であるという仮定は，p値が1に近く大きいとこでしか成立しない → 近似曲線を用いて推定

朱鷺の杜Wiki

• 機械学習
• 学会・研究会
• 書籍・資料
• 論文英語
• フリーウェア
  • python
  • numpy
• テストデータ
   
• 日本語版PRML本
• カーネル多変量解析
   
• 人気ページ
• 今日の人気ページ
• ページ一覧

参加しよう

• Wiki超入門
• 練習用ページ
• 数式の表示
• こびとさん
• 編集用ID: ibis
• パスワード: 「VC次元」のVのフルスペルで最初だけ大文字
   

  最新の30件

  2024-05-31

  • 人工知能学会全国大会
  • しましま/人工知能学会全国大会2024

  2024-04-13

  • python

  2024-04-09

  • K-NEL
  • K-NEL/errata

  2023-11-22

  • PRML/errata2

  2023-11-21

  • PRML/errata1

  2023-11-01

  • しましま/IBIS2023

  2023-10-29

  • IBIS

  2023-06-11

  • しましま/人工知能学会全国大会2023

  2023-03-28

  • Book

  2022-11-27

  • 朱鷺の社

  2022-11-24

  • しましま/IBIS2022

  2022-07-08

  • AutoTicketLinkName

  2022-06-17

  • しましま/人工知能学会全国大会2022

  2021-11-13

  • しましま/IBIS2021

  2021-10-29

  • 回帰分析

  2021-06-11

  • しましま/人工知能学会全国大会2021

  2021-03-07

  • MenuBar

  2021-02-15

  • python/numpy

  2020-12-22

  • 特異値分解

  2020-12-18

  • complement naive Bayes

  2020-11-27

  • しましま/IBIS2020

  2020-10-17

  • Paper/bias-on-the-web

  2020-07-16

  • F値

  2020-06-30

  • DataSet

  2020-06-24

  • バイアス-バリアンス

  2020-06-10

  • Paper

  2020-03-15

  • PRML
  • PRML/link

カウンタ

• 累計: 14632
• 今日: 2
• 昨日: 4