機械学習プロフェッショナルシリーズ スパース性に基づく機械学習 読書メモ

サマリー

スパース学習とは、データセットに含まれる特徴量のうち、重要なものだけを選択してモデルを構築する機械学習の手法となる。スパース性は、モデルに含まれるパラメータのうち、値がほとんどゼロであることを意味する。スパース学習のメリットは、モデルがより解釈可能になることで、重要な特徴量が選択され、不要な特徴量が除外されるため、モデルの予測結果を説明することが容易になる。また、スパース性は過剰適合を防ぐためにも役立つ。

ここでは機械学習プロフェッショナルシリーズ「スパース性に基づく機械学習」をベースにこのスパース学習について述べる。

スパース学習の最も一般的なアプローチは、L1正則化を用いた線形回帰で、L1正則化は、モデルに含まれるパラメータのうち、影響の小さいものをゼロに近づけることで、スパース性を実現するものとなる。L1正則化はLasso回帰とも呼ばれている。今回は読書メモを記載する。

機械学習プロフェッショナルシリーズ スパース性に基づく機械学習

「どんな分野でも効率的な処理には優れたアルゴリズムが欠かせない。
スパース(疎)という性質に着目すると、最短の道が見えてくる。
定義や必要な数理、考え方の基礎から、
アトミックノルムなどの発展的な内容までを1冊で学ぼう。」

第1章 はじめに

スパース性(sparseness)
疎性
まばらであること
高次元ベクトルのほとんどの要素がゼロである
スパース性が有効である典型的な例
ゲノムの個人差からの予測(特定の病気のかかりやすさ、治療の有効性)
ゲノムの個人間の変異は数百万箇所で起こるが、特定の病気のかかりやすさに関連しているのはそのごく一部
数百万箇所全ての変異が特定の病気にどのように影響するかを推定するには、その一人同じオーダーのサンプルを集めなければいけない
病気と関連している変異が少数であるというスパース性の仮定を用いることで少ないサンプルで調べることができる
考えるべき問題
統計的な問題
いかに現実的な過程を用いて少ないサンプル数での推定を可能とするか?
計算量の問題
いかに組み合わせ爆発を防いで現実的な計算量で推定を行うか
3種類のスパース性
要素単位のスパース性
多くの要素がゼロで少数の要素が非ゼロの値をとる
グループ単位のスパース性
各行があらかじめ定義した1つのグループに対応し、各行が全てがゼロか全てが日ゼロの値をとるかに分かれている
あらかじめグループを定義することで、考えうるゼロ/非ゼロのパターンを制約し、より少ないサンプル数でも推定を可能にする
ゲノム変異からの予測では、遺伝子が作用する際には遺伝子Aが活性化すると遺伝子Bが活性化し、それが別の遺伝子Cを活性化する
経路をグループとして考え、ある変異が病気に寄与するかどうかを考える代わりに、経路単位で、病気に寄与するかどうかを考える
行列の低ランク性
共通のd変数の上に定義されたT個の関連する学習課題を同時に解きたい場合
推定すべき係数の数はdT
単純にdT次元のベクトルを推定する問題として捉える
もしくは各列にd個の係数を持つd行T列の行列を推定する問題
行列がランクrであるということはT個の学習課題に共通するr個の要因が存在するということ
低ランク行列はベクトルとしてみると全くスパースではない
行列の特異値をみると、行列のランクに等しい特異値だけが非ゼロで、他の特異値はゼロ
グループを定義しなくても、変数のグルーブや、複数の課題に共通する要因補まとめて学習可能
次空間データの解析や推薦システムなどにも有効
自然言語処理でのn-グラムなどの超高次元かつスパースな特徴ベクトルでは、分類器が少数の変数の組み合わせではできず、本書の対象からは外れる

第2章 データからの学習

