ホーム » 「正則化」タグがついた投稿
タグアーカイブ: 正則化
Lassoの最適化アルゴリズムの考察
こんにちは。
前回の最後に、
– Coordinate descent(座標降下法)
– ISTA (メジャライザー最小化)
– FISTA (高速化)
の3つの最適化方法を紹介しました。今回は上の2つを解説します。そして次回実装へうつりましょう。
まずは簡単なLassoからです。
Coordinate descent
いきなり解説に入る前に何ですが、座標降下法ってメチャクチャシンプルなんですよ。
けど全く有名じゃないんですよね。(多分、理由は記事の最後)まあ、アルゴリズムみましょう
目的関数の最適化を考えます。
ここではconvexかつdifferentiabl、
はconvexとします。
(例えばconvexかつundifferentiablなを考えた場合、反例があります。詳しくはREADMORE)
回目の更新を右肩の添え字で表すと、各変数に対して
のように更新するアルゴリズムです。
Pointは1つ、変数を1つずつ更新するんです。その他の変数は定数とみるんです。なので
この図の感じですね。しかし次の問題を考えてみましょうに対して
です。例えば初期値をで座標降下法をアプライしてみると
のどちらから更新しても
で停滞することがわかります。しかし
これは明らかに最適解はですよね。こういったことからスパースな問題にはあまり良くないようです。
次にメジャライザーの方を行きましょう。
Iterative Shrinkage Thresholding
ちなみにこのアルゴリズムは初めて聞きました。EMアルゴリズムでも似たことが行われますね。
こちらもアルゴリズムは単純で
というものです。
一次元の場合、を
周りでのテイラー展開
多次元の場合、
下の図がイメージになります。上界というのは「より大きいやつ」という意味です。
この図からアルゴリズムがどうやって動いて何で最適化できるのかは直感的にわかったかと思います。
しかし、このメジャライザーが本当に存在するのか?など疑問に思う人がいるでしょう。
では考察しましょう。
まず初期値をとします。そして目的関数を
,メジャライザーを
とします。
そして、メジャライザーは次のような性質を満たしてほしいです。
–
– に対して
すると性質から明らかにの最小化が
の最小化に繋がることがわかります。
では実際にそんな都合のいいを探しましょう。の前にちょっと寄り道します。
どんな形のメジャライザーが都合いい?
メジャライザーを探すといえどこのままでは全くわかりません。
にすればいいのか?いや、それもわかりません。なので
いきなりですが次の最適解を考えましょう。次元は1です。(
)
前回の記事でやったようにこれは場合分けで簡単にできますね
に対して
同様にしてに対して
では最後にの範囲で場合分けすると前回のSoft thresholding functionが出てきましたね。
詳しく復習すると
の時
の時
の時
これが大切です。
ではLassoの目的を再掲しましょう。
今の例と似てますよね。
ここで
これがほしいメジャライザーを予測するということです。
では元に戻って都合のいいを探しましょう。平方完成できるやるがいいんでしたね。
テイラーの2次近似の形を想像しながら
という形で考えましょう、(は計算の都合上のもの)そうすれば
とできますね。よって
は
となります。
そうなんです。先ほどメジャライザーを考えたときにを使いましたね。
このを決める必要があります。メジャライザーの性質(2)から
が「0以上」を任意のについて言える必要があるので

