Python 코드로 Nadaraya-Watson 모델 소개

개시하다

PRML(Pattern Recognition and Machine Learning) Nadaraya-Watson 모델에서 배운 내용을 정리하고 인공적으로 생성된 데이터를 사용하여 학습했다.주로 6.3절 내용이다.필요에 따라python 코드를 읽으십시오.

태그 정보

트레이닝 데이터에 대한 설명 변수:\mathbf{X} =\left\{mathbf{x 1},\mathbf{x 2},\cdots\mathbf{xN}\right\},\mathbf{xn} = (x{n, 1}, x{n, 2},\cdots, x{n D})^T

트레이닝 데이터의 목적 변수:\mathbf{t} =\left\{t 1, t 2,\cdotst N\right\}

새 입력 데이터:\mathbf{x*}

\mathbf{x*}에 대한 목적 변수: t*

\mathbf{x*}의 목적 변수에 대한 예측: y (\mathbf{x]*)

근접한 데이터로 예측하다

'근거리' 데이터를 사용하여 새로운 입력 데이터의 출력을 예측하는 것을 고려하다.
import 문

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import norm

np.random.seed(28)

데이터

이번에는 다음 t=sin(x)+0.1x^2 데이터를 사용합니다.
작도 코드

line_x = np.linspace(0.0, 2*np.pi, num=500)
line_t = [np.sin(x) + 0.1*x**2 for x in line_x]

plt.plot(line_x, line_t)

다음과 같은 45개의 데이터가 생성되었습니다.이번에는 이것을 훈련 데이터로 삼아 공부한다.
\begin{aligned}
t_n =\mathcal{N}(t_n | sin(x_n) + 0.1x^2, 0.25)
\end{aligned}
작도 코드

beta = 0.5

data_x = np.random.rand(45) * 2 * np.pi
data_t = [np.sin(x) + 0.1*x**2 + np.random.normal(0, beta) for x in data_x]

plt.scatter(data_x, data_t)
plt.plot(line_x, line_t)

근린법

최근 인접법에서 훈련 데이터에서 변수와\mathbf{x*}의 거리(유클리드 거리 등)가 가장 가까운 목적 변수 t*.이 알고리즘은 각 데이터에 지나치게 적응할 수 있다.

k-인접역법

k-근방법은 최근 인접법과 비슷하며, 훈련 데이터에서 설명 변수와\mathbf{x*}의 거리가 가장 가까운 것부터 순서대로 k개를 선택하여 산술 평균 중 t*.적당한 k의 값을 선택하면 요즘 방법보다 안 어울려 예측이 잘 되는 것 같아요.
아래 그림에서 왼쪽 상단의 k=1은 최근 인접법이다.k가 커지면서 분포의 국부적 변화를 예측하는 것이 작아진다.
학습 및 드로잉 코드

def kNN(k, xs, ts, x_star):
    distance = [[abs(x - x_star), t] for (x, t) in zip(xs, ts)]
    distance.sort()
    t_star = 0
    for i in range(k):
        t_star += distance[i][1]
    t_star /= k
    
    return t_star

def RMSE(true_t, pre_t):
    sum = 0
    for (tt, pt) in zip(true_t, pre_t):
        sum += (tt - pt) ** 2
    rmse = np.sqrt(sum / len(true_t))
    
    return rmse

ks = list(range(1, 21))
kNN_RMSEs = []
nearest_neighbour_ts = [[] for _ in range(len(ks))]

for (i, k) in enumerate(ks):
    for x in line_x:
        nearest_neighbour_ts[i].append(kNN(k, data_x, data_t, x))
    kNN_RMSEs.append(RMSE(line_t, nearest_neighbour_ts[i]))

fig = plt.figure(figsize=(12, 9))

ax1 = fig.add_subplot(2, 2, 1)
ax2 = fig.add_subplot(2, 2, 2)
ax3 = fig.add_subplot(2, 2, 3)
ax4 = fig.add_subplot(2, 2, 4)

ax1.scatter(data_x, data_t)
ax1.plot(line_x, line_t)
ax1.plot(line_x, nearest_neighbour_ts[0], label="k=1")

ax2.scatter(data_x, data_t)
ax2.plot(line_x, line_t)
ax2.plot(line_x, nearest_neighbour_ts[2], label="k=3")

ax3.scatter(data_x, data_t)
ax3.plot(line_x, line_t)
ax3.plot(line_x, nearest_neighbour_ts[8], label="k=9")

ax4.scatter(data_x, data_t)
ax4.plot(line_x, line_t)
ax4.plot(line_x, nearest_neighbour_ts[19], label="k=20")

ax1.legend(loc = 'upper left')
ax2.legend(loc = 'upper left')
ax3.legend(loc = 'upper left')
ax4.legend(loc = 'upper left')

plt.show()