2.1 訓練データと汎化
新しい事柄を理解したいとき、とのようにするのか?
新しい言葉を覚える
ワインの好みを覚える
ワインの場合は味見をして好きであれば、産地、生産農家、ブドウの種類、ラベルに書かれた言葉などを覚えておき、次に似たものを注文する
例示することが容易でも、ルールとして言い表すことが難しいもの
手書き文字の書き方バリエーション
N個の列からなる訓練データ (training data)を(xi, yi)ni=1
xi ∈ ℝdは入力ベクトル
ワインの例だとxiは産地、ブドウの種類などを数値表現したもの
手書き文字だとxiは入力画像の濃淡値
yiはラベル
ワインの例だとワインの味を5段階で評価したもの
手書き文字だと0〜9のいずれかの整数
データから学習するとは、訓練データが何らかの規則によって生成されている時に、データを生成する規則をなるべくよく模倣し、再現すること
統計的機械学習
データを生成する規則として(xi, yi)が 同時確率P(x,y)から独立同一に生成されているという状況を考えたもの
判別モデル
入力ベクトルが与えられた元で、どの程度良くラベルyを予測できるか
ワインの評価の場合は「期待二乗誤差」L(f)=𝔼x,y[(y – f(x))2] 最小化する関数fは条件付き期待値
手書き文字の場合は期待誤差分類率L(f) = 𝔼x,y[I{yf(x) < 0}]や相対エントロピー(relative entropy)を考えることが一般
回帰(regression)
入力ベクトルxの上の連続関数を訓練から推定する
分類(classification)
手書き文字認識のように離散的な出力yをとる関数を推定する
ラベルが離散的であっても条件付き確率P(x|y)は連続関数であり、苔を推定すれば分類問題もとける
2.2 分散とバイアス
2.3 正則化
過学習を防いで汎化性能(未知のデータへの対応能力)を高めるためのテクニック、 モデルに「正則化項」つけることでモデルの形が複雑にならないように調整する
パラメータベクトルのノルムを制約することで仮説集合の大きさを制御する
ノルム(norm)
平面あるいは空間における幾何学的ベクトルの”長さ＂の概念の一般化
ベクトル空間に対して「距離」を与えるための数学の道具
ノルムの定義された空間を線形ノルム空間あるいは単にノルム空間という
種々のノルム
ユークリッドノルム
|x|2 := √(|x1|2 + ・・・+|xn|2)
最大値ノルム
|x|∞ := max(|x1|,…,|xn|)
説明
パラメータベクトルのノルムを罰則項として用いたり、制約することによる分散の減少
2.4 交差確認
2.45 制約付き最小化問題と罰則項付き最小化問題の等価性
制約つき最小化問題と罰則つき最小化問題の統制

第3章 スパース性の導入

3.1 オッカムの剃刀
ある事柄を証明するために不必要に多くの要因を仮定してはならない
同じことが証明できるならなるべく少ない要因を用いるべきだ
機械学習の過剰適合とのアナロジー
少ない数の要因で 説明することの数学的表現
ゲノム変異から病気のかかりやすさを予測する問題
予測するべき対象をx
予測するべき値をy
xから導かれるありとあらゆる可能な仮説Φ1(x),…Φd(x)をまとめてベクトル𝜱(x)とする
Yの予測値
要因の数はωの非ゼロ要素の数
s(w)=|supp(w)|
3.2 𝓁1ノルム正則化
ベクトルωのℓ1ノルム
xi…xdの絶対値の足し算
マンハッタン距離
碁盤の芽のように縦横垂直しかない道路で、斜めに移動できない世界の距離を表す
ℓ1ノルム正則化つき学習
1次元での説明図
2次元での説明
劣微分の定義
3.3 人工データを用いた説明
次元d=200,真の非ゼロ要素の 数k=10の人工データ実験の結果
Optimalはサンプル数が10〜20の間で テスト誤差が急激に小さくなる
次に良いのはL1
n=50の付近で誤差が最大値の1/2を下回る
L1では非ゼロの要素は70まで減少(200から)
L2では非ゼロの要素は200
人工データ実験で得られた重みベクトルwの係数
3.4 文献に関する補遺
ℓ1ノルム最小化の歴史はガリレオやラプラスまで遡る
理論的なアプローチは1965年のLoganの博士論文
信号とそのフーリエ変換は同時にスパースになることはない
アプローチ
天文学
地球物理学
電波天文学
統計学
計算神経学
スパースコーディング
機械学習
ベイズ理論
サポートベクトルマシン

第4章 ノイズなしL1ノルム最小化の理論

