ウェルフォード法と一次元線形回帰

1次元線形回帰は、最も単純な回帰法の1つ（および一般的に最も単純な機械学習法の1つ）であり、属性の1つに対する観測値の線形依存性を記述することができます。 一般的な場合、機械学習の問題では、多数の異なる属性に対処する必要があります。 この場合の1次元線形回帰は、目的関数との最良の相関を達成できるようにするものの1つを選択します。

このシリーズの以前の投稿で、平均と共分散の計算の精度について説明し、多くの場合これらの問題の計算エラーを回避するウェルフォード法にも精通しました。 今日は、一次元線形回帰の問題におけるウェルフォード法の実際的な応用を見ていきます。

内容

• 1.一次元線形回帰
• 2.中央揃えのサンプルのソリューション
• 3.一般的な場合の決定
• 4.ウェルフォード法の適用
• 5.実験方法の比較
• おわりに
• 文学

1.一次元線形回帰

1次元線形回帰問題では、実数の2つのシーケンスがあると仮定します。 $$$x$ そして答え $$$y$ 。 さらに、対応する重みのベクトルがあります $$$w$ 。 いつものように、これらのシーケンスには潜在的に無限の数の要素が含まれると仮定しますが、現時点では $$$n$ 各シーケンスの最初の要素。

私たちのタスクは、特徴と答えの間の線形関係を復元すること、つまり線形決定関数を構築することです。 $$$f：\ mathbb {R} \右矢印\ mathbb {R}$ ：

$$

$$f（x_i）= \ alpha \ cdot x_i + \ beta$$

これにより、平均二乗損失関数が最小化されます。

$$

$$Q（f、x、y、w）= \ sqrt {\ frac {1} {\ sum_ {i = 1} ^ {n} w_i} \ sum_ {i = 1} ^ {n} w_i \ cdot（f （x_i）-y_i）^ 2}$$

分析のために、根本的で正規化されていない式を使用する方が簡単です。

$$

$$Q_1（f、x、y、w）= \ sum_ {i = 1} ^ {n} w_i \ cdot（f（x_i）-y_i）^ 2 = \ sum_ {i = 1} ^ {n} w_i \ cdot（\ alpha x_i + \ beta-y_i）^ 2$$

機能の最小点から $$$Q$ そして $$$Q_1$ 一致する場合、そのような置換は正しいです。

2.中央揃えのサンプルのソリューション

損失機能 $$$Q_1$ に関してデリバティブを書きやすい $$$\ alpha$ そして $$$\ベータ$ ：

$$

$$\ frac {\ partial Q_1（f、x、y、w）} {\ partial \ alpha} = 2 \ cdot \ sum_ {i = 1} ^ {n} w_i x_i（\ alpha x_i + \ beta-y_i）$$

$$

$$\ frac {\ partial Q_1（f、x、y、w）} {\ partial \ beta} = 2 \ cdot \ sum_ {i = 1} ^ {n} w_i（\ alpha x_i + \ beta-y_i）$$

それらをゼロに等しくすると、次のようになります。

$$

$$\ alpha \ cdot \ sum_ {i = 1} ^ {n} w_i x ^ 2_i + \ beta \ cdot \ sum_ {i = 1} ^ {n} w_i x_i-\ sum_ {i = 1} ^ {n} w_i x_i y_i = 0$$

$$

$$\ alpha = \ frac {\ sum_ {i = 1} ^ {n} w_i x_i y_i-\ beta \ cdot \ sum_ {i = 1} ^ {n} w_i x_i} {\ sum_ {i = 1} ^ { n} w_i x ^ 2_i}$$

$$

$$\ beta = \ sum_ {i = 1} ^ {n} w_i y_i-\ alpha \ cdot \ sum_ {i = 1} ^ {n} w_i x_i$$

重要な余談。 この場合、導関数をゼロに等しくすることは正しいです。なぜなら、

1.損失汎関数は、最適化されたパラメーターに関して凸であるため、 ローカル最適の任意のポイントもグローバル最適のポイントになります 。

2.最適化されたパラメータに関する汎関数損失は放物線であるため、見つかった極値は最小値になります。

