📂머신러닝

퍼셉트론 수렴 정리

$X^{+}$, $X^{-}$가 선형 분리 가능한 트레이닝 셋이라고 하자. $y$를 다음과 같은 레이블이라고 하자.

$$y_{i} = \pm 1\ (\mathbf{x}_{i} \in X^{\pm})$$

전체 트레이닝 셋 $X = X^{+} \cup X^{-}$에 $N$개의 데이터가 있다고 할 때 다음과 같은 순서로 입력값을 대입한다고 하자.

$$\mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N), \mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N),\mathbf{x}(1), \mathbf{x}(2), \cdots$$

즉 마지막 데이터까지 학습 과정이 끝나면 처음으로 돌아가 다시 시작하는 것이다.

정리¹

예측에 실패한 입력값이 나올 때 마다 다음과 같이 둔다고 하자.

$$\mathbf{x}_{1}, \mathbf{x}_{2}, \cdots, \mathbf{x}_{n}, \cdots$$

가중치의 초기값을 $\mathbf{w}_{1}=\mathbf{0}$이라고 하자. $n$번째 예측 실패한 입력 데이터에 대해서 다음과 같이 가중치를 업데이트 한다고 하자.

$$\mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n}$$

그러면 다음의 식을 만족하는 $n_{o}$가 존재한다.

$$\mathbf{w}_{n_{o}} = \mathbf{w}_{n_{o} + 1} = \mathbf{w}_{n_{o} + 2} = \cdots$$

$$\begin{cases} \mathbf{w}_{n_{o}}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{n_{o}}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases}$$

설명

위 정리를 한 마디로 요약하면 ‘퍼셉트론은 유한번에 학습을 완료한다’ 이다. $n_{o}$ 이후에는 가중치가 업데이트 되지 않는 다는 말이고, 이는 모든 $\mathbf{x}$에 대해서 $y = \hat{y}$라는 말이다.

가중치를 업데이트 하는 방식이 그저 틀린 데이터를 더해주기만 하면 된다는 점과 유한번의 횟수에 학습이 끝남을 수식적으로 보이는 것이 핵심이다.

증명

예측을 실패한 입력 데이터의 수를 $n$이라고 하면 위와 같이 가중치를 업데이트 할 때 $n$의 상한이 있음을 보일 것이다.

---

$\mathbf{x}_{n}$의 예측에 실패했으므로 다음과 같이 가중치를 업데이트한다.

$$\begin{equation} \mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n} \label{eq3} \end{equation}$$

그리고 $X^{+}$와 $X^{-}$가 분리가능하다고 가정했으므로 다음의 식을 만족하는 솔루션 $\mathbf{w}_{\ast}$가 존재한다.

$$\begin{cases} \mathbf{w}_{\ast}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{\ast}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases} \quad \text{and} \quad \| \mathbf{w}_{\ast} \| = 1$$

그러면 다음이 성립한다.

$$\mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} = \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + y_{n}\mathbf{w}_{\ast}^{T}\mathbf{x}_{n}$$

그리고 $\alpha>0$를 다음과 같이 정의하자.

$$\alpha := \min \limits_{\mathbf{x} \in X} y \mathbf{w}_{\ast}^{T}\mathbf{x}$$

그러면 다음의 부등식이 성립한다.

$$\mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} \ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha$$

그런데 가중치의 초기값이 $\mathbf{w}_{1}=\mathbf{0}$이었으므로 다음의 식이 성립한다.

$$\begin{equation} \begin{aligned} \\ \mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n-1} + 2\alpha \\ &\cdots \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{1} + n\alpha \\ &= n\alpha \end{aligned} \label{eq1} \end{equation}$$

그리고 코시-슈바르츠 부등식에 의해서 다음의 식이 성립한다.

$$\begin{equation} \| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{\ast} \|^{2} \| \mathbf{w}_{n+1} \|^{2} \ge | \mathbf{w}_{\ast}^{T} \mathbf{w}_{n+1} |^{2} \label{eq2} \end{equation}$$

$\eqref{eq1}$와 $\eqref{eq2}$에 의해서 다음의 식이 성립한다.

$$\begin{equation} \| \mathbf{w}_{n+1} \|^{2} \ge n^{2}\alpha^{2} \label{eq4} \end{equation}$$

다시 $\eqref{eq3}$으로부터 아래의 식을 얻는다.

$$\| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} + 2 y_{n}\mathbf{w}^{T}_{n}\mathbf{x}_{n}$$

그런데 $y_{n}\mathbf{w}^{T}_{n} \mathbf{x}_{n} \le 0$이므로 다음의 부등식을 얻는다.

$$\| \mathbf{w}_{n+1} \|^{2} \le \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} \le \| \mathbf{w}_{n} \| ^{2} + \beta$$

이때 $\beta = \max \limits_{\mathbf{x} \in X} \| \mathbf{x} \|^{2}$이다. 그러면 가중치의 초기값이 $\mathbf{w}_{1}=\mathbf{0}$이었으므로 다음의 식이 성립한다.

$$\begin{equation} \begin{aligned} \| \mathbf{w}_{n+1} \|^{2} &\le \| \mathbf{w}_{n} \| ^{2} + \beta \\ &\le \| \mathbf{w}_{n-1} \| ^{2} + 2\beta \\ &\le \| \mathbf{w}_{n-2} \| ^{2} + 3\beta \\ &\vdots \\ &\le \| \mathbf{w}_{1} \|^{2} + n\beta \\ &= n\beta \end{aligned} \label{eq5} \end{equation}$$

두 부등식 $\eqref{eq4}, \eqref{eq5}$를 한데 묶으면 다음과 같다.

$$n^{2} \alpha^{2} \le \| \mathbf{w}_{n+1} \|^{2} \le n\beta$$

$n$에 대해서 정리하면 다음과 같다.

$$\begin{align*} && n^{2} \alpha^{2} &\le n\beta \\ \implies && n &\le \dfrac{\beta}{\alpha^2} \end{align*}$$

따라서 다음을 얻는다.

$$n_{\text{max}} = \dfrac{\beta}{\alpha^{2}}$$

이는 퍼셉트론이 예측을 실패하는 횟수가 아무리 많아야 $\dfrac{\beta}{\alpha^{2}}$라는 뜻이고 그 이후로는 모든 트레이닝 데이터에 대해서 예측을 성공한다는 의미이다.

■