4.1 問題設定
線形方程式の、観測変数の次元が道数ベクトルの次元より少ない場合、方程式のかいは一位ではない
未知数ベクトルがスパースであることが期待できる場合は、 方程式を満たすベクトルの中で最もスパースなものを買いとするのが自然
虱潰しに探す必要があり効率的でない
ℓ1ノルム最小化で効率的に計算する
w*∈ℝdを未知のスパースな高次元ベクトルとする
線形な少数の観測(上式)からベクトルw*を復元する
線形方程式は「劣決定(underdetermined)」
逆問題(inverse problem)
サンプル数nが次元dに比べて小さい
線形方程式からw*を一位に決めることができない
例
EEGやMEGの信号から脳活動を推定する
一般化された最小化問題
y=(y1,…,yn)T∈ℝは観測値を並べたベクトル
X=[x1,…,xn]T∈ℝnxdは各行が観測モデルにおけるベクトルxiの行列
4.2 幾何学的考察
最小化問題を幾何学的に考察
ピンク色の直線は、最小化問題の等式制約を満たすwの集合
水色の領域は、真のベクトルw*を中心として、ℓ1ノルムが減少する方向からなる錐
D(∥・∥1;w*)をℓ1ノルムの点w*における降下錐とよぶ
降下錐
(A)は水色の領域と唯一w*で交わる
(B)はw*を端点とする線分で水色領域の内部で交わる
水色領域の内部はℓ1ノルムが真のスパースベクトルw*よりも減少する方向
共通する部分があるということはw*がℓ1ノルム最小化問題の解でないことを意味する
真のスパースベクトルw*がℓ1ノルム最小化問題の唯一の解である必要十分条件
部分空間N(w*)および降下錐D(∥・∥1;w*)は小さければ小さいほどよい
部分空間N(w*)の次元はd-nなので、N(w*)はサンプル数が増えるほど小さくなる
降下錐は真のスパースベクトルw*がスパースであればあるほど小さくなる
スパースでないとDは半平面となる
4.3 ランダムな問題に対する性能
行列Xの要素がある分布からランダムに得られているという仮説
スパースベクトルw*がℓ1ノルム最小化問題の唯一の会である必要条件
集合Cの統計的次元 (statical dimension)
代表的な凸錐の統計的次元
定理
ランダムに与えられた問題に対する最小化問題の成功確率
成功確率は比較的狭いサンプル数の領域で0%から100まで変化する
その領域におけるサンプル数が統計的じげんによく対応している
4.4 文献に関する補遺
どのような性質が満たされれば望みの結果が得られるのか
どのような条件でこのような性質が(高い確率で)満たされるのか

第5章 ノイズありL1ノルム最小化の理論