아래의 그림은 k에 대한 평균 제곱 오차치(실제 분포에 비해)를 출력했지만 k가 3에서 10 정도 되는 곳에서 오차가 작아진 것을 알 수 있다.k의 값이 너무 크고 작아도 좋지 않다.
작도 코드

plt.plot(ks, kNN_RMSEs)
plt.xlabel("k")
plt.ylabel("RMSE")
plt.show()

Nadaraya-Watson 모델

k-부근법의 생각을 조금만 더 넓혀보고mathbf{x*}와 훈련 데이터의 거리에 따라 가중치를 바꾸는 방법을 생각해 봅시다.여기서 우리가 고려하는 것은 거리가 가까울수록 값이 크다는 것을 나타내는 비음함수 g(\cdot)이다.k(\cdot,\cdot)는 다음과 같이 정의됩니다.
\begin{aligned}
k(\mathbf{x_*},\mathbf{x_n}) =\frac{g(\mathbf{x_*} -\mathbf{x_n})}{\sum^N_{m=1}g(\mathbf{x_*}-\mathbf{x_m})}
\end{aligned}
그리고 이 함수를 사용하면 다음과 같다.n에 가중을 가하고 아래의 모델로 t*를 진행한다.이 모형은 Nadaraya-Watson 모형이라고 합니다.
\begin{aligned}
y(\mathbf{x}_*) =\sum^N_{n=1}k(\mathbf{x_*},\mathbf{x_n})t_n
\end{aligned}
정의에 따라 k(\cdot,\cdot)는 다음 두 조건을 충족합니다.
\begin{aligned}
k(\mathbf{x_*},\mathbf{x_n}) &\geq 0\\
\sum^N_{n=1}k(\mathbf{x_*},\mathbf{x_n}) &= 1
\end{aligned}
그리고 다음과 같이 구체적인 k(\cdot,\cdot)를 규정하고 아까의 데이터로 분포 예측과 균형 오차를 계산한다.반드시 g(\cdot)를 고스 분포로 바꿀 필요는 없다.
\begin{aligned}
k(\mathbf{x_*},\mathbf{x_n}) =\frac{\mathcal{N}(\mathbf{x}_* |\mathbf{x}_n,\sigma^2)}{\sum^N_{m=1}\mathcal{N}(\mathbf{x}_* |\mathbf{x}_m,\sigma^2)}\\
\end{aligned}
k(\mathbf{x*},\mathbf{xn})의 매개 변수\sigma의 값에 따라 각 데이터에 적합한 수량을 결정합니다.오른쪽 상단의 그림을 보면 분포가 매끄러운 곡선을 보일 것으로 예상된다.
학습 및 드로잉 코드

def nadaraya_watson(sigma, xs, ts, x_star):
    prob_sum = 0
    tmp_t = 0
    for (x, t) in zip(xs, ts):
        prob = norm.pdf(x_star, x, sigma)
        prob_sum += prob
        tmp_t += prob * t
    pre_t = tmp_t / prob_sum

    return pre_t

sigmas = [(0.1*i) ** 2 for i in range(1, 21)]
nw_RMSEs = []
nadaraya_watson_ts = [[] for _ in range(len(sigmas))]

for (i, sigma) in enumerate(sigmas):
    for x in line_x:
        nadaraya_watson_ts[i].append(nadaraya_watson(sigma, data_x, data_t, x))
    nw_RMSEs.append(RMSE(line_t, nadaraya_watson_ts[i]))

fig = plt.figure(figsize=(12, 9))

ax1 = fig.add_subplot(2, 2, 1)
ax2 = fig.add_subplot(2, 2, 2)
ax3 = fig.add_subplot(2, 2, 3)
ax4 = fig.add_subplot(2, 2, 4)

ax1.scatter(data_x, data_t)
ax1.plot(line_x, line_t)
ax1.plot(line_x, nadaraya_watson_ts[0], label="$\sigma=0.01$")

ax2.scatter(data_x, data_t)
ax2.plot(line_x, line_t)
ax2.plot(line_x, nadaraya_watson_ts[5], label="$\sigma=0.36$")

ax3.scatter(data_x, data_t)
ax3.plot(line_x, line_t)
ax3.plot(line_x, nadaraya_watson_ts[9], label="$\sigma=1.0$")

ax4.scatter(data_x, data_t)
ax4.plot(line_x, line_t)
ax4.plot(line_x, nadaraya_watson_ts[19], label="$\sigma=4.0$")

ax1.legend(loc = 'upper left')
ax2.legend(loc = 'upper left')
ax3.legend(loc = 'upper left')
ax4.legend(loc = 'upper left')

plt.show()

작도 코드

plt.plot(sigmas, nw_RMSEs)
plt.xlabel("sigma")
plt.ylabel("RMSE")
plt.show()

이론

모델