最適なパラメータの場合 $$$\ベータ$ ゼロに等しい場合、解決策を見つけることは難しくありません。 サンプルを前処理する標準的な機械学習方法であるセンタリングが、この効果に正確につながることに気付くかもしれません。 実際、中心変数の問題を考えてみましょう。

$$

$$x'_i = x_i-\ frac {\ sum_ {i = 1} ^ n w_i x_i} {\ sum_ {i = 1} ^ n w_i}$$

$$

$$y'_i = y_i-\ frac {\ sum_ {i = 1} ^ n w_i y_i} {\ sum_ {i = 1} ^ n w_i}$$

重み付き属性の合計はゼロになり、重み付き応答の合計もゼロになりました。

$$

$$\ sum_ {k = 1} ^ {n} w_k x_k '= \ sum_ {k = 1} ^ {n} w_k \ cdot \ Big（x_k-\ frac {\ sum_ {i = 1} ^ n w_i x_i} {\ sum_ {i = 1} ^ n w_i} \ Big）= \ sum_ {k = 1} ^ {n} w_k x_k-\ sum_ {i = 1} ^ n w_i x_i = 0$$

$$

$$\ sum_ {k = 1} ^ {n} w_k y_k '= \ sum_ {k = 1} ^ {n} w_k \ cdot \ Big（y_k-\ frac {\ sum_ {i = 1} ^ n w_i y_i} {\ sum_ {i = 1} ^ n w_i} \ Big）= \ sum_ {k = 1} ^ {n} w_k y_k-\ sum_ {i = 1} ^ n w_i y_i = 0$$

その場合、自由パラメーターの最適値はゼロになります。

$$

$$\ beta '= \ sum_ {i = 1} ^ {n} w_i y_i'-\ alpha '\ cdot \ sum_ {i = 1} ^ {n} w_i x'_i = 0$$

そしてこれは、パラメータの最適値が $$$\ alpha '$ 見つけやすい：

$$

$$\ alpha '= \ frac {\ sum_ {i = 1} ^ {n} w_i x'_i y'_i} {\ sum_ {i = 1} ^ {n} w_i x' ^ 2_i}$$

3.一般的な場合の決定

次に、一般的なオフセンターデータのケースに戻りましょう。 もし $$$f '$ 中央のケースの決定的な関数であり、その値は式によって決定されます

$$

$$f '（x'_k）= \ alpha' \ cdot x'_k$$

値を概算する $$$y'_k = y_k-\ frac {\ sum_ {i = 1} ^ n y_i x_i} {\ sum_ {i = 1} ^ n w_i}$ 次に、次の決定的な関数が量を近似します $$$y_k$ ：

$$

$$f（x_k）= \ alpha '\ cdot \ Big（x_k-\ frac {\ sum_ {i = 1} ^ n w_i x_i} {\ sum_ {i = 1} ^ n w_i} \ Big）+ \ frac { \ sum_ {i = 1} ^ n y_i x_i} {\ sum_ {i = 1} ^ n w_i} = \ alpha '\ cdot x_k + \ Big（\ frac {\ sum_ {i = 1} ^ n y_i x_i} {\ sum_ {i = 1} ^ n w_i}-\ alpha '\ cdot \ frac {\ sum_ {i = 1} ^ n w_i x_i} {\ sum_ {i = 1} ^ n w_i} \ Big）$$

したがって、1次元線形回帰の初期問題の解は次のように記述できます。

$$

$$\ alpha = \ frac {\ sum_ {i = 1} ^ {n} w_i（x_i-m_n ^ {wx}）（y_i-m_n ^ {wy}）} {\ sum_ {i = 1} ^ {n} w_i（x_i-m_n ^ {wx}）（x_i-m_n ^ {wx}）}$$

$$

$$\ beta = m_n ^ {wy}-\ alpha \ cdot m_n ^ {wx}$$

ここでは、前回の記事で紹介した加重平均の表記法を使用します。

$$

$$m_n ^ {wx} = \ frac {\ sum_ {i = 1} ^ n w_i x_i} {\ sum_ {i = 1} ^ n w_i}$$

$$

$$m_n ^ {wy} = \ frac {\ sum_ {i = 1} ^ n w_i y_i} {\ sum_ {i = 1} ^ n w_i}$$

