Regressão Linear 2

Prévia do material em texto

Regressão Linear (II)
Prof. Danilo Silva
EEL7514/EEL7513 - Tópico Avançado em Processamento de Sinais:
Introdução ao Aprendizado de Máquina
EEL / CTC / UFSC
Tópicos
I Regressão linear: revisão
I Método do gradiente
I Normalização de atributos
2 / 38
Regressão Linear: Revisão
Regressão Linear
I Modelo de regressão linear:
ŷ = f(x) = w0 + w1x1 + · · ·+ wnxn = wTx
onde
I y ∈ R é o valor-alvo do qual ŷ ∈ R é uma predição
I x =
[
1 x1 · · · xn
]T ∈ Rn+1 é o vetor de atributos
I w =
[
w0 w1 · · · wn
]T
é o vetor de parâmetros
I Conjunto de treinamento D = {(x(1), y(1)), . . . , (x(m), y(m))}
organizado em uma matriz de projeto e um vetor de rótulos
X =
— (x
(1))T —
...
— (x(m))T —
 e y =
 y
(1)
...
y(m)

4 / 38
Exemplo
5 / 38
Regressão Linear com Funções de Base
I De maneira geral, os atributos xi podem ser escolhidos como uma
transformação não-linear de uma ou mais variáveis de entrada
xi = ϕi(x), ou xi = ϕi(u1, . . . , uN )
onde ϕi(·) são chamadas de funções de base
I Um exemplo é regressão polinomial de ordem n:
ŷ = w0 + w1x+ w2x
2 + · · ·+ wnxn
onde ϕi(x) = xi.
I Nesse caso, embora o modelo continue linear em relação aos
atributos xi (e também em relação aos parâmetros wi), um ajuste mais
flexível pode ser feito com relação à variável original x
6 / 38
Exemplo
7 / 38
Mínimos quadrados
I Função custo:
J(w) =
1
m
m∑
i=1
(wTx(i) − y(i))2 = 1
m
‖Xw − y‖2
I Gradiente:
∇J(w) = 2
m
XT (Xw − y)
I Solução ótima (equação normal):
w = (XTX)−1XTy
8 / 38
Mínimos quadrados com regularização `2
I Função custo:
J(w) =
1
m
‖Xw − y‖2 + λ 1
m
‖w‖2
I Gradiente:
∇J(w) = 2
m
XT (Xw − y) + λ 2
m
w
I Solução ótima (equação normal):
w = (XTX + λI)−1XTy
9 / 38
Limitações da solução analítica
I Nem todas as funções custo admitem solução analítica
I Ex: regularização `1, perda `1 (MAE), outras perdas
I Calcular XTX pode ser computacionalmente custoso para n muito
grande: a ordem de complexidade (em número de operações) é O(mn2)
I Solução: métodos iterativos de otimização
10 / 38
Introdução à Otimização
Numérica
Introdução à otimização numérica
I Problema (otimização sem restrições):
min
w
J(w)
A solução do problema (mínimo global) é denotada por w∗
I Condição necessária de 1a ordem para otimalidade:
∇J(w) = 0
Todo ponto que satisfaz essa condição é um ponto estacionário
I Nem todo ponto estacionário é um mínimo local, mas a maioria dos
métodos de otimização satisfaz-se em encontrar um ponto estacionário
12 / 38
Exemplo
13 / 38
Convexidade
I Se J(w) é uma função convexa, então todos os pontos estacionários
são mínimos globais (i.e., a condição de 1a ordem é suficiente)
I Uma função é convexa se todo segmento de reta conectando dois
pontos no gráfico da função situa-se inteiramente acima da função
14 / 38
Métodos de otimização
I Em geral, produzem uma sequência de pontos w[0], w[1], . . . , w[t] que
reduzem o valor da função J(w) a cada iteração
I Algoritmo genérico:
initialize w[0]
for t = 1, . . . , max_iter:
update w[t]
if ‖∇J(w[t])‖ < tol: break
I A diferença entre os métodos está na atualização de w[t]
I Se a função é não-convexa, o ponto estacionário encontrado depende
do ponto inicial w[0]
15 / 38
Exemplo
16 / 38
Exemplo
17 / 38
Métodos de otimização
I Constroem uma aproximação local para J(w[t]) em torno de w[t−1]
I Métodos de 1a ordem:
J(w + δ) ≈ J(w) +∇J(w)Tδ
I Métodos de 2a ordem:
J(w + δ) ≈ J(w) +∇J(w)Tδ + 12δ
T∇2J(w)δ
onde a matriz hessiana é dada por
∇2J(w) =

∂2
∂w0∂w0
J(w) ∂
2
∂w0∂w1
J(w) · · · ∂2∂w0∂wnJ(w)
∂2
∂w1∂w0
J(w) ∂
2
∂w1∂w1
J(w) · · · ∂2∂w1∂wnJ(w)
...
...
. . .
...
∂2
∂wn∂w0
J(w) ∂
2
∂wn∂w1
J(w) · · · ∂2∂wn∂wnJ(w)

18 / 38
Exemplo
I O gradiente indica a tangente, enquanto a hessiana indica a curvatura
I Ex:
J(w) = 1m‖Xw − y‖
2 + λ 1m‖w‖
2
∇J(w) = 2mX
T (Xw − y) + λ 2mw
∇2J(w) = 2mX
TX + λ 2mI
19 / 38
Exemplo
Q =
[
2 0
0 2
]
Q =
[
2 0
0 0
]
Q =
[
2 0
0 −2
]
J(w) =
1
2
wTQw, Q = QT =⇒ ∇2J(w) = Q
I Os autovalores da hessiana estão associados ao grau de curvatura
20 / 38
Método do Gradiente
Método do gradiente (gradient descent / steepest descent)
I Método de 1a ordem
I Percorre o espaço de busca escolhendo sempre a direção de maior
declive na função objetivo
I Atualização de pesos:
w[t] = w[t−1] − α[t]∇J(w[t−1])
onde α[t] é o tamanho do passo (step length), também chamado de taxa
de aprendizado (learning rate)
I A taxa de aprendizado pode ser escolhida fixa (α[t] = α) ou
adaptativamente
22 / 38
Exemplo
23 / 38
Exemplo
23 / 38
Exemplo
23 / 38
Método de Newton
I Método de 2a ordem
I Encontra o ponto de mínimo da aproximação quadrática
I Atualização de pesos:
w[t] = w[t−1] −
[
∇2J(w[t−1])
]−1
∇J(w[t−1])
I Converge mais rapidamente que o método do gradiente, mas tem a
desvantagem de exigir o cálculo da hessiana
I Ex: se J(w) é uma função quadrática, o método de Newton converge
em um único passo—a solução é exatamente a equação normal
24 / 38
Exemplo
25 / 38
Exemplo
26 / 38
Método do Gradiente para Regressão Linear
I Complexidade reduzida de O(mn2) para O(mn · max_iter)
I Sem regularização:
w[t] = w[t−1] − α 2
m
XT (Xw[t−1] − y)
I Com regularização `2:
w[t] =
(
1− λα 2
m
)
w[t−1] − α 2
m
XT (Xw[t−1] − y)
I Por isso a regularização `2 também é chamada de weight decay
I Com regularização `2 (sem regularizar w0):
w[t] =
(
I− λα 2
m
L
)
w[t−1] − α 2
m
XT (Xw[t−1] − y)
27 / 38
Método do Gradiente: Escolha da Taxa de Aprendizado
I Uma das desvantagens do método do gradiente é ter de escolher a taxa
de aprendizado
I Se α é muito pequeno, a convergência pode ser lenta
I Se α é muito grande, pode ocorrer overshoot. Nesse caso, o método
pode não convergir ou até mesmo divergir
I Sempre é possível encontrar um valor de α (suficientemente pequeno)
que garante convergência. No entanto, para acelerar a convergência na
prática, também é possível usar um valor de α selecionado
adaptativamente de acordo com a iteração, α[t].
28 / 38
Exemplo
29 / 38
Exemplo: Custo em função da iteração
30 / 38
Exemplo: Custo em função da iteração
30 / 38
Exemplo: Custo em função da iteração
30 / 38
Escolha da taxa de aprendizado
I Importante: para analisar a convergência e escolher a taxa de aprendizado,
deve ser usada a função objetivo da otimização, J(w), mesmo que
regularizada—ao invés de usar o erro de treinamento, Jtrain(w)
I Afinal, dependendo de λ, da função objetivo, e do ponto inicial, o erro
Jtrain(w) pode até aumentar em algumas iterações, mas J(w) deve
sempre diminuir se a taxa de aprendizado for escolhida adequadamente
31 / 38
Normalização de Atributos
Convergência do Método do Gradiente
I Se a matriz hessiana ∇2J(w) = 2mX
TX for mal condicionada (isto é,
com valor elevado da razão entre os autovalores máximo e mínimo),
então o método do gradiente apresentará dificuldades de convergir
(comportamento em “zig-zag”)
I Exemplo:
J(w) = λ0w
2
0 + λ1w
2
1
∇J(w) =
[
λ0w0
λ1w1
]
, ∇2J(w) =
[
λ0
λ1
]
w[t] = w[t−1] − α
[
λ0w
[t−1]
0
λ1w
[t−1]
1
]
I Se |λ0/λ1| � 1 ou |λ1/λ0| � 1, então não existe uma taxa de
aprendizado igualmente boa para os dois parâmetros
33 / 38
Exemplo (bem condicionado)
34 / 38
Exemplo (mal condicionado)
34 / 38
Normalização de Atributos
I O melhor condicionamento ocorre quando XTX ∝ I
I Uma solução é normalizar todos os atributos (exceto x0 = 1) para que
tenham média nula e variância unitária:
x′j =
xj − x̄j
σxj
onde x̄j = 1m
∑m
i=1 x
(i)
j e σ
2
xj =
1
m
∑m
i=1(x
(i)
j − x̄j)2
I Exemplo:
X =
1 x
(1)
1
1
...
1 x
(m)
1
 =⇒ 1