の必要があります。つまり、の最大の固有値が
として取りうる最小の値になります。
そこで固有値の大きさを見積れる定理があるのでそれを使いましょう。
– Gershgorin circle theorem
– Gershgorin’s Theorem for Estimating Eigenvalues
この定理からmaxをとることで
と固有値の大きさが見積もれます。
長かったですがとりあえずLassoはおしまいです。
でわ。
READMORE
Lassoの進化、Group Lassoとは
こんにちは。
Lassoでスパース、スパースと言ってましたが実際はスパース推定という言葉がよく使われます。これについての説明を軽くしてからGroup lassoの紹介をします。
スパース推定とは
スパースは”疎”を意味します。スパース推定とはどのパラメータが0になるかを推定すること。つまり、データの本質がわかります。直感的には次の図から
もう少し実用的な例は?
右の入力から左の出力を考えるLassoモデルを考えると
のようにアレルゲン反応のスパース推定ができます。
つまり、スパース推定により関与しないパラメータがわかります。
Group Lassoとは
グループラッソとは
先ほどのアレルゲンを例にとると例えば、ヒノキなどの個体単位ではなく「花粉」というグループ単位でスパース性が検証できるモデルのことです。Lassoはの正規化項は次のものでした。
Group Lassoの正規化項は次で定義されます
ここではg番目のグループを表すindex。(ただし、
、
はグループgの大きさ)
前述通りGroup Lassoでは特徴をグループ化します。よって、事前に類似の傾向がありそうな特徴の情報を考慮します。
なるほど、と思った方と、ん?、と思った方がいると思います。
これは図を用いてチェックしましょう。
Group Lassoの解
- 参考文献の論文に従い、解説します。
まず個の変数からなるもっとも一般的な回帰問題を考えます
Yはベクトル、
、
は
番目のデータに対応した
行列で
はサイズ
の係数からなるベクトルとする。さらに各
は直交行列であると仮定する。
すなはちとする。さらに、
、
とすると上式は
かける。
長ったらしく書きましたが要は「グループの大きさが各のサイズ」です。なので
を考えるとこれはLassoそのものとなります。
と
の正定値対称行列
に対して次を定める。
ただし、とする。正定値行列
が与えられた時、Group Lasso回帰では次の解を考える。ただし
Bakin(1999)はこれをグループ変数によるLassoの拡張版として提案しました。
ここも特に気にする必要はなく、大切なのは正定値対称行列により変数に「重み」が掛かっているところです。機械学習ではこのように変数に重みを加える動作をよくします。一例として
– マハラノビス距離(Mahalanobis distance)
があります。僕たちが無意識に距離として使っているものはユークリッドノルムで、つまり単位行列の時です。
では先ほどの
をみましょう。
下の図はグループが2つ(各係数はベクトルとスカラー)、つまりの場合を考え、
が単位行列の場合の正規化項を表しています(ラッソはダイヤ、リッジは円だったやつの三次元バージョン)
つまり、
- Figure(a)は
- Figure(e)は
- Figure(i)は
もっと噛み砕くと
- Figure(a)は Lassoの
-norm
- Figure(e)は GroupLassoのnorm
- Figure(i)は Ridgeの
-norm
です。Figure(e)において平面を見ると
というグループ単位でゼロに潰れることがわかります。
だからGroup Lassoはグループ単位ででスパース性を与えているんです。
でわ。
READMORE
Lassoを数式から実装まで(理論編)
こんにちは。
その1でラッソの概要と大きな特徴であるスパース性を確認しました。
今回からはラッソ実装に向けて数学を頑張りましょう。
Notationのについて
- Obj (objective function)
- OLS (Ordinary least squares) (回帰の残差平方和)
: データ数
: 次元(特徴)
:
番目の特徴
:
番目の観測データ
のうち
に対応するもの
目的関数について
今回、つまりラッソの目的関数は以下の通り
(OLS)の勾配について
上の目的関数は微分できません。なのでひとまず置いておいて
OLSをいつも通り微分して微分を計算します。
後々のため、今回は勾配でなく、での微分を計算します。
簡単のためこれを次のように表します。
L1-normの微分について
-normは微分できないとわかりました。なので
微分できるように、微分という概念を拡張します。そこで出てくるのが
です。wikiのリンク
定義(劣微分)
Convex の点
における劣微分は次の条件を満たす
で定義する。
(簡単のためについてはなし、微分の代わりに勾配という言葉を使っている)
書き換えると
における劣勾配は次の閉区間の集合である。
これが勾配の拡張になっていることは微分可能な点においてその劣勾配が一点集合になることからわかる
実はこれは簡単で、場合分けして綺麗に微分できるところの間を1つの微分の集合と見るのです。
今回のノルム、つまり
を例にとると、
(1)
(2)
そしてこの間の集合を0での微分とするのが劣勾配
(3)
次のはイメージ図
ではこの劣勾配を使って今回の目的関数の第2項を微分してゼロとおきます。
(4)
(5)
ここで先ほどと同様に場合分けを行って
(6)
(7)
そして、
(8)
ですね。文字が多くなってしまったので再確認ですが、目標はを求めることです。上の2つの式は簡単に求まりますが、3つ目の式については閉区間に0が含まれるという条件で考えましょう。なので
(9)
(10)
(11)
なので
(12)
まとめると
(13)
(14)
(15)
となります。ちなみにこの場合分けからSoft thresholding functionという関数が定義されます。
最後に劣微分と一緒にplotを見てみましょう。
微分できなくてよく使う関数をたまたま思い出しました。ニューラルネットワークで使うRELU fucntionですね。
– 活性化関数ReLUとその類似関数
他にも色々あるようです。
色々計算づくしでしたが微分を計算できました。あとは最適化のみですが今までは勾配法を使っていましたが「微分不可能な場合は勾配法は無理」なので他の最適化法が必要です。そこでLassoの問題ではいくつかのメジャーな方法があります。
- Coordinate descent(座標降下法)
- ISTA (メジャライザー最小化)
- FISTA (高速化)
です。もっとも簡単なのは座標降下法です。メジャライザーはテイラー展開を用いて上界を扱うものですがこれらについては次回解説します。
でわ。
READMORE
Lassoはなんでスパース?
こんにちは。
素人にfish_shellは無理でした。kzです。
リッジが終わりましたね。ついに来ました
ラッソ
最近色々ラッソについて調べていたんですが、微分不可能な関数の最適化ってやっぱ難しいですね。機械学習において非常に重要な2つのキーワード
– ラグランジュの未定乗数法
– KKT条件
は別の記事でゆっくり解説します。では本題に入りましょう。
Lasso
過学習を考慮した回帰モデルの一つ
– L_1正則化項を使用した回帰model
– スパース性を考えるときに用いる(これについては次の記事で詳しく説明します。)
(1)
リッジ回帰との唯一の違いは正規化項がL1(絶対値)であるということ。
微分できない?
ちょっと微分について復習しよう。おまけで複素解析も出てくるよ
L1とL2
これまでに何度か説明していると思いますがまずは
– 微分可能性
が大きな違いです。L1は尖っているので0で微分できませんね。
他の違いは?
リッジ回帰ではデカイパラメータがでかくなりすぎないよう上限を設けましたね。
ラッソも上限はありますが、ゼロがKEYWORDです。なぜなら
– 無関係な特徴量はゼロで排除する
という特徴があります。ゆえに、モデルで初めに設定したものよりも少ない特徴量で済む可能性があります。これが先ほどのスパース性と言われる所以です。
パラメータが0を図から考察
では図を用いて直感的に理解しましょう。次の図はRidge, Lassoを議論するときに使われるとてもポピュラーなものです。
「スパース」とは「スカスカ」なイメージ
つまり、ゼロがいっぱいあるイメージでいい。
しかし重要なのは常にスパースなわけじゃないこと。
スパースと言われるのはこの「尖ったポイント」に最適解がある時。
これはL1だからできますよね。L2は円だったのでスパース性はありません。
パラメータが0を数式から考察
次のように超シンプルな回帰モデルを考えます。(以下転置使ってますが無くてもいいです)
(2)
次の最小化を考えます。
(3)
(この2は計算の都合上のもの)
ここで解がと仮定します。
すると、より
と仮定するのと同値であることがわかります。さて、目的関数を
に関して微分しましょう
仮定より今は微分できます
(4)
であり、これをゼロと置くことでこの解は次のものだとわかります
(5)
ここでを増やしていくと
でゼロになることがわかりますね。
この瞬間にLassoはスパース性を持ちます。
一方、リッジの場合は
(6)
(7)
となるので、よりパラメータはゼロにはならないですね。
でわ
Ridgeを数式から実装まで(理論)
こんにちは。
料理にはまっているkzです。
本日はリッジ回帰行きましょう。次回実装します。🐷
Ridge Regression
過学習を防ごうということで導入された正則化回帰の一例。
– 正則化項を使用した回帰model
– パラメータに上限あり
たまにリッジ回帰はペナルティーありの線形回帰という記事を見かけますがそうではなく多項式回帰でもあります。つまりモデルが
(1)
だけでなく
(2)
もOKということ。
Notation
- Number of data:
- Dimension:
- Parameters:
つまり各データは
(3)
と表されます。も同様。
Constrained minimizationは
(4)
(5)
となりますが扱いずらいのでベクトル表示に変更し同時にKKT条件より最適化問題を同値なものに書き換えます。
(6)
ではまず解を求めましょう。いつも通り微分をゼロとおいて解くだけ。今回のコスト関数は次の通り
(7)
としてで微分する。
– 「ベクトルで微分・行列で微分」公式まとめ
(8)
したがって
は正則をキープするためのものでしたね。
ここまでは前回の内容をちょっとだけ丁寧にやっただけのおさらいのようなものです。ここからが数学チック。
さて、この解が最適解かどうかを関数の凸性から確認してみましょう。凸性は前回やりましたがお椀型なら極小値が最小値になることでしたね。
– 第2章 凸関数
– Convex functions
(9)
に対して次は同値である。
– が凸である
– に対してヘッセ行列
がpositive-semi-define
では
(10)
となりますね。ここでこれがpositive-semi-defineであることは次からわかります。に対して
(11)
とノルムの定義よりわかりました。