別の方法で、このような移行が正しいことを理解できます。 中心データのソリューションが最適な場合、パラメーター $$$\ alpha '$ そして $$$\ベータ '$ 最小損失機能を提供する $$$Q_1$ ：

$$

$$Q_1（f '、x'、y '、w）= \ sum_ {i = 1} ^ {n} w_i \ cdot（\ alpha' \ cdot x'_i + \ beta '-y'_i）^ 2$$

次に、変数を置き換えて、中心から外れたデータに戻ります。

$$

$$Q_1（f '、x'、y '、w）= \ sum_ {i = 1} ^ {n} w_i \ cdot \ Big（\ alpha' \ cdot（x_i-m_n ^ {wx}）-y_i + m_n ^ {wy} \ Big）^ 2 =$$

$$

$$= \ sum_ {i = 1} ^ {n} w_i \ cdot \ Big（\ alpha '\ cdot x_i +（m_n ^ {wy}-\ alpha' \ cdot m_n ^ {wx}）-y_i \ Big）^ 2$$

結果の式は、損失関数の値を記述します $$$Q_1$ の式に従った偏りのないデータの場合 $$$\ alpha$ そして $$$\ベータ$ 私たちは上に得た。 この場合の機能の値は最小に達するため、問題は正しく解決されます！

4.ウェルフォード法の適用

ここで、パラメータを計算するときに注意してください $$$\ alpha$ 前の記事で扱った計算と同じ共分散が使用されます 。 実際、その表記法を使用して、次のように書くことができます。

$$

$$\ alpha = \ frac {D_ {n} ^ {wxy}} {D_ {n} ^ {wxx}} = \ frac {C_ {n} ^ {wxy}} {C_ {n} ^ {wxx}}$$

つまり、回帰係数を計算するには、Wellfordメソッドを使用して共分散を2回計算する必要があります。 これらの計算の過程で、自由回帰係数の計算に必要な平均値を同時に見つけます。

別の要素を選択に追加するためのコードは 、サインと回答の平均と分散、およびサインと回答間の共分散を更新することで構成されます。

