[解決済み] ロジスティック回帰のpythonソルバーの定義

質問

sklearnのロジスティック回帰関数を使っているのですが、最適化問題を解くために、それぞれのソルバーが裏で実際に何をしているのか気になります。

どなたか、"newton-cg", "sag", "lbfgs" と "liblinear" が何をしているのかを簡単に説明していただけませんか。

どのように解決するのですか?

さて、パーティに遅刻していなければいいのですが......。まずは、たくさんの情報を掘り下げる前に、直感を確立することを試みてみましょう ( 注意 これは簡単な比較ではありません。 TL;DR)

はじめに

仮説 h(x) は 入力 を受け取り 推定出力値 .

この仮説は1変数の連立方程式のような単純なものから、使っているアルゴリズムの種類によっては非常に複雑で長い多変数方程式まであります( 例：線形回帰、ロジスティック回帰...etc. ).

私たちのタスクは 最適なパラメータ (シータやウェイトなど)を使って 最小の誤差 を計算し、出力を予測する。この誤差を計算する関数を コストまたは損失関数 であり、どうやら私たちの目標は を最小化することです。 を最小化し、最良の予測出力を得ることができます。

もう一つ思い出してほしいのは、パラメータ値とコスト関数への影響（つまり誤差）の関係は、次のようになります。 ベル曲線 (すなわち 二次曲線 重要なので思い出してください）．

そこで、その曲線の任意の点から始めて、止まった各点の微分（つまり接線）を取り続けると、( で停止し、そうでなければ、複数の特徴がある場合、偏導関数をとります。 と呼ばれるものに行き着きます。 大域的最適化 に行き着く。

コストの最小点（つまり大域的最適点）で偏微分をとると、次のようになる。 スロープ 接線の 0 (となる（そうすれば目標に到達したことがわかる）。

がある場合のみ有効です。 凸型 がある場合のみ有効ですが、そうでない場合は、いわゆる 局所最適化 この非凸関数を考えてみよう。

これで、私たちがやっていることと用語のヘコミの関係を直感的に理解できたはずです。 派生的 , タンジェントライン , コスト関数 , 仮説 ...など。

余談：上記の直感は、Gradient Descent Algorithm（後述）にも関連します。

背景

線形近似。

関数が与えられると f(x) での正接を求めることができます。 x=a . 接線の方程式は L(x) は L(x)=f(a)+f′(a)(x−a) .

次の関数のグラフとその接線を見てみましょう。

このグラフから x=a の付近では、接線と関数は ほぼ のグラフになります。場合によっては、接線を使うこともある。 L(x) を関数の近似値として使うこともある。 f(x) の近くで x=a . このような場合、接線を " と呼びます。 線形近似 での関数への "。 x=a .

二次近似。

線形近似と同じですが、今回は曲線を扱うので はできません。 に近い点を見つけることができます。 0 のみを用いて 接線 .

代わりに 放物線 を使うことにする。

良い放物線を描くためには、放物線と二次関数の両方が、同じ 値 であること、同じ 一次導関数 であり、同じ 二次導関数 . この式は( 興味本位で ): Qa(x) = f(a) + f'(a)(x-a) + f''(a)(x-a)2/2

これで、詳細な比較を行う準備が整ったはずです。

メソッド間の比較

1. ニュートン法

での勾配降下ステップの動機付けを思い出してください。 x で、2次関数（つまりコスト関数）を最小化します。

ニュートン法ではある意味で より良い 二次関数の最小化。 2次近似を使うのでより良い（つまり、最初の AND 第二 偏導関数)を使うからです。

これは、ヘシアンを使ったねじれた勾配降下法と想像できます ( の2階偏導関数からなる正方行列です。 n X n ).

さらに、ニュートン法の幾何学的解釈は、各反復において、近似的に f(x) の周りの二次関数で xn で、その二次関数の最大/最小に向かって一歩ずつ進む（高次元では、これは 鞍点 ). なお、もし f(x) が2次関数である場合、厳密な極限は1つのステップで見つかります。

欠点。

1. それは、計算機的に 高い は、ヘシアン行列（つまり2次偏微分の計算）のためです。

2. に引き寄せられる。 サドルポイント これは多変数最適化で一般的な点です（つまり、この入力を最大点にするか最小点にするかで偏導関数が不一致になる点です！）。

2. Limited-memory Broyden-Fletcher-Goldfarb-Shanno Algorithm（限定メモリBroyden-Fletcher-Goldfarb-Shannoアルゴリズム）。

一言で言えば、ニュートン法のアナログであるが、ここではヘシアン行列は で近似されます。 は、勾配評価（または近似勾配評価）で指定された更新を使用します。言い換えれば、逆ヘッシアン行列への推定を使用します。

Limited-memoryという用語は、単に近似を暗黙的に表すいくつかのベクトルだけを保存することを意味します。

あえて言うなら、データセットが 小さい L-BFGSは他の手法と比較して相対的に最も性能が良く、特に多くのメモリを節約できるが、いくつかの" 深刻な 「

L-BFGS は他の手法と比較して、特に多くのメモリを節約することができます。

余談：このソルバーはバージョン 0.22 以降、LIBLINEAR に代わって sklearn LogisticRegression のデフォルトソルバーとなりました。