はじめに
雑音を含む線形観測からスパースなベクトルを復元する問題
観測雑音を考慮し、真のベクトルが厳密にスパースでない場合にも対応
5.1 問題設定
雑音を含む線形観測(上式)から未知の高次元ベクトルw*を推定する
𝝃iは雑音項で平均0,分散がσ2で独立であると仮定
ℓ1ノルム正則化に基づく回帰係数ベクトルw*の推定は最小問題として上式となる
Lassoあるいは基底追跡雑音除去(basis pursuit denoting)
雑音なしモデルとの違い
観測モデルが雑音項を含む
凸最適化問題のwが真の回帰係数ベクトルw*にぴったりと一致する確率ではなく、 二乗誤差∥w-w*∥22を定量的に評価する
回帰係数ベクトルw*が厳密にスパースであるとは仮定しない
観察雑音𝛏iは正規分布に従うと仮定
容易に劣ガウス雑音(例えば行っていく感情の一様分布)
観察が雑音を含むため、推定量wが真の回帰係数ベクトルw*にぴったり一致することはない
サンプル数nが増えるとともに誤差がどのようになるかを非前筋的に解析する
w*が厳密にスパースではない場合に対応するため、 誤差の上界は推定誤差と近似誤差の和として任意のkに関して上式のようになる
真の回帰係数ベクトルw*の絶対値の上位k個の係数からのみなるベクトルをws*とする
残りの係数からなるベクトルをws*=w*-wsk*と定義する
推定誤差項Eestはkの増加関数
近似誤差項Eapproxはkの減少関数
推定誤差項
推定誤差項の分子に現れる量は一定の誤差をLのに必要なサンプル数の目安を与える
真の回帰係数ベクトルw*の次元dが非常に大きくても、kが小さい限り、たかだか次元の対数のオーダーのサンプルがあれば良い
5.2 ランダムな問題に対する性能
ベクトルwがたかだかk個の非ゼロ要素を持つこと
定理
次元dが指数関数的に増加しても必要なサンプルの数は多項式でしか増えない
正則化パラメータλnに関する条件は、雑音項σ2に依存する
非ゼロ要素の数kには依存しない
正則化パラメータλnを選択する時には、真の回帰係数ベクトルw*に関する事前知識が不要
確率的に成立する
系
パラメータqが非ゼロ要素の個数(q=0)とℓ1ノルム(q=1)を内装する役割を演じている
5.3 準備
ヘルダーの不等式
ヘルダーの不等式の特殊な場合
コーシー・シュワルツの不等式
双対ノルム
任意のノルムと双対ノルムの間にはヘルダーの不等式を一般化した式が成り立つ
イェンセンの不等式
凸関数の定義
一般に二つのノルムの間にヘルダーの不等式のℓpとℓたの関係が成り立つ時
補題:スパースベクトルのℓ1ノルム
補題:正規分布の裾確率
ノルムの互換性
補題:多次元ガウスベクトルのℓ∞ノルム
ブールの不等式
ユニオンバウンド(union bound)
補題:カイ二乗分布の裾確率
マルコフの不等式
ヘフディンの不等式
ベルンシュタインの不等式
5.4 基本的な性質
補題
ノルムの分解可能性
5.5 制限強凸性
仮定:制限強凸性
強凸性
行列Xが制限強凸性を満足するときに スパースな高次元ベクトルwが低次元ベクトルyから 区別できることの説明
定理
5.6 定理5.1と系5.1の証明
定理
5.7 定理5.2の証明
5.8 数値例
人工に生成したデータでのlasso評価結果
実験2

第6章 L1ノルム正則化のための最適化法

6.1 最適化法の種類
最小化問題
L(w)が凸関数であればℓ1制約つき最小化問題と等価
Λ→0の極限で上式と等価
関数Lに関する仮定に応じた4つのアルゴリズム
繰り返し重みつき縮小法
損失項とリッジ正則化項(λ∥w∥22)の和が効率的に最小化できることを仮定
(加速つき)近接勾配法
損失項L(w)の滑らかさだけを必要とする
双対拡張ラグランジュ法
関数LがL(w)=fℓ(Xw)のように損失関数fℓとデータ行列Xに分解できることを必要とする
双対交互乗数法
双対拡張ラグランジュ法と同様の仮定
関数LとしてL(w)=1/2∥Xw-y∥22のような二乗誤差の場合は、コレスキー分解の事前計算ができて、より効率的になる
6.2 準備
最適化を扱うのに必要となる道具を準備する
ℓ1ノルムの変分表現(variational representation)
Prox作用素(prox operator)
凸共役(convex conjugate)
補題:ℓ1ノルムの変分表現
ℓ1ノルムは、パラメータηを用いて書き直すことができる
定義:prox作用素
凸関数gに関して、prox作用素proxgを定義する
補題6.1のイメージ
補題:ℓ1ノルムに関するprox作用素
ℓ1ノルムに関するprox作用素は ソフト閾値関数(soft-threshold function)と呼ばれる
正則化パラメータλが閾値の役割を果たし
絶対値がλ以下の係数yiはゼロに打ち切られ、それ以上の係数も原点方向にλだけ縮小される
ℓ1ノルムに関するprox作用素(実線)と ℓ2ノルムの2乗に関するprox作用素(破線)との比較
ℓ1ノルムの性質のまとめ
定義:H平滑
定義:凸共役
ロジスティック損失関数と絶対関数の凸協約関数
6.3 繰り返し重み付き縮小法
6.4 近接勾配法およびその加速
6.5 双対拡張ラグランジュ法
6.5.1 式(6.22)の導出
6.6 双対交互方向乗数法
6.7 数値例

第7章 グループL1ノルム正則化に基づく機械学習

