Algoritmos e ModelaçãoComputacional

Projecto

Paulo MateusMáquinas de Boltzmann Restritas - RBM

MEBiom – LMAC2019

Objetivo

• O objetivo do projeto é implementar um algoritmo de aprendizagem baseado em Máquinas de Boltzmann - um bloco constituinte das Deep BeliefNetworks.• O dados Biomédicos são públicos e fornecidos na

página da disciplinas e provêm do UCI machinelearning repository - http://archive.ics.uci.edu/ml/

Classificador8 CAPITULO 2. CONCEITOS BASICOS

2.1 Classificador

Um classificador sobre um domınio D e simplesmente um mapa f : D ! C onde C

e chamado o conjunto de classes. Por exemplo, para o caso da base da dados Cancer,

o conjunto de classes e C = {benign, malignant} e um elemento em D corresponde a

um tuplo de dez medicoes sobre o tumor. Nos casos de interesse, o domınio e sempre

estruturado da seguinte forma: D =Qn

i=1Di onde n e o numero de medicoes e Di e o

domınio da i-esima medicao. Assim, um elemento d 2 D e da forma d = (d1, . . . , dn).

Dados2.2. DADOS 9

2.2 Dados

O classificador e construıdo (ou aprendido) a partir de um conjunto de dados T . Os dados

sao uma amostra de elementos do domınio e respectiva classe ou seja T = {T1, . . . , Tm}e Tj = (d1j, . . . , dnj, cj) onde m e a dimensao dos dados, di,j 2 Di, cj 2 C para todo o

1 i n e 1 j m. Como os dados sao discretizados, isto e Di ✓ N, podemos veros dados como uma matriz m⇥ (n + 1) de entradas naturais.

Classificar10 CAPITULO 2. CONCEITOS BASICOS

2.3 Classificar vs estimar

Uma maneira simples de classificar consiste em inferir a distribuicao que gera os dados (ha

muitas outras maneiras). Sejam X1 . . . Xn e C variaveis aleatorias para as quais os dados

T sao uma amostra multinomial do vector aleatorio ~V = (X1 . . . , Xn, C). O objectivo de

classificar pode-se reduzir a inferir a distribuicao deste vector da seguinte forma

f (d1, . . . , dn) = c

tal que Pr(~V = (d1, . . . , dn, c)) > Pr(~V = (d1, . . . , dn, c0)) para c0 6= c.

Por outras palavras, sabendo a distribuicao do vector ~V , classificar um elemento do

domınio reduz-se a escolher o elemento da classe que maximiza a probabilidade de observar

o elemento do domınio com este elemento da classe (ou seja f e o estimador de maxima

verosimilhanca para a classe dado o elemento do domınio).

Lei dos grandes números2.3. CLASSIFICAR VS ESTIMAR 11

Note que a dimensao do domınioD cresce exponencialmente com o numero de variaveis,

e portanto inferir a distribuicao (multinomial) do vector V utilizando a lei dos grandes

numeros1 requer dados de dimensao exponencial no numero de variaveis para obter dis-

tribuicoes proximas das distribuicoes reais. Nestas condicoes, quando se utilizam dados

pequenos, a distribuicao obtida fica muito enviesada aos dados, fenomeno a que se da o

nome de overfitting.

1Prob(~V = (d1, . . . , dn, c)) = limm!1|{im:Ti=(d1,...,dn,c)}|

m e T e uma amostra arbitrariamente grande.

2.3. CLASSIFICAR VS ESTIMAR 11

Note que a dimensao do domınioD cresce exponencialmente com o numero de variaveis,

e portanto inferir a distribuicao (multinomial) do vector V utilizando a lei dos grandes

numeros1 requer dados de dimensao exponencial no numero de variaveis para obter dis-

tribuicoes proximas das distribuicoes reais. Nestas condicoes, quando se utilizam dados

pequenos, a distribuicao obtida fica muito enviesada aos dados, fenomeno a que se da o

nome de overfitting.

1Prob(~V = (d1, . . . , dn, c)) = limm!1|{im:Ti=(d1,...,dn,c)}|

m e T e uma amostra arbitrariamente grande.

Campo de Markov Aleatório

Um Campo Aleatório de Markov é1) Vetor aleatório X=(!", … , !%)2) G= (X,E) onde X={!", … , !%}3) Seja A e B conjuntos disjuntos de nós

