Projeto Final - Algoritmos e Incerteza - Algoritmos ...mmolinaro/algInc18-2/apresentacoes/Apresentacao... · Projeto Final - Algoritmos e Incerteza - Algoritmos Projection-Free Guilherme

Projeto Final - Algoritmos e Incerteza -Algoritmos Projection-Free

Guilherme Bodin

Guilherme Bodin Algoritmos e incerteza 13 de Novembro de 2018 1 / 25

Sumario

1 Algoritmos Projection-Free

2 Revisao de algebra

3 Low-rank matrix completion problem

4 Como e porque usar para matrix completion

5 Online Conditional Gradient e seu regret


Algoritmos Projection-Free




O que e uma projecao?

Projecao em nosso contexto e projecao de um ponto em um conjuntoconvexo.

A projecao de um ponto y ∈ Rn em um conjunto convexo C ⊂ Rn ebasicamente o ponto mais proximo de y em C no sentindo de normaeuclidiana.

PC(y) , arg minx∈C

||x− y||



O que e uma projecao?

Figura: Exemplo de lecture notes da Angelia Nedic



Onde usamos projecoes?

Gradient Descent!

Figura: Algoritmo Gradient Descent do livro do Hazan

Metodo de Newton

Outros algoritmos podem usar outras versoes de projecao (ninguemdisse que o ponto mais proximo precisa ser no sentido da normaeuclidiana)



Projecoes sao caras?

Depende do problema. Vou tentar responder daqui a pouco.



Projection-Free

Frank-Wolfe (Conditional Gradient)

Figura: Algoritmo Gradient Descent do livro do Hazan


Revisao de algebra

Revisao de algebra


Revisao de algebra

Valores singulares de uma matriz

Seja a matriz X ∈ Rn×m. O numero nao negativo σ ∈ R+ e dito valorsingular da matriz X se existirem dois vetores u ∈ Rn e v ∈ Rm tal que:

XTu = σv , Xv = σu

Os vetores u e v sao chamados vetor singular a esquerda e vetor singular adireita respectivamente.


Revisao de algebra

Decomposicao singular de uma matriz (SVD)

A matriz X pode ser escrita como

X = UΣV T , U ∈ Rn×ρ , V ∈ Rρ×m

onde ρ = min{n,m}, U e a base ortogonal dos vetores singulares a es-querda, V e a base ortogonal dos vetores singulares a direita, e Σ e a matrizdiagonal com os respectivos valores singulares.


Revisao de algebra

Posto, norma nuclear e produto interno

O posto (em ingles rank) de uma matriz e o menor k < ρ tal que a matrizpode ser escrita como pode ser escrita como:

X = UV , U ∈ Rn×k , V ∈ Rk×m

A norma nuclear de X e a norma `1 dos seus valores singulares

||X||∗ =

ρ∑i=1

σi

Denota-se A •B o produto interno de matrizes como vetores em Rn×m, ouseja,

A •B =

n∑i=1

m∑j=1

AijBij = Tr(ABT )


Low-rank matrix completion problem

Low-rank matrix completionproblem



Formulacao

Imagine que uma exista uma matriz de opinioes M ∈ {0, 1, ∗}n×msobre filmes/series onde:

Mij =

0 se pessoa i nao gosta do filme j

1 se pessoa i gosta do filme j

∗ se pessoa i nao opinou/viu sobre j

O objetivo e completar essa matriz com 1’s e 0’s nas entradasfaltantes.

A premissa dessa formulacao e assumir que a matriz tem rank baixo,ou seja, a matriz M ”verdadeira”pode ser escrita como :

M = UV , U ∈ Rn×k , V ∈ Rk×m

intuitivamente isso significa que apenas k fatores (diretor, genero,atores, etc) descrevem as entradas de M .



Formulacao

Vamos chamar de || · ||OB a norma euclidiana das entradas observadas damatriz, ou seja,

||M ||2OB =∑Mij 6=∗

M2ij

Gostarıamos de minimizar essa norma || · ||2OB de forma que a matriz resul-tante tenha rank baixo.

minX∈Rn×m

||X −M ||2OB

s.a. rank(X) ≤ k

Problema: Nao sei o que significa essa restricao em termos de programacaomatematica. rank(X) ≤ k. O padrao e substituir rank pela || · ||∗, isso euma relaxacao.



Formulacao

Com as alteracoes o problema fica:

minX∈Rn×m

||X −M ||2OB

s.a. ||X||∗ ≤ k

E pode-se mostrar que:

||X||∗ = Tr (√XXT )

o que nos leva ao problema:

minX∈Rn×m

||X −M ||2OB

s.a. Tr (√XXT ) ≤ k


Como e porque usar para matrix completion

Como e porque usar para matrixcompletion



Como?

Vamos reestruturar o problema chamando

∇f(Xt) = ∇t = (Xt −M)OB

{(Xt

ij −Mij), (i, j) ∈ OB0, caso contrario

Assumindo (como no livro) que a matriz X e quadrada e simetrica, nessecaso norma nuclear e traco sao iguais. O problema vira.

minX∈Rn×n

X • ∇t

s.a. TrX ≤ ke e possıvel mostrar (exercıcio do livro) que isso e equivalente a:

minx∈Rn

xT∇tx

s.a. ||x||22 ≤ kque e equivalente a calcular o autovetor associado ao maior autovalor de∇t (direcao que o gradiente mais cresce).



Como?

Chamando de vmax(∇t) essa conta temos o algoritmos conditional gradientpara esse problema:



Por que?

Figura: Paragrafo do capıtulo 7 do livro do Hazan


Online Conditional Gradient e seu regret

Online Conditional Gradient e seuregret



Online Conditional Gradient

Figura: Algoritmo Online Conditional Gradient do livro do Hazan



Regret



Regret


OBRIGADOGuilherme Bodin

13 de Novembro de 2018


Documents

Projeto Final - Algoritmos e Incerteza - Algoritmos ...mmolinaro/algInc18-2/apresentacoes/Apresentacao... · Projeto Final - Algoritmos e Incerteza - Algoritmos Projection-Free Guilherme