はじめに
あらかじめ定義したグループ構造を事前知識として利用して、グループ単位でゼロ/非ゼロを選択するためのノルム
マルチタスク学習、マルチカーネル学習やベクトル場の推定に有効
7.1 定義と具体例
はじめに
d個の変数の適当な分割を𝓞とする
例えばdを偶数として𝓞={{1,2}. {3,4},…{d-1,d}}は2つの変数の組みへの分割
グループℓ1ノルム正則化項は上式となる
Wgは分割の一つの要素gに対応する|g|次元ベクトルを表す
例
g={1,2}とすると
Wgは2次元部分ベクトルwg=(w1,w2)T
ノルム∥・∥pは何でも良いが、p=2やp=∞がよく使われる
p=1ノルムを用いる場合や各グループが一つの変数からなる場合は分割構造は失われ、ℓ1ノルム正則化に帰着する
Lassoのグルプ構造を考慮した拡張
7.1.1 マルチタスク学習
T個の学習課題があり、其々がd’次元のパラメータベクトルw1,…,wT∈ℝd’を推定したいという設定を考える
T個の学習課題に共通して有用な少ない数の特徴量を選びたい
各特徴量に対応した大きさTのグループを定義すると最小化問題は上式で定義できる
共通の台(非ゼロ要素の集合)ヲ持つベクトルw1,…,wTを推定することが可能
グループℓ1ノルム正則化を用いると、 複数の学習課題にまたがって 共通の変数を選択することができることのイメージ
7.1.2 ベクトル場の推定
脳電図(EEG)や脳磁図(MEG)
空間的に隣接した多数のニューロンが同期して活動することで、活動に応じた生まれた電磁波を測定
脳や頭蓋骨を伝わって頭の表面に貼り付けたセンサーを用いて計測することができる
特定のセンサーiで観測される電場や磁場は 脳内の様々な場所の活動の線形の重ね合わせとして 上記のようにモデル化される
jは脳内の空間位置の添字
xjはj番目の位置における活動を表す3次元ベクトル
aijはj番目の空間位置からi番目のセンサーへの電磁波の伝搬を表す係数
脳電図と脳磁図では係数が違うが数学的なモデルは同じ
脳内の特定の位置のニューロン集団の活動の電気双極子によるモデル化
計測可能な電極の数nが一般に脳活動を仮定する小領域(ボクセル)の数Nより小さいので、一種の逆問題となる
適切にタスクを設計することで、対象とする認知活動をある程度限定する
活動源の数はボクセルの数よりずっと少ないというスパース性の仮説が有効
ベクトルの係数を正則化するのではなく、ノルムを正則化することで、空間座標の取り方に依存しない正則化が可能となる
最小化問題
EEG/MEG信号y=(yi)i=1nからベクトルば(xj)j=1Nを推定する
7.1.3 マルチカーネル学習
カーネル法は、カーネル関数k:XxX→ℝの定義する関数空間で線形なモデルを学習する仕組み
どのようなカーネル関数を用いるか、 等価にどのような再生核ヒルベルト空間を考えるかが常に問題となる
マルチカーネル学習
基底カーネル関数km(x,x’):XxX→ℝ(m=1,..,M)が与えられた元で
これらをカーネル重みdmを用いて線形結合したカーネル関数(上式)と それから導かれる予測器を同時に学習する枠組み
カーネル重みの選び方により、
基底カーネルから有用なカーネル関数をえらびだしたり
複数のカーネル関数を組み合わせたりすることができる
カーネル重みに関する正則化項を加えた最小化問題
ℓは損失関数でSVMで用いられるヒンジ損失やロジスティック損失を考えることができる
Hはカーネル重みdmに関する正則化項で、凸関数とする
代表的なグループノルム正則化項gとカーネル重み正則化項hの組
7.2 数学的性質
7.2.1 非ゼログループの数との関係
補題
7.2.2 双対ノルム
補題
7.2.3 変分表現
補題
7.2.4 prox作用素
補題
7.3 最適化
7.3.1 繰り返し重み付き縮小法
変分表現を用いることにより、ℓ1ノルムの場合と同様に繰り返し重みつき縮小かほうを与えることができる
7.3.2 (加速付き)近接勾配法
近接勾配法はproxさ要素を用いて書き表せる
7.3.3 双対拡張ラグランジュ法

第8章 トレースノルム正則化に基づく機械学習