今見たのは
(12)
の凸性ですよね。そして
(13)
こちらは明らかに凸。ではが本当に凸かどうか。これは直感的には明らかですが証明が簡単なのでやってみましょう。
集合を定義域とする関数
がともに凸関数であると仮定する。
このときに対して
が凸であることを示す。
(14)
(15)
(16)
Q.E.D.
Lassoは結構めんどくさいんですよね。。
でわ
線形回帰とRidge回帰を数式からやる(理論編)
こんにちは。
正則化パート2ですね。前回の最後に
- Ridge Regression (Tikhonov regularization)
- Lasso Regression
を例に出しました。今回はこれらを用いて正則化について学びましょう。の前に線形回帰を思い出しましょう。その時に
を考えて
の列ベクトルが張る空間への射影行列をやりましたね。ここで
が正則ということなのでもう一歩踏み込みQR分解を行います。つまり
を使うと
とできます。わかったことは
の列ベクトルが張る空間への射影行列
が
となるということ。超シンプル。これが線形回帰。で、これに
正則化項を加えます。つまり
に対して
を考えます。これをリッジ回帰というのでしたね。ラッソは正則化項を使います。
違いは?
正則化項のノルムです。と
の違いは?もう少し親しみある言い方だと距離と絶対値の違いは?
Answer: 微分可能性
は微分できませんね。前回の図を思い出してください。
は尖っていました。
勾配法は微分を使いましたね。なので一旦ラッソは無視してリッジについて学びましょう。
次の解を考えます。ただし
「アーグミン」は右辺を最小化するときの
ということ。これを展開し、微分すると
これが欲しかったですね。さっきの
と似てませんか?邪魔なのは
の項。なのでここで
とするとさっきのと同じになります。だって元々のコスト関数の正則化項が0になるわけですからね。
、これ意味ある?
ここでは半正定値対称行列であり、実数値からなる対称行列は実数の固有値を持ちます。よって
の固有値は0以上。行列式を計算して見よう。
これをについて解くと
の固有値が求まりますね。そこでその固有値の一つを
とするとリッジ回帰における固有値は
となり、
分シフトされていますね。つまり、行列式をゼロから遠ざけており正則をキープしてくれています。
逆にとすると
となってしまいますね。これもまずい。
をどうやって決めるか
これが問題ですね。これは交差検証で選ばれます。交差検証ってなんやあ??
K-fold cross validation
ですかね。これはデータ個をK等分割(5か10が一般)してモデルの汎化性能を評価するためにあります。しかしここではパラメータ
のベストチョイスのために使います。これはとても重要な概念なので次の記事で深く確認しましょう。今回は簡単な図を最後に見てお別れです。
でわ
READMORE
過学習を防ぐトリック、正則化とは
こんにちは。
少し前に標準化・正規化についてお話ししました。これらは勾配法による学習の際に学習速度が速くなるというメリットがありました。では今回は
正則化とはなんぞや
名前が似てますね、ということは
勾配法に関係あり?学習速度に関係あり?
いい読みです。次の図を見てください。
どっちの曲線が「いい学習」をした結果だと思いますか? もう一問
どちらが「いい分類」をしていますか?
「いい分類・いい学習」とは何か?
を考える必要があります。データには誤差がつきものです。なので「誤差を許容するという寛大な心が必要」なんです。つまり、
モデルは柔軟性を持つべき
という考えから「正則化」とう考えに突入します。
具体的には?
そもそもなんで過学習してしまうのか、ですよね。
あるモデルが過学習するということはパラメータが手持ちのデータを重視しすぎるということ
言い換えると
過学習とはモデルが未知のデータを考慮しなくなるということです。
このままではいけません。未知のデータを考慮させる必要があり、そのための作戦が「正則化」です。具体的には
パラメータの学習に制限を設けること
です。例えば、パラメータを学習させたいとします。そこでモデルを
、ラベルを
とでもし
を最小化することでを学習させる問題を考えます。このままやると
は好き放題学習しますが
で
とかのように制限設けるとはこの範囲で学習しますよね。しかしこれは考える問題が
から
のように制約付きの最適化問題になりました。ヤバイ、しかも
制約が不等式!!!
これはやばいです。しかし!
KKT条件という物を使えば解決します。(ちなみにSVMとかでも出てきますがかなり難しいです)(ちなみに制約が等式の時はラグランジュの未定乗数法)つまりで
とできます。ただしはLpノルムです。
Lpノルムって何?
とします、つまり
はn次元実ベクトルとします。この時
に対して
と定義します。これをのLpノルムと言います。関数解析でやるので覚えといて〜。初めての人は直感がわかないと思うので図で見てみましょう。
一般的に使うのはです。少し話が逸れましたが
これですね。コスト関数を最小化する際にが大きくならないようにペナルティーの形で加えます。なので第二項は罰金項、正規化項などと呼ばれます。これを使った実際の例は次の2つがあります。
- Ridge Regression (Tikhonov regularization)
- Lasso Regression
です。リッジ回帰は正規化項を使います。なので
となります。一方でラッソ回帰は正規化項を使います。なので
です。これらについて詳しくは別の記事で書きます。今はとりあえず「正則化」の例として覚えておいてください。
さて、正則化はパラメータの学習に制限を設けることと言いました。で、各ノルムに対する正規化項の特徴についてです。がこれも長くなるので次の記事で会いましょう。
でわ。
READMORE