【解説】人工ニューロンとは

# 概要

個人的に学習しているDeep Learningの備忘録として,
基礎の基礎である人工ニューロンについての記事を作成しました.

人工ニューロンはパーセプトロンとほぼ同義です.
以降, 研究開発における一般的な呼称に合わせ, パーセプトロンと表記します.

本記事では, 以下の流れでパーセプトロンの概要を段階的に解説していきます.

1. `パーセプトロンとはそもそも何なのか`
2. `パーセプトロンの構造と処理内容`
3. `論理回路としてのパーセプトロン`
4. `迷惑メールかどうかを件名から予測するパーセプトロンモデル`

最後の節では, 実際に簡易的なデータを用意し, それをモデルに学習させていきます.
最終的には, 迷惑メールかどうかを80%強の精度で判定できるモデルを構築します.

内容が誤っている可能性も多分にありますので, ご指摘等ありましたらコメントをお願いいたします.

:::note warn
本記事はある程度Pythonや数学的な知識がある方向けの記事です.
:::

# 目次

- [動作環境](#動作環境)
- [パーセプトロンとは](#パーセプトロンとは)
- [パーセプトロンの仕組み](#パーセプトロンの仕組み)
  - [1. 入力信号の線形和](#1-入力信号の線形和)
  - [2. バイアス項の加算](#2-バイアス項の加算)
  - [3. 活性化関数](#3-活性化関数)
  - [4. まとめ](#4-まとめ)
- [パーセプトロンの実装](#パーセプトロンの実装)
- [パーセプトロンの予測モデル](#パーセプトロンの予測モデル)
  - [1. データの準備](#1-データの準備)
  - [2. データの前処理](#2-データの前処理)
  - [3. モデルの実装](#3-モデルの実装)
  - [4. モデルの訓練と評価](#4-モデルの訓練と評価)
- [補足](#補足)
- [参考](#参考)

# 動作環境

本記事のプログラムは以下の環境で動作確認をしています.

|  |  |
| --- | --- |
| OS | macOS Sonoma14.4.1 |
| Python | 3.9.6 |

# パーセプトロンとは

パーセプトロンとは, ニューラルネットワークを構成する最小単位のアルゴリズムを指します.
別名を人工ニューロンといい, 脳の処理の基本単位である神経細胞を模したモデルの一つです.

パーセプトロンのアルゴリズムは複数の信号を受け取り, 閾値によって0または1のどちらかを出力します.

詳しくは後述しますが, 問題が線形分離可能であれば, 有限回の反復処理によって必ず解答を出力できることが知られています（単純パーセプトロンの収束定理）.

裏を返せば, 線形分離不可能な問題に対しては対象外であり, 二値分類等の簡単な問題のみに使用されます.

次節で実際の仕組みを見ていきます.

# パーセプトロンの仕組み

パーセプトロンの概念図は以下です.

![perceptron.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3762056/7d31eb16-fd50-39b2-f6f9-fc7b3178ed1b.png)

| `変数` | `説明` |
| :---: | :--- |
| $x_i$ | $i$番目の入力信号の値 |
| $w_i$ | $i$番目の入力信号固有の重み |
| $b$ | バイアス |
| $y$ | 出力信号 |
| $\varphi$ | 活性化関数<br>※入力信号の線形和を, 求める出力の形に変形するための関数 |

現在利用されているニューラルネットワークモデルの多くは, この図のようなパーセプトロンが複雑に絡み合い,層をなすことで構成されています.

以下では, パーセプトロンがどのような処理を行っているのかを段階的に見ていきます.

## 1. 入力信号の線形和

まず, 各入力信号$x$それぞれの重要度に応じた重み付けを行います.

※ ここでいう重みとは, どの信号が重要なのかを表す値であり, 各信号が固有の値を保持しています.

```math
\begin{align}
  & x_1w_1 + x_2w_2 + \dots + x_mw_m \\
  & = \sum_{i=1}^m x_iw_i \tag{1}
\end{align}
```

:::note info
この処理によって, 優先順位の高い信号を増幅, そうではない信号を減衰させることができます.
:::

## 2. バイアス項の加算

式$(1)$に対し, パーセプトロンの発火しやすさの値であるバイアス項を加算します.

$$\sum_{i=1}^m x_iw_i + b \tag{2}$$

後述しますが, この値が大きいほど1を出力しやすく, 小さいほど0を出力しやすくなります.

:::note info
先に言ってしまうと, パーセプトロンなどの情報処理モデルにおける" 学習 "とは, 先程の重み$w$とバイアス$b$を最適な値に微調整していくことを指します.
:::

## 3. 活性化関数

最後に, 式$(2)$を活性化関数に通します.

活性化関数には様々な種類があり, パーセプトロンでは主にステップ関数が用いられます.

### ステップ関数

ステップ関数とは, 入力信号の線形和とバイアスの和が閾値を超えた場合は1, そうでなければ0を出力する関数です.

具体的には, 以下のように表されます.

```math
\begin{align}
  \begin{cases}
    1 & \text{if } \Big(0 \leq \sum_{i=1}^m x_iw_i + b \Big) \\
    0 & \text{if } \Big(\sum_{i=1}^m x_i w_i + b < 0 \Big)
  \end{cases} \tag{3}
\end{align}
```

<details><summary>バイアス項の解釈について</summary>

余談ですが, $(3)$の条件式を変形すると, 以下の式が得られます.

```math
\begin{align}
  \begin{cases}
    -b \leq \sum_{i=1}^m x_iw_i \\
    \sum_{i=1}^m x_iw_i < -b
  \end{cases}
\end{align}
```

ここで, $-b_k$を$\theta$と置くと,

```math
\begin{align}
  \begin{cases}
    \theta \leq \sum_{i=1}^m x_iw_i \\
    \sum_{i=1}^m x_iw_i < \theta
  \end{cases}
\end{align}
```

のように表すことができます.

したがって, バイアス項$\theta(= -b)$は閾値と解釈できます.

この値を微調整することにより, あるニューロンの発火のしやすさを制御できることがわかります.
</details>

Pythonのmatplotlibを用いて, バイアス項が$b = -5$の場合ステップ関数を描画してみると, 次のようになります.

![step_function.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3762056/5e94e000-69e2-ee97-3ee4-e639ad54c5f6.png)

<details open><summary>ソースコード</summary>

```python:step_function
import matplotlib.pyplot as plt
import numpy as np

# データの準備
x = np.linspace(0, 10, 100)
y = np.heaviside(x - 5, 1)

# プロットの作成
plt.figure(figsize=(10, 6))
plt.step(x, y, where='mid', label='Heaviside Step Function', color='b', linewidth=2)

# 軸ラベルとタイトル
plt.xlabel('x-axis', fontsize=14)
plt.ylabel('y-axis', fontsize=14)
plt.title('Step Function Plot', fontsize=16)

# グリッドの追加
plt.grid(True)

# 凡例の追加
plt.legend()

# 注釈の追加
plt.annotate('Step occurs at x=5', xy=(5, 0.5), xytext=(6, 0.7),
             arrowprops=dict(facecolor='black', shrink=0.05))

# プロットの表示
plt.show()

```
</details>

## 4. まとめ

ここまでの手順をまとめると,
出力$y$は, $m$個の入力信号$x$, それぞれの重み$w$, バイアス$b$, 活性化関数$\varphi$を用いて以下のように表されます.

$$y = \varphi\Big(\sum_{i=1}^m x_iw_i + b \Big) \tag{4}$$

# パーセプトロンの実装

では, 例として基本情報技術者試験等にも出題される, 論理回路の実装を行っていきます.

こちらの実装では, 事前に用意した重みとバイアスを用いて, ある単一のパーセプトロンにおける処理を考えます.

## 論理回路の実装

AND回路とは, 2つの入力信号が共に1である場合のみ, 1を出力する論理回路です.

表で表すと, 以下のようになります.

| 入力信号1 | 入力信号2 | 出力信号 |
| :---: | :---: | :---: |
| $0$ | $0$ | $0$ |
| $1$ | $0$ | $0$ |
| $0$ | $1$ | $0$ |
| $1$ | $1$ | $1$ |

Pythonを用いてAND回路を実装していきます.

:::note warn
ここでは, `and_gate`メソッドが0か1の出力を行うため, ステップ関数による変換は必要ありません.
:::

```python:and_gate
import numpy as np

def and_gate(x: np.ndarray) -> int:
  """
  2つの入力信号が共に1である場合のみ1, それ以外は0を出力する関数
  
  Args:
    x (np.ndarray): 入力信号

  Returns:
    (int): 出力信号
  """
  weight = np.array([1.0, 1.0])
  bias = -1.5
  y = np.sum(x * weight) + bias

  return 1 if y > 0 else 0
```

それでは, 実際に入力信号を与えて出力させてみましょう.

入力信号のパターンとしては上述の表の通り, $2^2$通りのテストケースを用意します.

それらをAND回路に処理させ, コンソールに出力します.

```python
if __name__ == "__main__":
    test_cases = [
        np.array([0, 0]),
        np.array([1, 0]),
        np.array([0, 1]),
        np.array([1, 1])
    ]

    for x in test_cases:
        y = and_gate(x)
        print(f"Input: {x}, Output: {y}")
```

これでANDゲートの実装は完了です.

出力すると, 以下のような結果が得られると思います.

```python
Input: [0 0], Output: 0
Input: [1 0], Output: 0
Input: [0 1], Output: 0
Input: [1 1], Output: 1
```

また, NAND回路やOR回路を実装するには, $w$と$b$の値を変更するだけです.
以下に例を示します.

- NAND回路:
  AND回路の出力を反転させた回路
  
  | 入力信号1 | 入力信号2 | 出力信号 |
  | :---: | :---: | :---: |
  | $0$ | $0$ | $1$ |
  | $1$ | $0$ | $1$ |
  | $0$ | $1$ | $1$ |
  | $1$ | $1$ | $0$ |
  
  ```python:nand_gate
  weight = np.array([-1.0, -1.0])
  bias = 0.7
  ```
  <br>

- OR回路:
  入力信号のどちらかが1であれば1, どちらも0であれば0を出力する回路
  
  | 入力信号1 | 入力信号2 | 出力信号 |
  | :---: | :---: | :---: |
  | $0$ | $0$ | $0$ |
  | $1$ | $0$ | $1$ |
  | $0$ | $1$ | $1$ |
  | $1$ | $1$ | $1$ |
  
  ```python:or_gate
  weight = np.array([1.0, 1.0])
  bias = -0.5
  ```
  <br>

- XOR回路
  | 入力信号1 | 入力信号2 | 出力信号 |
  | :---: | :---: | :---: |
  | $0$ | $0$ | $0$ |
  | $1$ | $0$ | $1$ |
  | $0$ | $1$ | $1$ |
  | $1$ | $1$ | $0$ |
  
同様にして, XOR回路の実装を試してみてください.
どのように値を変更しても, 実装できないことが分かると思います.

それは, XOR回路の問題が線形分離不可能であることに起因します.

単一のパーセプトロンが, 入力空間を直線で分断する機能しか持たないためです.

視覚的に理解しやすいよう, 入力信号をプロットしてみます.

![xor_gate.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3762056/9790c970-6f9b-5040-72b9-1f4f7e4245c9.png)

0の点群と1の点群を正確に二分する直線は存在しないことが分かると思います.

<details open><summary>ソースコード</summary>

```python:xor_gate
import matplotlib.pyplot as plt

# 入力と出力を定義
inputs = [(0, 0), (0, 1), (1, 0), (1, 1)]
outputs = [0, 1, 1, 0]

# プロットの作成
plt.figure(figsize=(6, 6))

# 出力が0のポイントをプロット
output_0_plotted = False
output_1_plotted = False

for (x, y), output in zip(inputs, outputs):
    if output == 0:
        if not output_0_plotted:
            plt.scatter(x, y, color='red', s=100, label='Output 0')
            output_0_plotted = True
        else:
            plt.scatter(x, y, color='red', s=100)
    elif output == 1:
        if not output_1_plotted:
            plt.scatter(x, y, color='blue', s=100, label='Output 1')
            output_1_plotted = True
        else:
            plt.scatter(x, y, color='blue', s=100)

# 軸ラベルとタイトル
plt.xlabel('Input A', fontsize=14)
plt.ylabel('Input B', fontsize=14)
plt.title('XOR Gate Output', fontsize=16)

# グリッドの追加
plt.grid(True)

# 凡例の追加
plt.legend()

# プロットの表示
plt.show()

```
</details>

ここまでで簡単な動作原理は理解できたかと思います.

次節では, より実用的なシステムへと議論を発展させていきます.

# パーセプトロンの予測モデル

ここでは, これまで学習したパーセプトロンの基礎を用いて, 「メールの件名から迷惑メールかどうかを予測するモデル」を作成していきたいと思います.

以下の手順で実装を行なっていきます.

1. データの準備
2. データの前処理
3. モデルの実装
4. モデルの訓練と評価

:::note warn
以降, 変数名については一般的な命名規則ではなく, パーセプトロン実装時の慣習に従います.
:::

## 1. データの準備

データの準備を行う前に, 必要なパッケージをインストールします.

```python: perceptron.py
import numpy as np
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
```

:::note info
sklearnは, データ分析や機械学習のためのライブラリの一つです.
詳しくは, 下記公式サイトをご覧ください.
:::

https://scikit-learn.org/stable/

学習や評価に必要なサンプルデータを, GPTに出力してもらいました.

データの構造としては, リスト>タプルになっています.
また,それぞれのデータは件名とラベル（0: 通常のメール, 1: 迷惑メール）を保持しています.
長いので折りたたんでおきます.

<details><summary>サンプルデータ</summary>

```python:perceptron.py
data = [
    ("Free money", 1),
    ("Earn cash now", 1),
    ("Hello friend", 0),
    ("Meeting tomorrow", 0),
    ("Congratulations, you've won!", 1),
    ("Important update", 0),
    ("Limited time offer", 1),
    ("Urgent: Your account has been compromised", 1),
    ("Discount on all products", 1),
    ("Can we catch up?", 0),
    ("Invoice for your recent purchase", 0),
    ("You've been selected for a prize!", 1),
    ("Project deadline extended", 0),
    ("Exclusive deal just for you", 1),
    ("Family reunion details", 0),
    ("Last chance to save big", 1),
    ("Team meeting agenda", 0),
    ("New job opportunity", 1),
    ("Summer sale ends soon", 1),
    ("Weekly newsletter", 0),
    ("Security alert", 0),
    ("Special promotion inside", 1),
    ("Your order has been shipped", 0),
    ("Limited seats available", 1),
    ("Please review the attached document", 0),
    ("Win a free vacation", 1),
    ("System maintenance notification", 0),
    ("Final notice: Payment due", 1),
    ("Invitation to connect", 0),
    ("Act now to claim your reward", 1),
    ("Your friend has sent you a gift", 1),
    ("Upcoming event reminder", 0),
    ("Important: Update your information", 0),
    ("Congratulations, you are a winner!", 1),
    ("Project kickoff meeting", 0),
    ("Claim your exclusive bonus now", 1),
    ("Friendly reminder", 0),
    ("Top secret investment opportunity", 1),
    ("Your subscription is expiring soon", 0),
    ("Update: Your recent activity", 0),
    ("Limited time discount on all items", 1),
    ("Invitation to join our network", 0),
    ("Urgent: Immediate action required", 1),
    ("Job interview confirmation", 0),
    ("Breaking news: Major update", 0),
    ("Win big with our latest contest", 1),
    ("Your feedback is important to us", 0),
    ("New feature announcement", 0),
    ("You've been pre-approved", 1),
    ("Notification: Payment received", 0),
    ("Exciting new product launch", 0),
    ("Unlock your potential with us", 1),
    ("Your invoice is ready", 0),
    ("Special deal just for you", 1),
    ("Upcoming maintenance scheduled", 0)
]
```

</details>

## 2. データの前処理

続いて, 用意したデータをモデルに適した形へ加工していきます.

```python:percepton.py
# データの分割
subjects, labels = zip(*data)
labels = np.array(labels)

# テキストデータの数値変換
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(subjects).toarray()

# トレーニング・テストセットの作成
X_train, X_test, y_train, y_test = train_test_split(X, labels, test_size=0.3, random_state=42)
```

### 2.1 データの分割

```python
subjects, labels = zip(*data)
```

`*data`: データセットをアンパックし, 個々のタプルに分解

`zip()`: 個々のタプルの最初の要素（件名）, 2番目の要素（ラベル）をそれぞれ変数に格納

```python
labels = np.array(labels)
```

`np.array(labels)`: ラベルをNumPy配列に変換

### 2.2 テキストデータの数値変換

```python
vectorizer = CountVectorizer()
```

`CountVectorizer`: テキストデータをベクトル表現に変換するツール

```python
X = vectorizer.fit_transform(subjects).toarray()
```

`fit`: 件名全体から語彙を構築

`transform`: 各件名を語彙に基づくベクトルへ変換

`toarray`: 結果の疎行列を配列に変換

### 2.3 トレーニングセット, テストセットの作成

```python
X_train, X_test, y_train, y_test = train_test_split(X, labels, test_size=0.3, random_state=42)
```

| 変数 | 説明 |
| :---: | :--- |
|`X_train` | トレーニングセットの特徴量データ |
|`X_test` | テストセットの特徴量データ |
|`y_train` | トレーニングセットのラベルデータ |
|`y_test` | テストセットのラベルデータ |

:::note info
特徴量: ここでは, メールの件名をベクトル化したもの
:::

`split`: データを分割
`test_size=0.3`: データの30%をテストセット, 70%をトレーニングセットに分割する指定
`random_state=42`: ランダムな分割を再現可能にするためのシード値

以上でデータの前処理は完了です.

## 3. モデルの実装

続いて, モデルを実装していきます.

```python:perceptron.py
# モデルの実装
class Perceptron:
    """
    パーセプトロンの実装クラス

    Attributes:
        W (np.ndarray): 重みベクトル（バイアス項を含む）
        lr (float): 学習率
        epochs (int): エポック数（トレーニング反復回数）
    """
    def __init__(self, input_size: int, lr: float = 0.1, epochs: int = 1000) -> None:
        """
        パーセプトロンの初期化

        Args:
            input_size (int): 入力次元数（特徴量の数）
            lr (float, optional): 学習率. デフォルト=0.1
            epochs (int, optional): エポック数. デフォルト=1000
        """
        # バイアス項を含む重みの初期化
        self.W = np.zeros(input_size + 1)
        self.lr = lr
        self.epochs = epochs

    def step_function(self, x: float) -> int:
        """
        ステップ関数

        Args:
            x (float): 入力値

        Returns:
            int: ステップ関数の出力（0または1）
        """
        return 1 if x >= 0 else 0

    def predict(self, x: np.ndarray) -> int:
        """
        入力データに対する予測

        Args:
            x (np.ndarray): 入力データ（特徴ベクトル）

        Returns:
            int: 予測ラベル（0または1）
        """
        # バイアス項を追加
        z = self.W.T.dot(np.insert(x, 0, 1))
        
        return self.activation_fn(z)

    def fit(self, X: np.ndarray, d: np.ndarray) -> None:
        """
        モデルのトレーニング

        Args:
            X (np.ndarray): トレーニングデータの特徴行列
            d (np.ndarray): トレーニングデータのラベルベクトル
        """
        for _ in range(self.epochs):
            for i in range(d.shape[0]):
                x = np.insert(X[i], 0, 1)
                y = self.step_function(self.W.T.dot(x))
                e = d[i] - y
                self.W = self.W + self.lr * e * x
```

### 3.1 `__init__`メソッド

```python
def __init__(self, input_size: int, lr: float = 0.1, epochs: int = 1000) -> None:
    self.W = np.zeros(input_size + 1)
    self.lr = lr
    self.epochs = epochs
```

`W`: 入力信号それぞれの重み+バイアスを0で初期化

`lr`: 学習率（Learning Rate）. 重みがどのくらいの大きさで更新されるかを決定する値

`epochs`: モデルをトレーニングする回数

:::note alert
学習率は小さすぎると「学習の遅延」, 大きすぎると「最適解に収束しない可能性」が発生します.
同様にエポック数も小さすぎると「学習が不十分」, 大きすぎると「過学習」等の事象が発生します.
ここでは, 上述した値を使いましょう.
:::

### 3.2 `step_function`メソッド

```python
def step_function(self, x: float) -> int:
    return 1 if x >= 0 else 0
```

[先述](#3-活性化関数)した通りのため, 解説は省略します.

### 3.3 `predict`メソッド

```python
def predict(self, x: np.ndarray) -> int:
    z = self.W.T.dot(np.insert(x, 0, 1))
        
    return self.activation_fn(z)
```

`np.insert`: 第1引数に指定した配列の, 第2引数の位置に第3引数の値を挿入（バイアス項を考慮するため）

`self.W.T`: パーセプトロンの重みベクトルの転置

`dot()`: 内積を計算

$\therefore$ `z`: 入力データに対する線形結合の出力（特徴ベクトルと重みベクトルの加重和）

### 3.4 `fit`メソッド

```python
def fit(self, X: np.ndarray, d: np.ndarray) -> None:
    for _ in range(self.epochs):
        for i in range(d.shape[0]):
            x = np.insert(X[i], 0, 1)
            y = self.step_function(self.W.T.dot(x))
            e = d[i] - y
            self.W = self.W + self.lr * e * x
```

`fit`: epochs回分, 全てのトレーニングデータに対して反復処理を行う

`x`: 現在のサンプルX[i]の先頭に, バイアス項として1を追加

`y`: バイアス項を含む重みベクトルとバイアス項を追加した特徴ベクトルの内積を計算, 活性化して予測を得る

`e`: 予測ラベルと実際のラベルとの誤差

`self.W`: 重みの更新

ここまでで, モデルの実装は完了です.

## 4. モデルの訓練と評価

最後に, 構築したモデルの訓練と評価を行います.

```python:perceptron.py
if __name__ == "__main__":
    # モデルの訓練

    # 特徴量の数を取得
    input_size = X_train.shape[1]
    # パーセプトロンモデルのインスタンス化
    perceptron = Perceptron(input_size)
    # モデルの訓練
    perceptron.fit(X_train, y_train)

    # モデルの評価
    
    # テストデータの特徴行列の各行に対する予測ラベルの配列を得る
    y_pred = np.array([perceptron.predict(x) for x in X_test])
    # 予測ラベルと実際のラベルから精度を計算
    accuracy = accuracy_score(y_test, y_pred)

    print(f"Accuracy: {accuracy * 100:.2f}%")
```

ここまでのコードを実行すると, 以下のような結果が得られます.

```
Accuracy: 82.35%
```

これは学習済パーセプトロンの予測がどのくらい正確だったかを示す値です.
教師データが少ないためかなり精度は悪いですが, パーセプトロンのアルゴリズムについては理解していただけたと思います.

今後, 精度をさらに改善していくための理論や実装についても纏めていく予定です.

興味のある方は是非ご一読いただければと思います.

以上でパーセプトロンの予測モデルの構築は完了です.

# 補足

<details><summary>単純パーセプトロンの収束定理</summary>

パーセプトロンには線形分離不可能な問題が解けないと述べてきましたが, 

一方で, 単純パーセプトロンは線形分離可能な問題であれば必ず解を算出できることが知られています.

以下に数学的な証明を載せておきます.
ご興味のある方はご一読いただけますと幸いです.

## 命題

```txt
任意の有限で線形分離可能なラベル付き集合に対し,
パーセプトロンの学習アルゴリズムは有限回の処理を繰り返すことで必ず解を導出できる.
```

## パラメータ

データセットを二分可能な重みベクトルを$w^*$, データセットを$S$とする.

$$\forall \mu, x_\mu, y_\mu, {}^tw^* > 0$$

$$S = \big\lbrace(x_\mu, y_\mu), \mu \in \lbrace 1 ...P \rbrace\big\rbrace$$

$w_n$, $w^*$間の角度$\theta$を用いて,

```math
\cos\big(\theta(n)\big) = \frac{{}^t w_n \cdot w^*}{||w_n|| \cdot ||w^*||}
```

点$x_\mu$の平面$w^*$に対するユークリッド距離$\delta_\mu$は,

```math
\delta_\mu = \frac{y_\mu \cdot {}^t w^* \cdot x_\mu}{||w^*||}
```

$x$とベクトル$w^*$超平面との間の最小距離は,

$$\delta^* = \min_\mu \delta_\mu$$

## 証明

パラメータの更新回数$n$を用いて, ベクトル空間における重みベクトル$w$は,

```math
\begin{align}
  ||w^n||^2 &= ||w_{n - 1} + y_n x_n||^2 \\
  &= ||w_{n - 1}||^2 + ||x_n||^2 + 2 y_n {}^t w_{n - 1} x_n
\end{align}
```

ここで, 原点を中心とする$x_\mu$を全て含む円の半径を$R$と定義すると,

$$R^2 = \max_\mu ||x_\mu||^2$$

さらに, $n$は更新回数であるため,

$$y_n {}^t w_{n - 1} x_n < 0$$

したがって,

$$||w_n||^2 \leq ||w_{n - 1}||^2 + R^2$$

これらを$n$回繰り返すため,

$$||w_n||^2 \leq nR^2 \tag{1}$$

$n$は更新回数であるため,

```math
\begin{align}
  {}^t (w^n) \dot w^* &= {}^t (w_{n - 1} + y_{n - 1} x_{n - 1}) w^* \\
  &= w_{n - 1} w^* + y_{n - 1} {}^t w^* x_{n - 1}
\end{align}
```

また, $\delta$の定義から,

```math
\begin{align}
  \delta_{n - 1} ||w^*|| &\geq \delta^* ||w^*|| = y_{n - 1} {}^t w^* x_{n - 1} \\
  \therefore {}^t w_n w^* &\geq {}^t w_{n - 1} w^* + \delta^* ||w^*||
\end{align}
```

同様に$n$回繰り返し,

$${}^t w_n \geq n \delta^* ||w^*|| \tag{2}$$

$(1)$, $(2)$から,

```math
    1 \geq \cos\big(\theta(n)\big) =
    \frac{{}^t w_n \cdot w^*}{||w_n|| \cdot ||w^*||} \geq
    \frac{n \delta^* ||w^*||}{\sqrt{n} R ||w^*||} =
    \frac{\sqrt{n} \delta^*}{R}
```

したがって,

$$n \leq \frac{R^2}{{\delta^*}^2}$$

ここに, $n$が有限であることが証明された.

</details>

# 参考

https://www.oreilly.co.jp/books/9784873117584/

https://gen-ai-media.guga.or.jp/glossary/simple-perceptron/

https://starpentagon.net/analytics/simple_perceptron/