목적 변수 tn은 y(\mathbf{z]n)에 고스 분포의 오차를 따라 생성된 것으로 여겨진다.또한\mathbf{z}n직접 관찰할 수 없으며 일부 분포 g(\mathbf{xi]n)에 따라\mathbf{xi}n, mathbf{x} 사용n =\mathbf{z}_n +\mathbf{\xi}_n의 형식으로 관측되었다고 여긴다.출력 오차가 고스 분포를 따르기 때문에 관측값\{\mathbf{x}n, t_n\}\; (n=1,\cdotsN)에 대응하는 제곱과 오차 함수를 고려합니다.
\begin{align}
E =\frac{1}{2}\sum^N_{n=1}\int\{y(\mathbf{x}_n -\mathbf{\xi}_n) - t_n\}^2g(\mathbf{\xi}_n)d\mathbf{\xi}_n
\end{align}
변분법을 사용하여 y(\mathbf{z})에 비해 E를 최소화하고 y(\mathbf{x})의 가장 좋은 해답은 Nadaraya-Watson 모델에 있음을 나타낸다.

도출 해제

먼저, y(\mathbf{x})의 미세한 변화를 고려합니다.\epsilon은 작게 잡았고 eta(\mathbf{x})는 임의의 함수로
\begin{aligned}
y(\mathbf{x})\rightarrow y(\mathbf{x}) +\epsilon\eta(\mathbf{x})
\end{aligned}
.이 대입 (1) 오른쪽의 y,tild{E}을 통과하세요
\begin{aligned}
\tilde{E} &=\frac{1}{2}\sum^N_{n=1}\int\{y(\mathbf{x}_n -\mathbf{\xi}_n) +\epsilon\eta(\mathbf{x}_n -\mathbf{\xi}_n) - t_n\}^2g(\mathbf{\xi}_n)d\mathbf{\xi}_n\\
&= E +\epsilon\cdot\frac{1}{2}\sum^N_{n=1}\int\{y(\mathbf{x}_n -\mathbf{\xi}_n) - t_n\}\eta(\mathbf{x}_n -\mathbf{\xi}_n)g(\mathbf{\xi}_n)d\mathbf{\xi}_n + O(\epsilon^2)
\end{aligned}
.\epsilon의 계수가 0일 때 E가 가장 작기 때문에\epsilon의 계수는 0이다
\begin{align}
\frac{1}{2}\sum^N_{n=1}\int\{y(\mathbf{x}_n -\mathbf{\xi}_n) - t_n\}\eta(\mathbf{x}_n -\mathbf{\xi}_n)g(\mathbf{\xi}_n)d\mathbf{\xi}_n = 0
\end{align}
.이것은 모든\eta(\mathbf{x})에 대해 생성되어야 합니다.
\begin{aligned}
\eta(\mathbf{x}) =\delta(\mathbf{x} -\mathbf{z})
\end{aligned}
옵션을 선택하면 됩니다.또한 이렇게 하면\mathbf{\xi}n상의 포인트를 평가할 수 있다.
\begin{aligned}
(2) &\Leftrightarrow\sum^N_{n=1}\int\{y(\mathbf{x}_n -\mathbf{\xi}_n) - t_n\}\delta(\mathbf{x}_n +\mathbf{\xi}_n -\mathbf{z})g(\mathbf{\xi}_n)d\mathbf{\xi}_n = 0\\
&\Leftrightarrow\sum^N_{n=1}\{y(\mathbf{z}) - t_n\}g(\mathbf{z} -\mathbf{x}_n) = 0\\
&\Leftrightarrow y(\mathbf{z})\sum^N_{n=1}g(\mathbf{z} -\mathbf{x}_n) =\sum^N_{n=1}t_ng(\mathbf{z} -\mathbf{x}_n)\\
&\Leftrightarrow y(\mathbf{z}) =\sum^N_{n=1}t_n\frac{g(\mathbf{z} -\mathbf{x}_n)}{\sum^N_{m=1}g(\mathbf{z} -\mathbf{x}_m)}\\
\end{aligned}
지금\mathbf{z}은\mathbf{x]*그렇다면
\begin{aligned}
y(\mathbf{x}_*) &= k(\mathbf{x}_*,\mathbf{x}_n)t_n\\
where\quad k(\mathbf{x}_*,\mathbf{x}_n) &=\frac{g(\mathbf{x}_* -\mathbf{x}_n)}{\sum^N_{m=1}g(\mathbf{x}_* -\mathbf{x}_m)}
\end{aligned}
.이렇게 되면 확실히 Nadaraya-Watson 모형으로 y(\mathbf{x})의 가장 좋은 해를 제시할 수 있다.
!
이 글은 쓰이지 않았지만 PRML의 6.3.1은 다른 방법으로 Nadraya-Watson 모형을 도출한 것이다.입력과 출력의 동시 분포를 고려하면 Nadraya-Watson 모델이 입력 조건 분포의 기대치로 내보냅니다.최우해뿐만 아니라 조건부 분포도 도출할 수 있어 더 많은 정보를 얻을 수 있고 궁금하면 읽어보는 것이 좋다.