はじめに
低ランク行列は、 協調フィルタリング、 システム同定、 行列を入力とする分類問題等、 非常に多くの応用がある
低ランク制約を直接扱うことは、非凸であり、やや溶きにくい最適化問題となる
ℓ1ノルム正則化の自然な拡張として得られる”トレースノルムの概要と関連アルゴリズム及び実装例について“でも述べているトレースノルムが低ランク性を誘発する
双対ノルムやprox作用素などの多くのℓ1ノルムに関する性質が、行列の特異値に対して拡張される
memo
行列の”フロベニウスノルムの概要とアルゴリズム及び実装例“で述べているフロべニウスノルム
行列の「大きさ」を表す量
全成分の二乗和のルート
∥A∥F
行列の全成分を一列に並べてベクトルとみなしたときのベクトルの長さ(2ノルム)とも考えられる
フロべニウスとトレース
性質1
ATはAの転置行列
フロべニウスノルムと直交変換
性質2
直交業れつを掛けてもノルムは変わらない
フロべニウスノルムと特異点
性質3
フロべニウスノルムの二乗は、特異点の二乗に等しい
トレースノルム正則化項付きロジスティック回帰による行列データの分類
http://yamagensakam.hatenablog.com/entry/2018/06/15/064758
センサーへの応用例
時系列データの分類に使われるその他の手法
HMM
LSTM
8.1 定義と具体例
8.1.1 協調フィルタリング
オンラインショッピングや検索における推薦システムのためのスコアリング手法の一種
ユーザーを行の添字、候補となるアイテムを列の展示として I,j要素がユーザーiによるアイテムjの評価やクリックの数の値をとる行列
行列の未観測要素を予測することでスコアリングを行う
大勢のユーザーのデータを使う
ユーザー数d1,アイテム数d2に対して、 簡単のため-1,+1の2値をとる行列Y∈{-1, +1}d1xd2を考える
例:-1は嫌い、+1は好き
観測されたユーザーとアイテムの組みの集合をΩとすると 経験誤差最小化問題(上式)を考えることができる
ℓは2値分類のための損失関数
ヒンジ関数やロジスティック関数を用いることが可能
行列Wに対して、低ランクである (縦長の行列U∈ℝd1xr, V∈ℝd2xrの積としてかけるという制約を加える
ユーザーとアイテムの関係をr次元空間に埋めこのれたベクトルの関係として捉える
I番目のユーザーに対応するベクトルuiと、 j番目のアイテムに対するベクトルvjの内積が
正であればユーザーiはアイテムjを好み
負であればユーザーiはアイテムjを嫌う
行列Wが低ランクであるという制約を陽に扱うことは 非凸な最適化問題になり少し厄介
ランクを制約する代わりに トレースノルムを正則化(アルイハ等価に制約)する
λ>0は正則化パラメータ
損失関数がヒンジ損失の場合
8.1.2 マルチタスク学習
複数のタスクにまたがって共通の変数を選択する手法
T個のタスクに関するパラメータベクトルを行列方向に並べた行列
各行を1つのグループとするグループℓ1ノルム正則化
複数のタスクの共通性をモデル化する方法は共通の変数を用いるだけではない
T個のタスクが共通の部分空間を用いると仮定する
W=UVTのように行列Wは低ランクになる
U∈ℝd’xrは全タスクに共通の部分空間の基底
V∈ℝTxrはこのr次元空間における それぞれのタスクに特有の係数ベクトル
行列のランクrはタスクの数Tを超えることはない
タスクが類似していればrは小さくなる
グループℓ1ノルムを用いて全タスクに共通の変数を選択すること
低ランク性に基づくマルチタスク学習の定式化
Wに対するランク制約をトレースノルム正則化 (あるいはトレースノルム制約)で置き換える
8.1.3 行列を入力とする分類問題
訓練データ(Xi,yi)i=1nに基づく2値分類問題
Xi∈ℝd1xd2は行列
yi∈{-1, +1}は2値ラベル
Xiをd1,d2次元のベクトルとして扱う場合の問題点
時空間データ(行が空間、列が時間に対応する行列)や 共分散行列間ように行列としての構造に意味がある場合は ベクトル化するとこれらの構造を見失う
行列Xを入力とする線形モデル
係数Wの行列となる
bはバイアス項
入力行列X1,…,Xnは低ランクとは限らない
係数行列Wが低ランクという過程は比較的ゆるい過程
Xの行が空間、列が時間に対する時空間データの場合
“特異値分解(Singular Value Decomposition, SVD)の概要とアルゴリズム及び実装例について“でも述べている特異値分解W=∑j=1rσjujvjTを考えると
特異ベクトルuj,vjは それぞれ空間、時間方向の特徴を抽出するフィルタ
特異値σjは特徴に対する重み
係数行列Wに関するランク制約の代わりに、 トレースノルム正則化を用いる
ℓは損失関数で ヒンジ損失やロジスティック損失を用いることができる
8.2 数学的性質
8.2.1 さまざまな定義
補題:トレースのノルムの等価な表現
半正定値行列
行列Pは半正定 (positive semidefinite)行列
Pの全ての固有値が非負 (対称行列は複素固有値を持たない)
半正定行列の特異点は固有値に一致
トレースノルムはトレースtr(X)に一致する
変数に関する反正定制約、等式制約、 および線形目的関数からなる最適化問題
トレースノルムはスペクトルノルムの双対ノルム
トレースノルムはノルムであり、凸関数
トレースノルムが線形行列不等式として表現できる
損失関数がヒンジ損失のように区分線形であるか、二乗誤差の場合
トレースノルム正則化に基づく学習を半正定値計画問題に帰着できる
トレースノルム最小化と 因子行列U,Vのフロべニウスノルム二乗の最小化が等価
行列U,Vの列の数を十分多く取れば、交互最小化などの比較的簡単な最小化法で済ませることができる
U,Vに関するフロべニウスノルム二乗正則化は U,Vに関して独立な正規分布の事前分布を過程していることと等価
8.2.2 ランクとの関係
補題:ランクがrの行列は トレースノルムとフロべニウスノルムの比が √rで抑えられることを示す
8.2.3 変分表現
補題:トレースノルムに関しても ℓ1ノルムやグループℓ1ノルムと同様に変分表現が可能
行列の平方根
8.2.4 prox作用素
補題
8.3 理論
トレースノルムを用いた行列推定の性能は非常によく兼キュアウサれている
定理
8.4 最適化
8.4.1 繰り返し重み付き縮小法
繰り返し重みつき縮小法を トレースノルム正則化に拡張することが可能
8.4.2 (加速付き)近接勾配法
一般のトレースノルム正則化つき学習問題に対する近接勾配法の反復式
効率的に計算するための工夫1
効率的に計算するための工夫2
8.4.3 双対拡張ラグランジュ法
近接勾配法と同様prox作用素が効率よく計算できる場合は 双対拡張ラグランジュ法を考えることができる
例:行列を入力とする分類問題

第9章 重複型スパース正則化

はじめに
重複のあるスパース正則化
ベクトルw∈ℝdの部分ベクトルや 線形変換したものに関するスパース正則化を組み合わせたもの
画像処理、統計、テンソル分解などに応用される
9.1 定義と具体例
はじめに
正則化項R(m)が m個の正則化項の和として上式で表されるとき、 Rを重複型正則化項と呼ぶ
関数Rjが ベクトルwの要素の重複のない場合はが、 グループℓ1ノルム
9.1.1 エラスティックネット
ベクトルwに対して、 ℓ1ノルムとℓ2ノルムを同時に 罰則項として用いる方法
エラスティックネット(elasticnet)
ℓ1ノルム正則化項と エラスティックネット正則化項の比較
ℓ1ノルムと同様に4つの頂点で尖っている
端点の間では等高線が丸みを持っている
9.1.2 全変動
画像W*∈ℝd1xd2が雑音を含んでY=W*+Eのように観測されたと仮定
この画像から雑音を取り除くため、最小化問題を考える
λ>0は正則化パラメータ
∥・∥TVは等方的全変動 (isotropic total variation)
各画素における勾配ベクトルのノルムの線形和
∇xWx,y, ∇yWx,yは、 xおよびy方向の微分係数
ソーベル演算子(Sobel operator)を用いて
最も簡単な3×3のフィルターを用いた場合でも、 Wの各要素は周囲8つの画素に関する正則化項の中に含まれることになる
等方的全変動は勾配ベクトルのℓ2ノルムの輪として定義されるため グループℓ1ベクトルの推定と同様に、座標の回転に関して不変
ℓ1ノルムで置き換えたもの
等方的全変動を用いた画像の雑音除去の例
その他の応用
圧縮センシング(compressed sensing)のMRI画像への応用
2次元ウェーブレット変換 (wavelet transformation)
9.1.3 重複のあるグループ𝓁1 ノルム正則化
重複のあるグループℓ1ノルム
9.1.4 テンソルの多重線形ランク
重複型トレースノルム
9.2 数学的性質
9.2.1 非ゼログループ数との関係
補題
9.2.2 双対ノルム
補題
重複型グループℓ1ノルムの性質のまとめ
9.3 最適化
はじめに
正則化項が変数wjに関して分離できず、prox作用素を計算するのが困難
9.3.1 エラスティックネットの場合
補題
9.3.2 交互方向乗数法

第10章 アトミックノルム

はじめに
ℓ1ノルムはベクトルの要素単位のスパース性を誘導
グループℓ1ノルムはグループ単位のスパース性を誘導
トレースノルムは行列の低ランク性(スパース性)を誘導
ノルムの単位級は スパースとなる点で尖っているため、 スパース性と結びつく
より汎用的な表現へアトミックノルムの詳細は”アトミックノルムの概要と適用事例と実装例“も参照のこと。
10.1 定義と具体例
10.1.1 重複のあるグループ正則化
10.1.2 ロバスト主成分分析
10.1.3 マルチタスク学習
10.1.4 テンソルの核型ノルム
10.2 数学的性質
10.3 最適化
10.3.1 フランク・ウォルフェ法
10.3.2 双対における交互方向乗数法
10.4 ロバスト主成分分析を用いた前景画像抽出

第11章 おわりに

11.1 何がスパース性を誘導するのか
「非ゼロ要素の数」という最適化しにくい量の代わりにℓ1ノルムが用いられる
ℓ1ノルムは連続で、非ゼロ要素の数が少ない(スパースな)点で微分不可能なため、最適解は一般にスパースになる
ベクトルwの各要素の絶対値|wj|に関して、凹(上に凸)で単調な関数gの和は、スパース正則化項として有効
p≤1ではスパース性を誘発するが、p=2で誘発しない
任意のアトム集合に対して、アトム集合の凸包を単位級とするノルムを定義することができ
そのアトム集合が表すスパース性に関して最もタイトな凸緩和を与える
アトミックノルムは
ℓ1ノルムやトレースノルムのような既に知られているノルムを特殊な場合として含む
スパースでかつ低ランクな行列の集合など、新しい種類のスパース性を誘導するノルムを導出するための系統的な枠組み
原理的にはどのようなアトム集合に対しても、どれくらいのサンプル数があれば、スパースな解が復元できるのか明らかにすることができる
11.2 どのような問題にスパース性は適しているのか
スパース性か有効かどうかを 経験的に考えるチェックリスト
次元dがサンプル数よりもずっと大きい学習/推定問題を考えている
予測性能だけではなく、なぜ予測できるのかを説明できることが重要である
検出した信号の分布の裾が重い
除去したい雑音の分布が裾が軽い
バイオインフォマティクスなどの分野で スパース性が積極的に利用されている理由
仮説候補の数dがサンプル数よりもずっと大きい
究極の目的が予測することではなく、生物というシステムを理解すること
地学の物理探査や画像の雑音除去などで 比較的早い時期からスパース性が用いられてきた理由
検出した信号の裾が重い
元画像と正規雑音画像の勾配のノルムの分布
自然な画像は多くのエッジを含んでいるため、 勾配がゼロに近い値あるいは大きい値の両方に分布
雑音画像の勾配は平均値の回りに集中する
ベクトルの係数の集合を分布とみたときに裾が重いベクトルは 係数の集合が平均値の周りに集中しているベクトルに比べて ℓ1ノルムが小さいという性質が成り立つ
11.3 結局，どの最適化アルゴリズムを使えばよいのか
既存のパッケージを使ってみるのが良い
双対拡張ラグランジュ(DAL)法
SPAMS(sparse modeling software)