sexta-feira, 13 de maio de 2016

Espaços de hipótese e algoritmos de aprendizagem

É 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.

In [9]:
%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')
Out[9]:
[<matplotlib.lines.Line2D at 0x2179590>]
In [11]:
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$.

In [12]:
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)
Score perceptorn 1.0
Score LinRegression 1.0
Out[12]:
(Perceptron(alpha=0.0001, class_weight=None, eta0=1.0, fit_intercept=True,
       n_iter=500, n_jobs=1, penalty=None, random_state=0, shuffle=True,
       verbose=0, warm_start=False),
 LinearRegression(copy_X=True, fit_intercept=True, n_jobs=1, normalize=False))

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.

In [15]:
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')
Out[15]:
[<matplotlib.lines.Line2D at 0x5203a90>]

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}}. $$
In [16]:
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)
Score perceptorn 0.972
Score LinRegression 0.925

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.

In [17]:
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)
Perceptron [[ -63.16696553 -167.94716625]] [ 1476.]
Lin Regression [-0.03890952 -0.10278301] 1.13912219107
Out[17]:
<matplotlib.patches.Ellipse at 0x12fdf9d0>

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.