void TWelfordSLRSolver::Add(const double feature, const double goal, const double weight) { SumWeights += weight; if (!SumWeights) { return; } const double weightedFeatureDiff = weight * (feature - FeaturesMean); const double weightedGoalDiff = weight * (goal - GoalsMean); FeaturesMean += weightedFeatureDiff / SumWeights; FeaturesDeviation += weightedFeatureDiff * (feature - FeaturesMean); GoalsMean += weightedGoalDiff / SumWeights; GoalsDeviation += weightedGoalDiff * (goal - GoalsMean); Covariation += weightedFeatureDiff * (goal - GoalsMean); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、すべての要素を追加した後、1次元線形回帰の最適なパラメーターを見つける問題を解決する方法です。

 template <typename TFloatType> void TWelfordSLRSolver::Solve(TFloatType& factor, TFloatType& intercept, const double regularizationParameter = 0.1) const { if (!FeaturesDeviation) { factor = 0.; intercept = GoalsMean; return; } factor = Covariation / (FeaturesDeviation + regularizationParameter); intercept = GoalsMean - factor * FeaturesMean; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

GoalsDeviation



の値はここでは使用されませんが、今後の記事で必要になります。

1つのクラスですべての計算を組み合わせることで、オーバーヘッドを回避できます。 たとえば、2つのオブジェクトがセカンダリを格納するための実装で使用され、3つのオブジェクトが共分散を格納するために使用された場合（符号付きの回答、回答付きの回答、回答付きのサイン）、サンプルの各例で重みの合計が5回更新されます。

5.実験方法の比較

実際の比較のために、1 次元および多次元の線形回帰の問題を解決するためのさまざまな方法を実装するプログラムを作成しました。 次の記事で多次元回帰について説明しますが、ここでは1次元のケースに焦点を当てます。

いつものように、「ナイーブ」な方法、カハン法による合計に基づく方法、およびウェルフォード法に基づく方法を比較します。

「単純な」方法は、共分散を計算するための公式を直接適用します 。

 void Add(const double feature, const double goal, const double weight = 1.) { SumFeatures += feature * weight; SumSquaredFeatures += feature * feature * weight; SumGoals += goal * weight; SumSquaredGoals += goal * goal * weight; SumProducts += goal * feature * weight; SumWeights += weight; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クラスはテンプレートであり、タイプdoubleおよびタイプTKahanAccumulatorのカウンターを持つ特殊化があります。

さらに、 TTypedBestSLRSolver



クラスが TTypedBestSLRSolver



れ、1次元回帰モデルを構築するための最良の機能を選択します。 これは非常に簡単に行われます。1次元の線形回帰の問題は、各記号について解決され、結果のモデルの中で最良のものが選択されます。

開発したメソッドをテストするために、LIACコレクションのモデルデータを使用します。 便宜上、データセットの一部は、作成されたプログラムが理解できる形式でデータディレクトリに配置されます。

タスクのデータは単純な方法で「台無しにされます」。サインと回答の値に特定の数値を掛け、その後に他の数値を追加します。 したがって、計算ケースの観点から問題を取得できます：散布値と比較して大きな平均値。

research-bslr



サンプルは連続して数回変化し、そのたびにスライド制御手順が開始されます。 チェックの結果は、テストサンプルの決定係数の平均値です。

たとえば、kin8nmサンプルの場合、結果は次のとおりです。

 injure factor: 1 injure offset: 1 fast_bslr time: 0.001322 R^2: 0.27359 kahan_bslr time: 0.002999 R^2: 0.27359 welford_bslr time: 0.00432 R^2: 0.27359 normalized_welford_bslr time: 0.004288 R^2: 0.27359 injure factor: 0.1 injure offset: 10 fast_bslr time: 0.001256 R^2: 0.27359 kahan_bslr time: 0.002948 R^2: 0.27359 welford_bslr time: 0.004303 R^2: 0.27359 normalized_welford_bslr time: 0.004275 R^2: 0.27359 injure factor: 0.01 injure offset: 100 fast_bslr time: 0.001283 R^2: 0.27359 kahan_bslr time: 0.003015 R^2: 0.27359 welford_bslr time: 0.004304 R^2: 0.27359 normalized_welford_bslr time: 0.004285 R^2: 0.27359 injure factor: 0.001 injure offset: 1000 fast_bslr time: 0.001262 R^2: 0.27324 kahan_bslr time: 0.002977 R^2: 0.27359 welford_bslr time: 0.004329 R^2: 0.27359 normalized_welford_bslr time: 0.00428 R^2: 0.27359 injure factor: 0.0001 injure offset: 10000 fast_bslr time: 0.00128 R^2: -59.271 kahan_bslr time: 0.003009 R^2: -0.0005269 welford_bslr time: 0.004304 R^2: 0.27359 normalized_welford_bslr time: 0.00428 R^2: 0.27359 full learning time: fast_bslr 0.006403s kahan_bslr 0.014948s welford_bslr 0.02156s normalized_welford_bslr 0.021408s
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、サンプル内のすべての値を1万倍に減らし、それらに10,000の値を追加すると、Kahanメソッドで合計しても標準アルゴリズムが動作しなくなります。 生産の実生活で見られるものを含む他のサンプルでも同様の結果が得られます。

おわりに

そこで、本日、1次元線形回帰の問題について話し、この問題の分析解を得る方法と、ウェルフォード法を使用して解を見つける方法を見つけました。

Wellfordの方法は、データの潜在的な問題に対する問題の解決を大幅に強化します。 ただし、この方法は標準アルゴリズムの2〜4倍遅いので、実際には、データで起こりうる問題に依存したり、できるだけ早く作業したりするのではなく、現時点でより重要なものを自分で決める必要があります。

異なるデータでモデルを何度も作成する必要があり、受信した各モデルの品質を制御する方法がない場合は、Wellfordメソッドを使用することをお勧めします。

次の記事では、Wellfordメソッドを使用して多次元線形回帰問題を解決する方法について説明します。

文学

1. habrahabr.ru： ウェルフォード法による平均と共分散の正確な計算
2. github.com： さまざまな計算方法を使用した線形回帰問題ソルバー
3. github.com：コネクショニスト人工知能研究所（LIAC）のARFFデータセットのコレクション
4. machinelearning.ru： 一次元線形回帰