m
XTX =
[
1 x̄1
x̄1 σ
2
x1 + x̄
2
1
]
=
[
1 0
0 1
]
se x̄1 = 0 e σx1 = 1
35 / 38
Normalização de Atributos
I A normalização de atributos resulta no modelo linear:
ŷ = f(x) = wTx′ = w0 + w1
(
x1 − x̄1
σx1
)
+ · · ·+ wn
(
xn − x̄n
σxn
)
I Os parâmetros x̄j e σxj devem ser estimados exclusivamente a partir do
conjunto de treinamento e guardadospara serem usados na predição
I Alternativamente, o modelo pode ser reexpresso como:
ŷ = f(x) = w′
T
x
onde w′j = wj/σxj e w
′
0 = w0 −
∑
j wj x̄j/σxj
I Obs: normalização é essencial quando os atributos possuem faixas de
valores bastante diferentes (ex: regressão polinomial)
36 / 38
Extensões
Regressão Não-Linear
I Modelo:
ŷ = f(x) = g(wTx)
onde g(z) é uma função não-linear
I Função custo (perda quadrática):
J(w) =
1
m
m∑
i=1
(g(wTx(i))− y(i))2
I Gradiente:
∇J(w) = 2
m
m∑
i=1
(g(wTx(i))− y(i))g′(wTx(i))x(i)
onde g′(z) = ddzg(z)
38 / 38
	Regressão Linear: Revisão
	Introdução à Otimização Numérica
	Método do Gradiente
	Normalização de Atributos
	Regressão Não-Linear