P( !&!' !( = * !& !( * !' !(

desde que para ir de um nó de A para um nó de B se passe por S em G

4) P(X=x)>0 para todo o x

!" !+

C

!,

!-

Teorema de Hammersley–Clifford

Seja cl(G) o conjunto de cliques do grafo(subgrafos fortemente conexos maximais) então

e ainda

large weights in the second layer. With binary inputs, very large weights are also needed to completelyminimize the reconstruction error. Since the implicit or explicit regularization makes it difficult to reachlarge-weight solutions, the optimization algorithm finds encodings which only work well for examples simi-lar to those in the training set, which is what we want. It means that the representation is exploiting statisticalregularities present in the training set, rather than learning to replicate the identity function.There are different ways that an auto-encoderwith more hidden units than inputs could be prevented from

learning the identity, and still capture something useful about the input in its hidden representation. Insteador in addition to constraining the encoder by explicit or implicit regularization of the weights, one strategy isto add noise in the encoding. This is essentially what RBMs do, as we will see later. Another strategy, whichwas found very successful (Olshausen & Field, 1997; Doi, Balcan, & Lewicki, 2006; Ranzato et al., 2007;Ranzato & LeCun, 2007; Ranzato et al., 2008; Mairal, Bach, Ponce, Sapiro, & Zisserman, 2009), is basedon a sparsity constraint on the code. Interestingly, these approaches give rise to weight vectors that matchwell qualitatively the observed receptive fields of neurons in V1 and V2 (Lee, Ekanadham, & Ng, 2008),major areas of the mammal visual system. The question of sparsity is discussed further in Section 7.1.Whereas sparsity and regularization reduce representational capacity in order to avoid learning the iden-

tity, RBMs can have a very large capacity and still not learn the identity, because they are not (only) tryingto encode the input but also to capture the statistical structure in the input, by approximately maximizing thelikelihood of a generative model. There is a variant of auto-encoder which shares that property with RBMs,called denoising auto-encoder (Vincent et al., 2008). The denoising auto-encoder minimizes the error inreconstructing the input from a stochastically corrupted transformation of the input. It can be shown that itmaximizes a lower bound on the log-likelihood of a generative model. See Section 7.2 for more details.

5 Energy-Based Models and Boltzmann MachinesBecause Deep Belief Networks (DBNs) are based on Restricted Boltzmann Machines (RBMs), which areparticular energy-based models, we introduce here the main mathematical concepts helpful to understandthem, including Contrastive Divergence (CD).

5.1 Energy-Based Models and Products of ExpertsEnergy-based models associate a scalar energy to each configuration of the variables of interest (LeCun& Huang, 2005; LeCun, Chopra, Hadsell, Ranzato, & Huang, 2006; Ranzato, Boureau, Chopra, & LeCun,2007). Learning corresponds to modifying that energy function so that its shape has desirable properties. Forexample, we would like plausible or desirable configurations to have low energy. Energy-based probabilisticmodels may define a probability distribution through an energy function, as follows:

P (x) =e−Energy(x)

Z, (11)

i.e., energies operate in the log-probability domain. Th above generalizes exponential familymodels (Brown,1986), for which the energy function Energy(x) has the form η(θ) · φ(x). We will see below that theconditional distribution of one layer given another, in the RBM, can be taken from any of the exponentialfamily distributions (Welling, Rosen-Zvi, & Hinton, 2005). Whereas any probability distribution can becast as an energy-based models, many more specialized distribution families, such as the exponential family,can benefit from particular inference and learning procedures. Some instead have explored rather general-purpose approaches to learning in energy-basedmodels (Hyvarinen, 2005; LeCun et al., 2006; Ranzato et al.,2007).The normalizing factor Z is called the partition function by analogy with physical systems,

Z =!

x

e−Energy(x) (12)

26

large weights in the second layer. With binary inputs, very large weights are also needed to completelyminimize the reconstruction error. Since the implicit or explicit regularization makes it difficult to reachlarge-weight solutions, the optimization algorithm finds encodings which only work well for examples simi-lar to those in the training set, which is what we want. It means that the representation is exploiting statisticalregularities present in the training set, rather than learning to replicate the identity function.There are different ways that an auto-encoderwith more hidden units than inputs could be prevented from

learning the identity, and still capture something useful about the input in its hidden representation. Insteador in addition to constraining the encoder by explicit or implicit regularization of the weights, one strategy isto add noise in the encoding. This is essentially what RBMs do, as we will see later. Another strategy, whichwas found very successful (Olshausen & Field, 1997; Doi, Balcan, & Lewicki, 2006; Ranzato et al., 2007;Ranzato & LeCun, 2007; Ranzato et al., 2008; Mairal, Bach, Ponce, Sapiro, & Zisserman, 2009), is basedon a sparsity constraint on the code. Interestingly, these approaches give rise to weight vectors that matchwell qualitatively the observed receptive fields of neurons in V1 and V2 (Lee, Ekanadham, & Ng, 2008),major areas of the mammal visual system. The question of sparsity is discussed further in Section 7.1.Whereas sparsity and regularization reduce representational capacity in order to avoid learning the iden-

tity, RBMs can have a very large capacity and still not learn the identity, because they are not (only) tryingto encode the input but also to capture the statistical structure in the input, by approximately maximizing thelikelihood of a generative model. There is a variant of auto-encoder which shares that property with RBMs,called denoising auto-encoder (Vincent et al., 2008). The denoising auto-encoder minimizes the error inreconstructing the input from a stochastically corrupted transformation of the input. It can be shown that itmaximizes a lower bound on the log-likelihood of a generative model. See Section 7.2 for more details.

5 Energy-Based Models and Boltzmann MachinesBecause Deep Belief Networks (DBNs) are based on Restricted Boltzmann Machines (RBMs), which areparticular energy-based models, we introduce here the main mathematical concepts helpful to understandthem, including Contrastive Divergence (CD).

5.1 Energy-Based Models and Products of ExpertsEnergy-based models associate a scalar energy to each configuration of the variables of interest (LeCun& Huang, 2005; LeCun, Chopra, Hadsell, Ranzato, & Huang, 2006; Ranzato, Boureau, Chopra, & LeCun,2007). Learning corresponds to modifying that energy function so that its shape has desirable properties. Forexample, we would like plausible or desirable configurations to have low energy. Energy-based probabilisticmodels may define a probability distribution through an energy function, as follows:

P (x) =e−Energy(x)

Z, (11)

i.e., energies operate in the log-probability domain. Th above generalizes exponential familymodels (Brown,1986), for which the energy function Energy(x) has the form η(θ) · φ(x). We will see below that theconditional distribution of one layer given another, in the RBM, can be taken from any of the exponentialfamily distributions (Welling, Rosen-Zvi, & Hinton, 2005). Whereas any probability distribution can becast as an energy-based models, many more specialized distribution families, such as the exponential family,can benefit from particular inference and learning procedures. Some instead have explored rather general-purpose approaches to learning in energy-basedmodels (Hyvarinen, 2005; LeCun et al., 2006; Ranzato et al.,2007).The normalizing factor Z is called the partition function by analogy with physical systems,

Z =!

x

e−Energy(x) (12)

26

Dificuldade de aprender MRF

• Note que quando mais esparso for o grafo mais simples é a distribuição.

• Se o grafo for completo, estamos na situação de nãotermos dados para o aprender!

• Não há algoritmos eficientes para aprender o melhorMRF para um conjunto de grafos esparsos significativoapenas para árvores!

Algoritmo de Chow-Liu

Máquinas de Boltzmann Bernoulli

• Considere uma MRF com n variáveis escondidas H (Bernoulli) e m visíveis (Multinomiais) V (para já consideremos Bernoulli)• Os dados apenas mostram as variáveis visíveis• G é um grafo é bipartido completoNeste caso

onde W é uma matriz m×# e e a e b são vetores (de viés) com m e n entradas

Máquinas de Boltzmann genéricas

Cada variável visível xi que tome valores {0,… ,di-1} é representada por di variáveis binárias tal que:

xi=k é representado por !"=(0,...,0,1,0,…0) onde todos os valores são 0, exceto a entrada k, que é 1.

Um vetor instâncias de variáveis visíveis v=(k1,...,km) é transformado no vetor $ = ("',..., "() de bits com

M=dim($)= ∑*+'( ,*.

Máquinas de Boltzmann genéricas

Nestas condições

• a= (#$%, … , #$()*$,…, #+% , … , #+(,*$) e

M=dim(a)=∑./$+ 0. (as entradas de # continuam a ser reais)

Note que #.1 = #[3 + ∑ℓ/$.*$ 0ℓ]

• W é uma matriz de dimensão M por n

• 7 8, ℎ = −#;8 − =;ℎ − 8;>ℎ (1)

Aprender RBB – Gibbs SamplingDevido à bipartição temos que:

e mais concretamente, no caso das variáveis escondidas

!(ℎ$ = 1|() = *(+$ + ∑./01 2.$ 3(.)

onde * 4 = 560756

Algoritmo 1Output: Estimar h=(h1,…,hn) a partir de v:Para todo o j=1...n1. 9$ = !(ℎ$ = 1|() , 2 gera-se uma uniforme u em [0,1]3. se u ≤ 9$, coloca-se ℎ$ = 1, caso contrário coloca-se ℎ$ = 0

Mais propriedades das BM

No caso das variáveis visíveis

!(#$ = &|ℎ) =*+,(-$

. + ∑1234 536.6∑ℓ89:;9 <ℓ,1

ℎ1 )

∑>2?<:@3 *+,(-$

> + ∑1234 536>6∑ℓ89:;9 <ℓ,1

ℎ1 )

Algoritmo 2Output : Estimar v=(v1,…,vm) a partir de h, Para todo o i=1..m1. ,$ = [!(#$ = 0|ℎ) , ... ,!(#$ = E$ − 1|ℎ)]2. gera-se uma uniforme u em [0,1]3. se ∑ℓ2?

.@3 ,$[ℓ] <u≤ ∑ℓ2?. ,$[ℓ], coloca-se I$ = &,

Mais propriedades das BM

Recorde que o índices em java necessitam de ser decrementados, ou seja:

• hj=h[j-1]• !"#$#∑ℓ'()*( +ℓ,-=W[. + ∑ℓ0"12" 3ℓ,j-1]

Aprender: Contrastive Divergence

1. Considere um dado v do conjunto de dados D e estimam-se as variáveis ocultas h de acordo com Algoritmo 1.

2. Calcule o produto de " hT e chame isso de gradiente positivo. 3. De h reconstrói-se as variáveis visíveis v’ (Algoritmo 2), e de v’,

reconstrói-se outra vez as escondidas h’T (Algoritmo1) 4. Calcule o produto de "’ e h’T gradiente negativo. 5. # = # + &("ℎ) − "+ℎ+,)6. . = . + & " − "+7. b = 0 + & ℎ − ℎ+

Teorema: Este algoritmo é tal que o W obtido é

Inicialização dos a, b e W

• !"#=log(F(Xi=k)/(1-F(Xi=k))onde F(Xi=k)=Sample.count({i},{k})/Sample.length()ou sejam a frequência nos dados da variável Xi tomar os valores k (note que a expressão em cima simplifica)

• W[i,j]=Uniform[-0.01,0.01] ou W[i,j]=Gauss(0,0.01) onde 0.01 é o desvio padrão.

• b[j]=0 ou b[j]=-4 (para motivar que W seja esparsa)

Como gerar Gaussianasimport java.util.Random;

random gauss = new Random();random unif = new Random();//podem ser inicializadas com um seed

double samplegaussian(double mean, double standdev){return mean+gauss.nextGaussian()*standdev;

}

double unif(){return unif.nextdouble();

}

Entrega da 2ª parte

• Classe GBmachine que estende a classe Bmachine• E(v,h) é calculado da forma Eq. (1) da página 12• O vetor a tem dimensão M e não m• A matriz W tem dimensão M×n e não m × n.

• Algoritmo de aprendizagem: contastive divergence• Interface gráfica

• Ler os dados e gravar a gBmachine num ficheiro• Outra para classificar novos pacientes

• Relatório com 4 páginas

Cotação final

• Sample (1.5 val)• Bmachine e Gbmachine (1.5 val)• Input/output de dados e resultados (2 val)• Algoritmo de aprendizagem e inicialização (3 val)• Aplicações gráficas (1 val)• Relatório minimalista (1 val)

Será entregue uma ficha de autoavaliação a preencher antes de cada oral.