#author("2018-11-06T03:00:27+00:00","default:ibisforest","ibisforest")
#author("2018-11-06T08:50:01+00:00","default:ibisforest","ibisforest")
* 第21回 情報論的学習理論ワークショップ (IBIS2018) [#o6c99e03]

COLOR(#00AA00){このページはしましまが [[IBIS2018>IBIS#IBIS2018]] に参加してとったメモです.私の主観や勘違いが含まれていたり,私が全く分かってなかったりしていますので,その点を注意してご覧ください.誤りがあれば,指摘してください.}

#contents

* 11月4日 (日) :チュートリアル [#j62a711d]

* 深層学習入門 [#nb8da56d]
園田 翔(理研AIP)

- 深層学習のNN構造一覧 https://www.asimovinstitute.org/neural-network-zoo

- 深層学習
-- 深層ニューラルネットの学習法:難しいといわれていたが,2012年から学習が可能になった
-- ニューラルネットによる機械学習の応用:画像処理,音声信号処理委,自然言語処理,ゲーム,ロボティクス
-- 深層学習 ⊂ 機械学習 ⊂ 人工知能
- 応用: 認識(YOLOによる一般物体検出,階層的なダウンサンプリング構造)生成(GAN,認識NNを逆に使って乱数をアップサンプリング)強化学習(AlphaGoなど)
- ニューラルネット:任意の写像が表現できるので,工夫次第で何でもできる
- 脆弱性:敵対的事例 (adversarial example),わずかな入力の変動で認識できなくなる
- 歴史
-- 第1次ブーム(50-60年代)単純パーセプトロン時代:19世紀末にシナプスの発見,1943年のMcCulloch&Pitts,1969 Minsky&Papert 挫折,
-- 第2次ブーム(80-90年代)多層パーセプトロンとバックプロパゲーション時代:多層についての効率性の理論も出てきた,CNNやRNNなどの基本構造はほとんど登場,学習の難しさから再び冬の時代に
-- 第3次ブーム(00年代後半)2006年で教師なし特徴抽出,2011年〜から音声や画像で多くの成功例
- 浅いニューラルネットで任意の関数を表現可能:活性化関数は任意の非線形関数でよい
-- 線形の方向に延びた活性化関数で決まる形状の畝状の関数が一つのニューロン,その任意個の線形結合で任意の関数が表現できる
- 誤差逆伝播学習:SGDで解く,勾配の計算は誤差逆伝播(合成関数の微分),簡単には収束しない(錬金術)
-- パラメータが非常に冗長で高い対称性:局所解が無数にあり,学習済みパラメータの解釈は困難
-- SGDでミニバッチを使うことで局所解の脱出を期待する
- Rectified linear unit:ヒンジ型の活性化関数,閾値からの距離の情報がステップ関数とは違って残る点が最適化において有利に,タスクによってはソフトマックスがよい場合もある
- 結局何が新しいのか?:計算機パワーと大量データ,ReLUによる勾配消失予防,Dropout&Batch正則化(層毎の正則化)ResNet(昔の名前,パターン変換)Seq2SeqやGANは新しいのでは? LSTMやCNNも昔からある
- 畳み込みニューラルネット:画像認識の性能を飛躍的に向上させた.毎年,層の数が増えたが,2015年で1000層ぐらいのNNの学習が可能になり多数の層の学習は一段落
-- 畳み込みとプーリング
-- スキップ接続:2015年ごろ,畳み込み層をスキップして出力層に直接入力を繋ぐ経路もある (ResNet)
- Deep Face:2014年,中間層では元の画像が徐々に線形分離可能な空間に移動されている
- 自動運転:2016年,運転動画⇔ステアリング信号対応がend-to-endでできた
- 回帰結合ニューラルネット(RNN)
-- BPTT:過去の誤差信号に時間に応じて指数的な係数がある→発散・消失が極端
-- LSTM:指数的な係数を1に近づくようにして安定的に収束するように
- sequence-to-sequence (encoder-decoder):入力と出力それぞれに RNN,入力は一度中間層にデータを溜めて,この中間層を使って出力側の信号を生成
-- 2015年,画像にキャプション,入力のencoderはCNN,出力のdecoderはLSTM
- 生成モデル:制限ボルツマンマシン,自己回帰型ネット (ARN),変分ベイズオートエンコーダ,敵対的生成ネット(GAN)
- ARN:過去の信号が与えられたときの次の信号の分布を学習,短いデュレーションから始めて徐々にデュレーションを長くしてゆく
- GAN:識別器⇔生成器
-- GAN,DCGAN,Conditional GAN,Wasserstein GAN
- 深層学習の理論
-- 何が学習できるか?非凸最適化なのにうまくいく理由.P≫N でなぜ汎化できるのか.内部写像が学習しているもの.ニューラルネットの説明(特徴量可視化)少数データからの学習(転移学習・メタ学習)
- 何が学習できるか?
-- 表現力の問題:深層ReLUネットの近似誤差評価.中間層の素子数に対して表現力は多項式的にしか増大しないので,深さに対して指数的に増加する方が有利,証明は変わったネットを使っている
-- リスク評価:ミニマックス最適,浅いネットでも達成可能だが,深層だと滑らかさのクラスが緩くても大丈夫
- 非凸最適化
-- ある条件の下では,DLの局所最適は大域最適(線形かつoverparametrized NNの解析が主)
-- SGDによる悪い危点の回避,層の深さと幅の広さはSGDを加速する
- なぜ汎化するのか?
-- 大まかにいって汎化誤差 G≦√{P / N},P=モデルサイズ・容量,N=データ数
-- かなり緩い限界,現実はもっと良い.多くの理論限界はパラメータ数より悪い.Aroraによる
-- どこかに正則化があるはず:明確(データ拡張,ドロップアウト,重み減衰)暗黙(SGDのノイズ,早期終了,初期値,スケーリング,学習係数,ミニバッチサイズ)どれかが有効な正則化
-- VC次元などはいずれもモデルの容量としては機能していない.そもそも深層学習がうまくいっている対象は物理的に単純だから,モデルが大きい方がよい初期値をひける可能性が高い
- 内部写像が学習しているもの
-- 積分表現理論:浅いNNのパラメータはリッジレット変換で与えられる
-- 意味の階層構造,特徴量の段階的変換
-- 輸送問題の見地:座標を線形分離可能な配置に輸送されなければならない → 常微分方程式で記述してモデル化(90年代からこの見方はある)
--- ResNet:スキップ接続は常微分方程式そのもの
--- 生成モデルは最適輸送理論における輸送写像になっている
--- DAEは輸送写像

* 転移学習:基礎と応用 [#da07859d]
山田 誠 (京大・理研AIP)

準備
- 転移学習:学習データとテストデータの分布が異なる場合を扱う機械学習の枠組み
-- 例:屋内画像で学習して,屋外画像を分類,音声認識でマイクが異なる
- 教師あり学習:入力:d次元ベクトルx,出力:y,ラベル付きデータ → モデル
- 半教師あり学習:ラベルありデータとラベルなしデータの両方を利用 → ラベルなしデータ x の分布はラベルありデータ (x,y) の部分と同じ,入力 x〜P(x),出力 y〜P(y|x)
-- 大量の教師なしデータの利用目的:入力分布の推定,入力空間のメトリックの推定
- 重み付き最尤推定法
-- 対数尤度に事例ごとに x の密度を重みとして掛ける → 密な部分のデータを予測し易いようにする
- グラフに基づいた方法
-- 入力データからデータ間の隣接関係を保持したグラフを構築し,そのグラフを用いて予測を行う → 多様体を構成するイメージ
-- ラベル伝播:ラベル付きデータのラベルの一致と,ラベルなしデータに対する隣接データ間の一致性を同時に高める

転移学習
- 教師あり学習や半教師あり学習は訓練とテストで分布が異なると予測はうまくいかない
-- 転移学習はこの問題に対処するものだが,いつもうまくいくとはいえないので,可能であれば同じ分布のデータを準備するのが王道
- 転移学習
-- 教師なし転移学習:テストデータに教師がなく,テストデータは訓練データと異なる分布
-- 教師あり転移学習:テストデータにも教師データがある.訓練データの方が多いという前提
-- 半教師あり転移学習:転移先が半教師あり設定になっている
- 教師なし転移学習:重要度重み付き最尤推定(共変量シフト)
-- 訓練とテストで一致 p(y | x),p(x) はテストと訓練で違う
-- p_te(x) / p_tr(x) の密度比で事例を重み付けした対数尤度を最適化する → 基本の共変量シフト
-- EIW-ERM:重みをτ状する.p_tr(x) と p_te(x) でサポートが大きく違うと発散するを抑止
-- RIW-ERM:密度比の補完の仕方がちがう.分母にもテスト分布が入っている.サポートの重複が全くなくても大丈夫
-- この方法は,学習データが大量にあって,テストデータは一部に特化しているような場合に有利
--- 動物全般についての訓練データがあって,鳥だけに特化した推定器を作りたいとか
-- uLSIF:密度比を直接推定するようなモデルを作る.(カーネル)線形のモデルなら解析解が計算できる.RIW の工夫を取り込んだものも.
-- 注意:深層学習の内部共変量シフトは,モデル学習時の中間層の入力変わってしまうことを意味する → 転移学習とは違う
- 教師あり転移学習:一番うまくゆきやすい,p_te(x)=p_tr(x) といった強い仮定はいらない
- 教師あり転移学習:重要度重み
-- 転移元と転移先データをまとめてしまう → α と (1 - α) でそれぞれを重み付け
- 教師あり転移学習:マルチタスク学習
-- 類似した複数のタスクを同時解くことで性能を向上させる
-- 各タスクの対数尤度を全タスクについて和 + タスク間のインタラクションを示す正則化項
-- グラフ正則化:Σ{タスクの対} タスク間の類似性重み × タスク間のモデルパラメータの乖離
--- タスクのパラメータ:w_0 + v_i のような風に共通パラメータ w0 と固有パラメータ v_i で構成されるというような明示的モデル化
- 教師あり転移学習:frustratingly easyドメイン適応
-- [x_tr x_tr 0] [x_te 0 x_te] という単純な変換をして学習する → うまくパラメータが共有できるマルチタスク学習になっている
-- 線形モデルだと w0+v1 と w0+v2 のパラメータモデル化をしているのと同じ
- 教師あり転移学習:深層学習のファインチューニング
-- CNNなどの最終識別レイヤーを取り除いて,別タスク用で最終レイヤーのみを学習
- 転移学習の応用
-- 3D姿勢推定:訓練とテストでの体格の違い.照明条件の違い
--- 照明条件の方が,訓練データの一部に特化するようなものなので,性能が出る
-- 加速度センサーからの行動識別:訓練データに含まれない被験者の試験
-- ジェスチャー識別:
- 推薦
-- 研究としては教師なしが面白いが,マルチタスクが実用的にはよい
-- 転移先のデータを少しでも用意して,教師ありにした方がよい


* データ駆動型科学のための統計的推論法 [#vbaa0c04]
竹内 一郎(名工大・理研AIP)

- 機械学習のアクセルの研究→性能の向上(大量データ・モデル改良)⇔ 機械学習のブレーキの研究→安定性・安全性の向上(課程・結果の解釈)
-- 機械学習の品質保証をしよう:統計学のP値の考えに基づく方法
- 機械学習は本来は予測用だが,理解のために利用したい場合も
-- 線形モデルの重みによって,入力の重要度が分かる
-- → ただし,重みの絶対値が小さいと意味がない → 組織的手法:検定
- 検定:真値がある値のとき,極端にその値から外れた値が生じる確率(false positive ratio; p値)を計算して,これが小さいと真値がある値ではないと考える
- 特徴選択で特徴を選んでいるときは,検定での判定は使えない → 選択バイアス
- 知識駆動型科学とデータ駆動型科学
-- 知識駆動型科学:仮説を人間の経験・知識で生成してから,それを検定で検証
-- データ駆動型科学:データにアルゴリズムを適用して仮説を生成,その仮説を検定
--- Collect data first, then ask questions -- E. Candes (2015)
--- データ駆動型科学では,仮説がデータから出てきたという前提(選択バイアスなどがある)での検定が必要
- 選択的推論:selective inference / post-selective inference
- 例:薬剤効果あり vs なし:遺伝子 g2 の活動量の差 δ2=2.0
-- δ2はSD=1の正規分布に従うとして検定
-- 出版バイアス.p値が小さいと出版発表されにくい → 観測されるデータに選択バイアスが入っている
-- 機械学習で仮説を作ると,アルゴリズムにより選択がかかる
- 選択的推論:選択バイアスがあっても適切な評価ができるように

線形モデルの選択的推論
- 特徴選択の逆像:訓練データごとに特徴選択アルゴリズムが選択する特徴は変わる → 特徴選択結果が同じになる,全ての訓練データ空間中の訓練データの領域
-- 特徴選択が A y ≦ b の形式でかける (Lee+ 2016) → 特徴選択の逆像は凸多面体になる
-- → 切断正規分布を用いて棄却点を表せる

教師なし学習における選択的推論
- ポストクラスタリング推論
-- 応用例:精密医療(個別化医療)詳細な病状に合わせて治療 → サブタイプの同定のためにクラスタリングする
-- 応用例:シングル細胞解析,細胞のタイプごとに分析
- クラスタリングでサブタイプを同定してから,各クラスタに特異的な特徴を発見して統計的信頼性を与える
-- クラスタリングで生じるバイアス:そもそも分かれるように分けてるので,差があるかを調べると差があるにきまっている
-- ポストクラスタリング推論:クラスタリングをした結果が与えられたときの検定統計量の分布を求める必要
--- 逆像:同じ分割が得られるデータの領域 → k平均法ではデータに関する線形+2次の制約で記述可能
--- 凝集型階層型クラスタリングでも,線形 + 二次 の制約で記述可能
- ポストセグメンテーション推論:動的計画法による一時元系列
-- 時系列の水準が区分的に変化するのを最小二乗であてはめ → 動的計画で解ける
-- アルゴリズムが作り出したセグメント間の差異を考慮
-- 逆像は二次不等式までで記述できる
- ポストセグメンテーション推論:グラフカットによるセグメンテーション
-- グラフ上で周囲と隣接するノードと値が大きく違う点でカットして,部分グラフを切り出す
-- 逆像は二次不等式までで記述できる

選択バイアスを補正する他の方法
- 多重検定補正
-- 機械学習が出す全ての結果を考えて,多重検定とみなして補正
- データ分割,交差確認
-- アルゴリズムの訓練データと,評価データを分離する

* クエリ可能な確率的組合せ最適化問題 [#nf473d03]
前原 貴憲 (理研AIP)

- 組合せ最適化問題:有限個の要素の組合せ(E:台集合) から 条件を満たすものの(FF:実行可能集合) うち 最も良いもの(f(X;θ):目的関数)を選択
-- 有限時間で解ける:2^|E| 通りを全部調べる → 課題:計算時間,情報不足
-- 情報不足:目的関数のパラメータが厳密には分からない
- 最適化のバリエーション
-- 期待値最適化:目的関数がθ上の期待値で表せる
-- ロバスト最適化:目的関数のmin-max最適化
-- クエリ可能最適化:最適化問題の解が良くなるように能動的(←収集の方策)に情報収集
- ポストビッグデータ時代の人工知能・機械学習
-- 十分多くの高品質データがあれば解ける → ない場合にはどうするかが今後の課題
-- クエリ可能最適化は,この課題に応えるもの
- 確率的マッチング問題
-- 腎臓交換問題:移植可能な腎臓のペアを交換して移植する → 最大多数の交換を実現する=最大マッチング問題
--- 移植可能かどうかの判断は簡便な方法では低精度でしか予測できない
-- グラフ G=(V,E),枝は確率 p_e で存在,できるだけ大きなマッチングが得られるクエリ戦略

マッチング問題
- マッチング:端点を共有しない辺集合(ノードは2個以下)
- 最大マッチング問題:サイズが最大のマッチングを求める → 多項式時間で解ける
- 極大マッチング:辺をこれ以上追加できないマッチング
- 極大マッチングと最大マッチング:サイズの差はたかだか2倍
- 最大マッチングは整数線形計画問題として表現できる → 変数の範囲を連続緩和した解は最大マッチングの解の上界を与える
- 頂点被覆:全ての枝集合に隣接する頂点集合
-- 最小頂点被覆は整数線形計画問題 → 連続緩和すると,最小被覆問題の下界を与える
- 最大マッチングの連続緩和:マッチングの連続緩和は最大マッチングのたかだか2倍

確率検査モデル
- 辺eにクエリを発行するとeの存在が分かる → 存在が分かったらeは選択しなければならない
-- 最適なクエリ戦略に対して期待的に定数倍しか違わないマッチングを与えるクエリ戦略は?
-- 既に辺を選んだ頂点に接続する辺にはクエリできない → 将来の可能性をできるだけ残すようなクエリをする
-- 問題に対する上界を計算して,上界から性能を大きく損なわない解を見つける

無制約モデル
- 辺eにクエリを発行するとeの存在が分かる → 存在が分かってもeは選択する必要はない
-- クエリ数 ⇔ 解の品質に興味 → 全部の辺にクエリを出した時の解に対して,たかだか定数倍しか違わない解を求める
- 最適解を逃さないが望ましい
-- 未クエリのっ辺は全て存在すると思って,最大マッチングを計算して,このマッチングに含まれる辺にクエリを発行

* 11月5日 (月) :ワークショップ 第1日 [#x6837f4d]

* 企画セッション:離散構造処理(10:10 – 12:10) [#q1527f5d]

** 離散構造処理系:その概要と最近の研究状況について [#cbccbe15]
講演者: 湊真一(京大)

- 離散構造処理:集合理論,記号論理,帰納的証明,グラフ理論,組合せ論,確率論などを含む
-- 離散構造処理系プロジェクト:離散構造の数学的構造 → 応用分野の効率化
- 論理関数:離散構造の代表,BDDやZDDによる表現
- BDDの簡約化技術:冗長な接点の削除と,同じもののマージ → 規約
-- 指数的に小さく圧縮できる場合がある
-- 1986年,Bryant,Apply演算アルゴリズム → 圧縮したままで意味のある論理演算が可能になり,飛躍的に効率化
- 組合せ集合の演算と論理関数演算の関係:結び=OR,交わり=AND,補集合=NOT
-- BDD の効率化 → 集合演算を効率的に扱える
- Zero-suppress DD (ZDD):BDD=行き先が同じならノードを削除 → ZDD=一方の行き先が定数 0 なら削除
-- 以前は ZBDD という名前で呼んでいたが,Knuth さんの提案で ZDD にした
-- 出現頻度に偏りがあり,1 になる割合が小さいと効率的に圧縮できる
-- 1 になっている組合せの数が簡単に計算できる
-- BDD に対して大きくなる場合はあるが,たかだか入力数 n に対して n 倍
-- BDD は0/1が対称な場合,ZDDは0/1が非対称な場合
- ZDD の基本演算:代入や論理演算は論理式と同じ,カルテジアンや商集合も可能
- ZDDの応用
-- LSIの論理式の簡単化を目的としてBDDは開発された → 百万文字の論理式を数千ノードのZDDで表現可能
-- データマイニングの頻出パターンマイニングでの解集合を圧縮してメモリ上に保持
- 発展の方向
-- πDD:順列集合を表すためのBDD
-- 命題論理 → ワード単位,文字列,ランキング,分割,ツリーなどの構造を表すものも
- ZDDの圧縮アルゴリズム
-- 一般の方法:自明な小さなZDDをまとめてゆく深さ優先探索
-- Kunuthらのsimpathを一般化したフロンティア法:動的計画法による (Pythonパッケージ graphillion)
- 最近の話題
-- 数え上げは確率の計算と相性がよい
-- ホットスポットの発見:病気などの発生頻度が高い地理的に連結した領域,連結領域の列挙は困難,スキャン統計量が高い領域の発見

** グラフ集合を圧縮して活用するためのデータ構造とアルゴリズム [#ka05f1fe]
講演者: 川原純(NAIST)

- ZDD:根から葉までの経路が,集合一つに相当
-- 特定の要素を含む集合の列挙,交わり・結び
- フロンティア法:ZDDの構成アルゴリズム
-- 入力グラフを固定 → グラフ上のパスは集合に該当
-- 辺を順に調べて,辺の有無を全て列挙する.自明な枝刈り
-- 調査中とこれから調査される辺の境界部分の辺をフロンティアとよび,その構造が同じだと探索結果も同じなので,探索空間を削減できる
- ZDDの再帰構造,根の0枝や1枝から到達可能なノードはZDD
- 根ノードが1のものとそうでないものにZDDを分割できる,その対応する要素を含む集合とそうでない集合に対応
- 集合の要素数:根から葉までのノードの数は,パスに対応する集合の要素数
- 線形重み最適化:集合の要素に重みがあるとき,重みが最小と最大の集合を求める

** 離散構造処理系の機械学習への応用 [#zb68af07]
講演者: 石畠正和(NTT)

- BDD・ZDDでできること:台集合に制約があるとき,それに対する最適化や集約演算を行う
- 重要文抽出
-- 与えられた文書から重要な文を抽出する
-- 文に長さと重要度がある → 一定以下の総文字数で,重要度を最大にする問題 → ナップザック問題
-- 文字数制限をZDDで表現できる
- 影響最大化
-- ネットワーク上の影響拡散を最大にするノードの組合せの最大化
-- 影響拡散:そのノードから情報が到達しうるノードの数
-- グラフ上のノードの個数に制限
-- 影響拡散の計算にZDDを利用し,影響拡散の劣モジュラ性を利用した近似計算
-- 有効パスが存在する部分グラフを列挙するのにDDを利用
- 敵対的組合せバンディット
-- 通信に使うパスの選択などに利用する
-- リグレットを小さくする組合せ集合をバンディットで選ぶ
-- 組合せ集合の表現にDDを使うことで,現実的な時間で計算できるように
- ネットワークの信頼性最大化
-- ネットワークの辺が確率的に故障したとしても,通信が可能
-- 信頼性をK個改善できるとき,その効率を最大化
-- 改善するK個の辺のネットワークの列挙と,信頼性の評価の両方にDDを用いる

* 招待講演2:実世界AI研究のすすめ [#ceb805c8]
金出武雄(CMU)

- ロボットや画像処理を用いたシステム・メディアについて研究してきた
- NAVLAB (-1984) 自動運転,10台作った,1995年,ピッツバーグからサンディエゴのうち98.2%をCVを用いた自動運転で走行
-- 運転席でハンドルを持つように待機しているので,自動運転の方が疲れる
- EyeVision(2001年のスーパーボール)
-- 映画マトリックスでは,同じ時間の違う向きからの画像を撮るのに多くのカメラで周囲を囲んだ
-- スタジアムの周囲から何個かのカメラで追跡するロボットカメラ(33台)→ 試合中のプレーを任意の角度から見ることができる
- 研究者の仕事と希望は?「良い研究をすること」
- Allan Newell:
-- Good science responds to real phenomena or real problems.(良い科学は現実の現象,現実の問題に応答する.)
-- Good science is in the details.(良い科学はちょっとしたところにある.)
-- Good science makes a difference.(よい科学は差を生む.)
- インパクトのある研究には
-- 成功を描く,大きく考えストーリを広げる.他の人が参加することができる.
- CMUステレオマシーン:実時間で距離画像を作れる 3億円,5kW → 今ならkinnectでできる
- 3D Dome (1995),51台のカメラを付けたドームで,3D+時間方向を任意に動かして見れる画像を作った
-- 現在は多数のカメラは普通に利用されている.
-- 最初のマルチカメラの論文は,高価な環境の構築は非現実的という理由で不採録だった
- 1000台のカメラに拡張 → 冗長性が大きいので簡単なプログラムによって,姿勢の正解データの取得などに利用
- 実世界AI;現実的い存在する社会的,経済的,工業的…(あらゆる的)い価値のある問題に解決を与え,差を生み出す人工知能
-- The objective is "catch mice," not build a "better mouse trap. (a DARPA's AI Project Manager)
知識を得たいならば,現実を変革する実践に参加しなければならない(毛沢東「実践論」)
- AIの新しいきょうりょくな手法は具体的問題と困難を追求する中で生まれてきた
-- ゲーム→General problem solver,科学構造式→エキスパートシステム,不確実性と因果のある計画問題
- AI冬の時代は人工的に作られた「問題」を「手段」に押し込めようとすることが引き起こした
-- Micro Worldアプローチ,問題の自己定義とその世界での解法(アナロジー),ロジックプログラミング(第5世代コンピュータ)
- 実世界AIのFocus-worthy問題例
-- 教育AIシステム:教育はひとの生産的社会的価値の源泉,personalized education:生徒の認知プロセスと水準をしって,問題解決法を教える.人の教師はその役割に徹する
-- 製品検査,システムの異常検知:負例が少数,不良品が出てくる理由は前と同じ理由では生じない
-- 会議に参加できるAIシステム N+1:会議の議事録を作る.会議の内容を把握して,建設的に参加できるもう一人になれるか.本当に人のように振る舞えるようにするには,記号接地とフレーム問題に直面する
--- タンポポの種のように飛ぶロボットについての議論で,その時点でどれくらいのエネルギーがあれば可能か?といった詳細を計算できる.
-- 「真の」自然言語理解AI:ジョークと皮肉が分かるAIシステム.知識と推論と言葉(常識と称されるものの正体)
--- 深層ネット:知識は多くのパラメータに分散的に格納されている(一部のパラメータを変更しただけでは結果は変わらない)→これだけでは無理.ニュートンの法則のようなrestrictive(?)な知識の利用がこれから必要
- 論文は読まれなければ意味がない.読む人の分布は指数分布.
- 金出のReputation Theory:評判:論文の価値 vi で,半減期 Ti で減少
-- 論文の粗製乱造はやめよう
- 読まれない論文にある問題点:
-- そのアイデアがなければ解けない最も「簡単」な例が言えない(難しい問題を示してもダメ)
--- Ed Clark -- Formal Verification of Hardware and Software
-- 交通ルールの左方優先ルールはデッドロックを引き起こすが,それを検出できるぞといった例
-- 論文からスタートする論文,他の論文に対するアンチテーゼで,問題に
- 本当に動くものが人を納得させる
-- If the ask "Your method is interesting,. How does it work so well", they are not yet convinced.
-- If they were, they would ask "How much is it?"
- パターンの追跡問題:画面中で一致するパターンを見つける → Lucas がオプティカルフローの論文について,私は良くない論文と言ったが,彼は出版すると主張 → 引用数2万以上の論文になった → 新たな論文の価値を計るのはほぼ不可能
- 問題はあなたが解いてくれるのを待っている


* 11月6日 (火) :ワークショップ 第2日 [#h9f3a5ca]

* 企画セッション:学習理論 [#n0de2459]

** 公平性に配慮した学習とその理論的課題 [#b497f797]
講演者: 福地一斗(理研AIP)

- 公平性の問題は注目されている(ICML2017, NIPS2017, KDD2017, KDD2018などで招待講演)FAT* という国際会議も開始
- 機械学習分野での公平性の問題事例
-- 採用,与信,入試,保険などの決定に機械学習が使われているが,差別的になる可能性
-- [Sweeney 13] 差別的な検索広告のテキスト,アフリカ系の名前の検索に犯罪歴を示唆するようなテキストが有意に多く表示されていた.
-- [Angwin+ 16] 再犯リスクスコア COMPAS で,高リスク判定されても再犯しない割合がアフリカ系で多かった
-- Google翻訳:トルコ語は三人称に性別がないが,英語にするときに職業によって性差が発生する
- 公平性への要求
-- Wite House Report {Podesta+ 14]:アルゴリズムによる差別的判断に注意喚起
-- 法的要求,米Title VII(人種などによる雇用差別の禁止),日 男女雇用機会均等法,EU GDPR
- 不公平の原因:データ収集における偏向
-- 差別的なラベル:人手で付けられたラベルは差別的な場合(過去の雇用判断が差別的であったり,意識・無意識な認知の偏向)
-- 標本選択バイアス:偏った標本の収集(お金を貸した人しか返せたかどうかのデータは得られない)
- 不公平の原因:学習における偏向
-- 少数派の無視:平均的な損失を改善しようとすると,少数グループのパターンは無視される
-- 予測モデルの設計:利用する特徴量や仮説モデル空間の設定の影響
--- disparate treatment, blindness, 直接差別:センシティブな情報自体を使ってしまう 
--- disparate impact, 間接差別:センシティブな情報と依存性の強い情報を利用するとセンシティブ情報に依存した決定がなされる (red-lining効果) → 単純にセンシティブ情報をモデルから削除しても公平にはならない
- 公平性の仮定:データ+アルゴリズムの不公平 vs アルゴリズムの不公平
- 集団公平性 (group fairness) vs 個人公平性 (individual fairness)
-- 集団:センシティブ集団ごとに平均的に決定が一致
-- 個人:センシティブ特徴以外は一致しているなら同じ判断
- 入力 X,センシティブ特徴 S,観測ラベル Y,予測ラベル ^Y
- 集団公平性 & データ+アルゴリズム
-- demographic parity:センシティブ手段間で判断の割合が一致
-- 予測性能と公平性のトレードオフの効率化が目標
- 集団公平性 + アルゴリズム
-- 観測ラベルは公平という前提 → demographic parityでは逆差別を生じる
-- 観測ラベル Y と予測ラベル ^Y を一致させる → Equal Odds [Hardt+ 16]
-- demographic parity と equal odds は同時には達成できない
- 集団公平性の理論的課題
-- 公平性の汎化限界:ラベルの種類数とセンシティブ属性の値の種類数に依存し,モデルには依存しない
-- 公平学習アルゴリズムは非凸最適化になるので,その対処
- 個人公平性の理論的課題
-- 公平性制約の下でのサンプル複雑度
-- Fair Bandit [Joseph+ 17]:バンディットの腕選択の公平性
- 理論的な公平性の定義の正当化
-- delayed effect:demographic parity をしないことで,社会的少数派がさらに不利になる2次的効果の解析

** 非滑らかな確率密度推定の統計理論的解析 [#m1a6da90]
講演者: 今泉允聡(統数研)

- AISTATS2018ベストペーパーの内容
-- 密度関数の推定で ‖f* - ^f‖ の誤差を知りたい,ただし, f* が非滑らか
- 確率密度:統計量や予測には欠かせない統計分析の基盤技術
-- 推定の良さ:データ数 n に対する誤差の収束レート → 信頼区間,統計的検定などで利用できる
- 密度関数が滑らか(微分可能)な場合は多くの研究がある
-- ,β回連続微分可能なとき,カーネル法に推定量の収束レート O_P(n ^{- 2 β / (2 β + D)})
- 現実の密度関数はそんなに滑らかではない
-- 論文で報告される p 値の分布,p値が大きい論文は出版されにくい
-- 蛍光灯のスペクトル:原子ごとに出す波長にピークがある
- 非滑らか(微分できない)とほとんど研究はない
- 誤差評価の方法:誤差 = 近似誤差 + モデル複雑性
-- 近似誤差:統計モデルが f* を表現できるか → 非滑らかな状況では難しい(テイラー展開などができない)→ Szemerediの分割理論を用いて非滑らかに対処
-- モデル複雑性:モデルの大きさ,過学習のしやすさ
- 等分割:区間を分割,(連結)等分割と繋がっていないかもしれない(一般の)等分割
- I^D(超立方体)のセル:次元ごとに等分割したときのセル,ここではK個に等分割して全体で K^D 個のセル
- ステップ関数:各セルごとに定数をとる関数
- Szemeredi (1975):弱正則性補題(weak regularity lemma),ステップ関数による任意の関数 f* のカットノルムはの近似誤差は 4 / √{D log K} で抑えられる
- 統計モデルとして,セルの集合 S* 上のヒストグラムを採用する方針
- M-SDE (minimized-Szemeredi density estimator)
-- 小分割をランダムに使って,それらを組み合わせて等分割を作る,CV損失を最小化するように貪欲探索
-- pros:実装が単純,理想的にはよい収束レート,cons:分割の一致保証はない,計算コストは高い
- V-SDE (Vronoi-Szemeredi density estimator)
-- 分割がランダムではなくボロノイ分割,シードを拡張することでセルを探索
-- pros:アルゴリズムの結果は理論的に保証,計算が速い,cons:全体の収束レートは悪い,理論はD=2のみ
- 収束レート
-- M-SDE:O( 1 / √{D log K} + K^D log n / √{n} )
-- V-SDE:O( 1 / (log n)^{1/8} ),ボロノイ分割を使うことによる誤差が加わる

** 連続最適化問題に対する定数時間アルゴリズム [#u79af151]
講演者: 吉田悠一(NII)

- 定数時間アルゴリズムとは
-- 入力が性質を満たすかどうかの判定 → 満たすか満たすにはほど遠い にすると非常に効率的になる
- 例:二部グラフかどうか?
-- 部分グラフをとってきて,それが二部グラフかどうかで判定 → 遠いときには高い確率で棄却できる
- 問題の特徴
-- 加法的組合せ論と関連
-- 対象が離散的ばかり,判定問題ばかり → 使われていない → 連続最適化問題にしよう
- 二次関数最小二乗化の定数時間手続き
-- 二次関数の,2次の項は自身の2乗とそれ以外の項に分け,あとバイアス項
-- 各項の係数を k 個サンプリングしてきて,その最小二乗を解く
-- 二乗誤差は,サンプル前とサンプル語の2次の係数のmaxノルムの大きい方で抑える
--- 証明:パラメータの行列を弱正則性補題で近似できると思えば,有限個をサンプルしてもだいたい大丈夫という方針
- テンソル分解による誤差の近似
-- Tucker分解を対象 → ランクを決め打ちして残差の2乗が小さくなるように実際には分割
-- ランクはここで情報量規準で決める → ランクごとに情報量規準を求めるのを楽にしたい
-- テンソルをサンプリングしてTucker分解して残差を求める
- 学習理論と定数時間アルゴリズム
-- 学習理論は受動的なサンプリングと,定数時間アルゴリズムは能動的クエリ

* 招待講演3:Multi-armed bandits and Boundary Crossing Probabilities [#c321a134]
Odalric-Ambrym Maillard (INRIA)

- 確率的多腕バンディット
-- 腕の数 A,腕 A_i の報酬分布ν_Ai,報酬 Y_i リグレット R_T
- 基本アルゴリズム
- follow the leader,今のところ一番いいものを引く
- 過去の平均との予測の差
- UCB:upper confidence:信頼区間の上界
- 探索-活用のジレンマ:最良の腕を選ぶか,最も選ばれていない腕にするか

- KL-ucb
-- 一様に良い方策:各回の報酬の総和が o(T^α) α∈(0,1) (?)



トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS