É comum durante o aprendizado de Machine Learning confundir os papéis do espaço espaço de hipóteses e do algoritmo de aprendizagem no determinação da hipótese encontrada. Para tirar esta dúvida resolvi escrever um pequeno exemplo que mostra dois algoritmos simples (Perceptron e Regressão Linear) explorando espaços de hipóteses completamente distintos.
Primeiramente, o espaço de hipóteses $\mathcal{H}$ contém a classe de funções consideradas por um algoritmo de aprendizagem, que irá escolher a função $g \in \mathcal{H}$ baseado em uma função de erro calculada em um conjunto de treinamento. A junção destas três partes é chamada de modelo de aprendizagem. Nesta aula sobre VC dimension, o prof. Mostafa argumenta que a capacidade de generalização de um modelo depende somente do espaço de hipóteses. Isto pode parecer contra-intuitivo, pois algoritmos diferentes podem resultar em soluções com desempenho muito diferente. Porém, como iremos ver nos exemplos abaixo, é o espaço de hipóteses que define a complexidade de um modelo (e, consequentemente sua capacidade de generalização) e o resultado apresentado pelo prof. Mostafa é um limitante inferior para o erro. Como não conhecemos a função objetivo $f$, que pode ser tão complexa quanto possível, existirá sempre uma parte de $f$ que não poderá ser capturada usando funções no espaço $\mathcal{H}$. Na aula sobre Bias-Variance, esta "margem" é definida como o bias.
Caso linearmente separável¶
Neste exemplo mostramos como diferentes algoritmos de aprendizado encontram diferentes hipóteses $g$ mesmo que estejam considerando o mesmo espaço de hipóteses $\mathcal{H} = \{f_w: f_w(x) = sign(w^T x) \}$.
Primeiramente, vamos amostrar duas populações de dois retângulos no plano.
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import scipy as sp
import scipy.stats
import sklearn
import sklearn.linear_model
dados1 = sp.stats.uniform.rvs(size=100 * 2).reshape((100, 2))
dados1[:,0] = dados1[:,0] * 3 + 5
dados1[:,1] = dados1[:,1] * 0.5 - 2
dados2 = sp.stats.uniform.rvs(size=100 * 2).reshape((100, 2))
dados2[:,0] = dados2[:,0] * 2
dados2[:,1] = dados2[:,1] * 5 + 2
plt.xlim((-2, 10))
plt.ylim((-10, 15))
plt.plot(dados1[:,0], dados1[:,1], 'ro')
plt.plot(dados2[:,0], dados2[:,1], 'bo')
def plot_decision(model, color, caption, min_=-2, max_=10):
xx = np.linspace(min_, max_, 100)
# Graças ao scikit learn e ao python, podemos passar
# model como parâmetro de plot_decision
coef = model.coef_.reshape(-1)
a = -coef[0] / coef[1]
yy = xx * a - model.intercept_ / coef[1]
plt.plot(xx, yy, color, label=caption)
Para selecionar a hipótese, usaremos dois algoritmos diferentes: perceptron e regressão linear. Em seguida, chamamos a função plot_decision para desenhar a superfície de separação. Escolhemos estes dois algoritmos pois ambos são algoritmos considerados "simples" por estimarem somente decisões lineares em $w$.
def treina_e_plota(X1, X2, min_=-2, max_=10, intercept=True):
X = np.r_[X1, X2]
y = np.r_[np.ones(X1.shape[0]), -np.ones(X2.shape[0])]
perc = sklearn.linear_model.Perceptron(fit_intercept=intercept, n_iter=500)
perc.fit(X, y)
linreg = sklearn.linear_model.LinearRegression(fit_intercept=intercept)
linreg.fit(X, y)
plt.figure(figsize=(10, 10))
plt.plot(X1[:,0], X1[:,1], 'ro')
plt.plot(X2[:,0], X2[:,1], 'bo')
plot_decision(perc, 'g', 'Perceptron', min_, max_)
plot_decision(linreg, 'y', 'Regressão linear', min_, max_)
plt.legend()
plt.title('Caso linearmente separável')
print('Score Perceptron', perc.score(X, y))
print('Score LinRegression', np.sum(np.sign(linreg.predict(X)) == y) / X.shape[0])
return perc, linreg
# Chama os algoritmos de treinamento.
treina_e_plota(dados1, dados2)
Como podemos ver, cada algoritmo de aprendizagem selecionou uma hipótese diferente, mas ambas separam perfeitamente as duas classes.
Caso não linearmente separável ¶
Como visto na aula sobre modelos lineares, os modelos estimados pela Regressão Linear e pelo Perceptron são lineares em $w$, mas não necessariamente em $x$. Para estimar modelos não-lineares em $x$ criamos uma versão transformada $z$ de todas as entradas e estimamos $f(z) = w^T z$. É importante notar que ao fazer essa transformação o espaço de hipóteses muda. Iremos exemplificar esta transformação estimando uma superfície de decisão para os dados abaixo.
def generate_circle(loc, scale, A, B, inside, size):
X = np.zeros((size, 2))
center = loc + scale/2
#print(center)
while size > 0:
point = scale * sp.stats.uniform.rvs(size=2) + loc
#print(point, (point[0] - center[0])**2/A**2 + (point[1] - center[1])**2/B**2)
if inside and (point[0] - center[0])**2/A**2 + (point[1] - center[1])**2/B**2 <= 1:
X[size-1] = point
size -= 1
elif not inside and (point[0] - center[0])**2/A**2 + (point[1] - center[1])**2/B**2 > 1:
X[size-1] = point
size -= 1
#size -= 1
return X
plt.figure(figsize=(8, 8))
dados1 = generate_circle(np.array([-5, -5]), np.array([10, 10]), 5, 3, True, 500)
dados2 = generate_circle(np.array([-5, -5]), np.array([10, 10]), 5, 3, False, 500)
plt.plot(dados1[:,0], dados1[:,1], 'ro')
plt.plot(dados2[:,0], dados2[:,1], 'bo')
Vamos explorar o espaço de hipóteses das funções de decisão elípticas $\mathcal{H} = \{ f : f(x; A, B) = sign(\frac{(x-c_x)^2}{A^2} + \frac{y - c_y)^2}{B^2} - 1) \}$ e, portanto, estimaremos o seguinte modelo linear:
$$ f(x; \alpha, \beta, \gamma) = sign( \alpha (x_1 - \overline{x_1})^2 + \beta (x_2 - \overline x_2)^2 + \gamma) = sign(\alpha z_1 + \beta z_2 + \gamma), $$com
$$ z_i = (x_i - \overline x_i)^2 $$Note que, dados $\alpha, \beta$ e $\gamma$, conseguimos recuperar os parâmetros $A$ e $B$ da elipse.
$$ A = \sqrt{\frac{-\gamma}{\alpha}}, B = \sqrt{\frac{-\gamma}{\beta}}. $$media = dados1.mean(axis=0)
dados1_X = (dados1 - media)**2
dados2_X = (dados2 - media)**2
perc, linreg = treina_e_plota(dados1_X, dados2_X, -3, 30)
Podemos ver no gráfico acima uma diferença entre ambos algoritmos: como para a Regressão Linear a distância entre um ponto classificado incorretamente e o hiperplano faz diferença, a reta amarela é puxada para cima. Isto ocorre pois os pontos azuis estão mais espalhados verticalmente.
Note que a decisão linear estimada acima é feita no espaço transformado, não no espaço original. Veja abaixo as duas decisões acima plotadas no espaço original de características.
print('Perceptron', perc.coef_, perc.intercept_)
print('Lin Regression', linreg.coef_, linreg.intercept_)
A_perc, B_perc = np.sqrt(-perc.intercept_/perc.coef_)[0]
A_lin, B_lin = np.sqrt(-linreg.intercept_/linreg.coef_)
from matplotlib.patches import Ellipse
plt.figure(figsize=(8,8))
ax = plt.gca()
plt.xlim((-10, 10))
plt.ylim((-10, 10))
plt.plot(dados1[:,0], dados1[:,1], 'ro')
plt.plot(dados2[:,0], dados2[:,1], 'bo')
e_perc = Ellipse(xy=media, width=2*A_perc, height=2*B_perc)
e_perc.set_facecolor('b')
e_perc.set_alpha(0.5)
ax.add_patch(e_perc)
e_lin = Ellipse(xy=media, width=2*A_lin, height=2*B_lin)
e_lin.set_facecolor('y')
e_lin.set_alpha(0.5)
ax.add_patch(e_lin)
Espero que este exemplo tenha sido significativo e que a diferença entre algoritmo de aprendizagem e espaço de hipóteses tenha sido esclarescida. Como sempre, quaisquer sugestões ou críticas são benvindas nos comentários.
