Gradient descentで学習した線形回帰アルゴリズムの実装

gradient descentを使って学習を行ったモデルを元に、走行距離に応じた自動車の価格を線形回帰で予測するシンプルなプログラムを作成してみたので、記事にしてみました。

## Estimate price
推論時は走行距離を受け取り、その走行距離に応じた推定価格を返します。次の式を使用して価格を予測します。

```math
estimatePrice(mileage) = \theta_0 + (\theta_1 \times mileage) \tag{1}
```

推論コードは[こちら](https://github.com/Hiroaki-K4/ft_linear_regression/blob/main/estimate_price.py)です。以下のコマンドで試すことができます。この例では、100000kmの車の価格を推定します。

```bash
python estimate_price.py --mileage 100000 --param_yaml param.yaml
```

## Train with a gradient descent algorithm
学習コードはデータセットのファイルを読み込み、データに対して線形回帰を実行します。線形回帰が完了すると、推論コードで使用する変数θ0とθ1が保存されます。学習手順は以下の通りです。

### 1. Normalize range
データの値をそのまま学習に使うと、うまく収束しませんでした。そこで、データを正規化してから学習に使用しました。正規化には[scaling to a range](https://developers.google.com/machine-learning/data-prep/transform/normalization#scaling-to-a-range)を使用しました。

$$
x=(x\prime - x_{min})/(x_{max}-x_{min}) \tag{2}
$$

**scaling to a range**は、次の両方の条件を満たす場合に良い正規化方法です。
- 外れ値がほとんどない。データのおおよその上限と下限がわかっている。
- データがその範囲にほぼ一様に分布している。

### 2. Calculate gradient
勾配を計算していきます。最小化するコスト関数は以下の通りです。mはデータ数です。

```math
\frac{1}{m}\sum_{i=0}^{m-1}(price[i]-estimatePrice(mileage[i]))^2
\tag{3}
```

θ0とθ1のそれぞれで微分した式は以下のようになります。

```math
\begin{align*}
D_{\theta_0}&=\frac{\partial (costFunction)}{\partial_{\theta_0}}=\frac{\partial}{\partial_{\theta_0}}\left(\frac{1}{m}\sum_{i=0}^{m-1}(y_i-(\theta_1x_i+\theta_0))^2\right) \\
&=\frac{1}{m}\frac{\partial}{\partial_{\theta_0}}\left(\sum_{i=0}^{m-1}(y_i^2+\theta_1^2x_i^2+\theta^2+2\theta_1x_i\theta_0-2y_i\theta_1x_i-2y_i\theta_0)\right) \\
&=\frac{-2}{m}\sum_{i=0}^{m-1}(price[i]-estimatePrice(mileage[i]))
\end{align*} \tag{4}
```

```math
\begin{align*}
D_{\theta_1}&=\frac{\partial (costFunction)}{\partial_{\theta_1}}=\frac{\partial}{\partial_{\theta_1}}\left(\frac{1}{m}\sum_{i=0}^{m-1}(y_i-(\theta_1x_i+\theta_0))^2\right) \\
&=\frac{1}{m}\frac{\partial}{\partial_{\theta_1}}\left(\sum_{i=0}^{m-1}(y_i^2+\theta_1^2x_i^2+\theta^2+2\theta_1x_i\theta_0-2y_i\theta_1x_i-2y_i\theta_0)\right) \\
&=\frac{-2}{m}\sum_{i=0}^{m-1}x_i(price[i]-estimatePrice(mileage[i]))
\end{align*} \tag{5}
```

### 3. Update parameter with learning rate
θ0とθ1の値は、学習率Lに応じて更新されます。

```math
\theta_0=\theta_0-LD_{\theta_0},
\theta_1=\theta_1-LD_{\theta_1} \tag{6}
```

### 4. Calculate cost function
コスト関数の式(3)が非常に小さくなるまで(理想的には0)、このプロセスを繰り返します。

### 5. Convert normalized value back to original value
得られたθ0とθ1は正規化されたデータの値なので、元のスケールに戻します。

```math
x_{original}=x_{norm}(x_{max}-x_{min})+x_{min} \tag{7}
```

学習コードは[こちら](https://github.com/Hiroaki-K4/ft_linear_regression/blob/main/train.py)です。実行時のコマンドは以下の通りです。

```bash
python train.py --csv_file_path data.csv --output_param_path param.yaml
```

結果のグラフは以下の通りです。いい感じですね。

![result_graph.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/663246/da71e775-7693-bafd-44b3-0d46a77f5405.png)

## References
- [Gradient descent](https://en.wikipedia.org/wiki/Gradient_descent)
- [Linear function](https://en.wikipedia.org/wiki/Linear_function)
- [Gradient Descent in Linear Regression](https://www.analyticsvidhya.com/blog/2021/04/gradient-descent-in-linear-regression/)
- [Linear Regression using Gradient Descent](https://towardsdatascience.com/linear-regression-using-gradient-descent-97a6c8700931)
- [Normalization](https://developers.google.com/machine-learning/data-prep/transform/normalization)