Probabilistic Graphical Models – Semana 2

Março 31, 2012

Depois de escrever/estudar os vídeos das aulas correspondentes à primeira semana, fui fazer os exercícios práticos e teóricos. Aprendi um pouco sobre Octave e conheci a ferramenta SAMIAM, uma interface gráfica para facilitar a manipulação de redes Bayesianas.

CPD’s Estruturados

Um CPD ou distribuição de probabilidade condicional é normalmente representado através de uma tabela, considerando todas as possíveis combinações de valores das variáveis das quais ela depende. Nesse conjunto de aulas são apresentados outros tipos de CPD’s.

Fundamentos

Um conceito importante que será utilizado nas próximas seções é o de independência para contexto específico (tradução livre de context-specific independence). Em alguns casos duas variáveis são independentes apenas se o valor observado de uma outra variável tiver um valor específico.

Um caso simples onde isso acontece é na rede Bayesiana onde uma variável é o OU de duas outras variáveis, conforme a Figura 1. Inicialmente, x1 e x2 são independentes. Porém, se observarmos y, elas deixam de ser. Por outro lado, se y for igual a 0, as variáveis se tornam independentes novamente, pois “independentemente” do valor da outra variável, sabemos que o valor de x1 ou x2 será 0.

Figura 1: OR determinístico

Podemos pensar nesse tipo de independência como um caso especial de independência condicional. Nesta, para que haja independência, deve haver independência para contexto específico para todas as combinações de valores das variáveis observadas.

CPD’s determinísticos

Um exemplo de CPD determinístico foi apresentado na seção anterior. Nesses casos, não precisamos de uma tabela considerando todas as possíveis combinações de resultados, sendo suficiente a função que descreve uma variável a partir de seus pais.

CPD’s com estrutura de árvore

Em casos em que não há independência condicional entre duas variáveis, mas há independência para um contexto específico, podemos usar uma representação de árvore para diminuir o número de combinações possíveis de entradas a serem consideradas.

Figura 2: CPD em forma de árvore

CPD Multiplexador. Usando a estrutura em árvore, podemos construir uma rede que representa um multiplexador, conforme a Figura 3. A variável A pode assumir valores de 1 a k, enquanto Y pode assumir os valores Z_1 a Z_k. Se a é o valor de A, e y o valor de Y, então y = Z_a. O CPD para Y que modela o multiplexador é simples: P(Y = X_a | A = a) = 1 e P(Y = X_a | A \neq a) = 0 para todo 1 \le a \le k.

Figura 3: Multiplexador

CPD OU ruidoso

Uma generalização do CPD determinístico é o CPD ruidoso (noisy). Um modelo onde esse CPD aparece é quando uma variável Y possui diversas causas X_1, \cdots, X_k e estas podem causar Y de maneira independente. Nesse caso, adicionamos uma “camada” de variáveis Z_1, \cdots, Z_k, onde Z_k é binária, sendo 1 se e somente se, a variável X_k causa Y. Esse novo conjunto de variáveis representa a transmissão de ruídos representados pelo conjunto de variáveis X, por isso o nome.

Também usamos a variável Z_0 para modelar o fato de que Y pode ser causada por outro meio além das variáveis X. Neste modelo, fazemos Y ser um OU determinístico de Z_0, \cdots, Z_k, conforme a Figura 4.

Figura 4: CPD OR ruidoso

Os CPD’s das variáveis Z_k para k > 0 são P(Z_k = 1 | X_k = 0) = 0 e P(Z_k = 1 | X_k = 1) = \lambda_k se X_k = 1, ou seja, podemos ler \lambda_k como a probabilidade da variável X_k causar Y. Para k = 0, P(Z_0 = 1) = \lambda_0.

Assim, é possível escrever o CPD de Y em função de X_1, \cdots, X_k. Temos que

P(Y = 0 | X_1, \cdots, X_k) = (1 - \lambda_0) \prod_{i | X_i = 1} (1 - \lambda_i).

CPD’s para o caso contínuo

Se uma dada variável Y depende de outra variável contínua X, é impossível tabelar todos os possíveis valores de X. Nesse caso, podemos definir Y como uma função de distribuição de probabilidade tendo X como parâmetro.

Um exemplo é usar a distribuiçãoa gaussiana para Y, com a média sendo o valor observado de X e uma variância fixa, ou seja Y \sim \mathcal{N}(X, \sigma^2).

Se Y depende de mais variáveis contínuas, podemos por exemplo usar algum tipo de combinação entre os valores observados para definir a média. Se Y também depende de uma variável discreta, podemos ter um CPD misto, onde as variáveis discretas definem as linhas da tabela e em cada linha existe uma distribuição com diferentes parâmetros.


Redes de Markov

Redes de Markov são representadas por um grafo não direcionado.

Redes de Markov por pares

Redes de Markov por pares. são um caso especial de redes de Markov, onde as relações entre variáveis são sempre entre pares e por isso podemos representá-las através de um grafo não direcionado.

Ao invés de definir fatores sobre os vértices como no caso das redes Bayesianas, definimos sobre as arestas. Nesse contexto, esses fatores são chamados de funções de compatibilidade ou funções afim.

As entradas de um fator entre duas variáveis X_i, X_j, o qual denotamos por \phi(X_i, X_j) , são as possíveis combinações dos valores das variáveis envolvidas.

Fazendo o produto dos fatores do grafo, obtemos \tilde P(X_1, \cdots, X_k) = \prod_{(X_i, X_j) \in E} \phi(X_i, X_j), que é uma medida não normalizada. Seja Z a constante de normalização (também conhecida como função de partição, termo herdado da físisca estatistica), então podemos definir a função de distribuição de probabilidade:

P(X_1, \cdots, X_k) = \tilde P(X_1, \cdots, X_k)/Z

Uma observação é que não há uma correspondência intuitiva entre os fatores e a distribuição de probabilidade P para redes de Markov ao contrário de redes Bayesianas.

Esse modelo não é muito expressivo. Para se ter uma ideia, considere um conjunto de n variáveis com d possíveis valores cada. Mesmo que tenhamos um grafo completo, com O(n^2) arestas e cada uma tendo O(d^2) entradas, a função de distribuição terá O(n^2d^2) entradas, ao passo que poderíamos ter uma com O(d^n).

Distribuição geral de Gibbs

A fraqueza do modelo anterior está na restrição de fatores com apenas duas variáveis. Para remediar isso, podemos usar a distribuição geral de Gibbs, que é uma generalização de redes de Markov por pares. Nesse caso, as arestas podem ser incidentes a mais de dois vértices, como num hipergrafo.

Mais formalmente, temos um conjunto de fatores \Phi = \{\phi_1(D_1), \cdots, \phi_k(D_k)\} onde D_i é o conjunto de variáveis incluídas no fator \phi_i, e é chamada de domínio. A distribuição geral de Gibbs corresponde ao produto de fatores em \Phi normalizado.

Rede de Markov induzida. denotada por H_{\Phi}, é uma rede de Markov por pares com conjunto de vértices correspondente à união dos domínios dos fatores em \Phi e existe uma aresta entre duas variáveis X_i e X_j se X_i, X_j \in D_i para algum \phi_i \in \Phi.

Com isso, podemos apresentar a definição de fatoração para redes de Markov.

Fatoração. Uma distribuição de probabilidade P fatora uma rede de Markov H se existe um conjunto de fatores \Phi = \{\phi_1(D_1), \cdots, \phi(D_k)\} tal que

(1) P = P_{\Phi}
(2) H é o grafo induzido de \Phi.

Note que há perda de informação quando representamos os fatores por uma rede de Markov induzida e portanto não conseguimos recuperar \Phi a partir de H_\Phi.

Entretanto, a relação de influência entre variáveis para uma distribuição de Gibbs pode ser representada por H_\Phi. Para isso, definimos o análogo de caminho ativo como sendo um caminho neste grafo sem nenhuma variável observada. Assim, dizemos que uma variável influencia a outra se existe algum caminho ativo entre elas.

Campos condicionais aleatórios

Campos condicionais aleatórios ou CRF (Conditional Random Field) são semelhantes a uma distribuição de Gibbs, exceto que a normalização é feita de modo diferente. Nesse caso, temos um conjunto de variáveis observadas X e calculamos a constante de normalização somando apenas para as entradas onde X tem o valor observado. A distribuição obtida depois da normalização é condicionada pelo valor das variáveis observadas X.

Mais formalmente, dado o produto de fatores não normalizado:

\tilde P_{\Phi}(X, Y) = \prod_{i =1}^{k} \phi_i(D_i)

A constante de normalização para uma dada observação de X é igual a

Z_{\Phi}(X) = \sum_{Y} \tilde P_{\Phi}(X, Y)

Dessa forma, temos uma distribuição condicional:

P_{\Phi}(Y | X) = \dfrac{\tilde P_{\Phi}(X, Y)}{Z_{\Phi}(X)}

Modelo logístico. (Logistic model ou Logistic regression) é um caso particular do CRF, onde temos uma variável Y conectada a um conjunto de variáveis X_1, \cdots, X_k.

O fator de cada (Y, X_i) é dado por

\phi(X_i, Y) = \exp(w_i 1\{X_i = 1, Y = 1\})

onde 1\{X_i = 1, Y = 1\} é uma função indicador, que retorna 1 se e somente se as variáveis possuem os valores indicados. Nesse caso, o produto dos fatores é:

\tilde P(Y, X) = \exp\{\sum_i (w_i X_i Y)\}

Discriminando por valores, a distribuição de probabilidade de Y = 1 dado X é dada por

P(Y = 1|X) = \dfrac{\tilde P(Y = 1, X)}{\tilde P(Y = 1, X) + \tilde P(Y = 0, X)}

Sendo \tilde P(Y = 0, X) = 1 e \tilde P(Y = 1, X) = \exp\{\sum_i (w_i X_i)\}

Independência em redes de Markov

Na mesma forma que temos a d-separação em redes Bayesianas, temos a separação entre duas variáveis X e Y em uma rede de Markov H dado Z, denotada por \mbox{sep}_H(X, Y | Z), que ocorre quando não existe nenhum caminho ativo entre elas dado Z.

Lema 1. Se P fatora uma rede de Markov H e \mbox{sep}_H(X, Y | Z), então P \models (X \perp Y | Z).

Da mesma forma que para redes Bayesianas, podemos definir o conjunto de independências condicionais sobre H como

I(H) = \{(X \perp Y | Z) : \mbox{sep}_H(X, Y | Z) \}

Se P satisfaz todas as independências de I(H), dizemos que H é um I-mapa (mapa de independência) de P. Logo, usando o Lema 1, temos

Teorema. P fatora uma rede de Markov H, então H é um I-mapa de P.

Inversamente, temos um resultado quase simétrico:

Teorema de Hammersley Clifford. Dada uma distribuição positiva P, se H é um I-mapa de P, então P fatora H.

I-mapas e mapas perfeitos

Nota: essa seção diz respeito a ambas redes Bayesianas e de Markov.

Podemos definir um conjunto de independências condicionais sobre P (ao invés de um grafo) como

I(P) = \{(X \perp Y | Z) : P \models (X, Y | Z) \}

Note que se P fatora uma rede G, então I(G) \subseteq I(P), mas o contrário não é verdade.

Um grafo mais esparso tende a conter mais independências e portanto representar mais precisamente as independências de P. Para isso, podemos remover arestas redundantes até obter um I-mapa minimal, ou seja, um grafo para o qual não existe aresta (X,Y) tal que E(G) \setminus (X, Y) é um I-mapa.

Idealmente, gostaríamos de encontrar um grafo tal que I(G) = I(P), caracterizando um I-mapa perfeito, mas nem toda distribuição admite tal mapa. Também temos o caso de que uma distribuição admite um I-mapa perfeito usando redes Bayesianas (grafo direcionado), mas não usando redes de Markov (grafo não-direcionado). Um exemplo simples é a estrutura em V.

O contrário também pode acontecer. Não é possível capturar exatamente as independências de uma rede de Markov como a da Figura 5, no caso (A \perp C | B, D) e (B \perp D | A, C).

Figura 5: Loop

Uma última definição: Dois grafos G_1 e G_2 são ditos I-equivalentes de I(G_1) = I(G_2).

Modelos Log-Linear

Esses modelos possuem a seguinte forma,

\tilde P = \exp(-\sum_j w_j f_j(D_j)),

onde w_j são chamados coefiecientes e f_j() características (features), com um domínio D_j, que é um conjunto de variáveis.

Esse modelo é bastante expressivo, de movo que podemos representar fatores com ele. Se por exemplo o fator \phi tem como domínio duas variáveis X e Y, tal que \phi(X = x_i, Y = y_j) = \sigma_{ij}, usamos uma função indicador para definir a função característica f_{ij} = 1(X = x_i, Y  = y_i) e coeficiente w_{ij} = \ln(\sigma_{ij}).

Mas o interessante é que podemos modelar apenas valores de variáveis que são relacionados (usando tabelas, teríamos várias entradas com valor 0), como no caso de processamento de linguagem natural. Podemos definir uma característica que retorna 1 se e somente se uma palavra começar com letra maiúscula e o rótulo for pessoa. O coeficiente correspondente captura a correlação entre esses dois valores.

Anúncios

Probabilistic Graphical Models – Semana 1

Março 18, 2012

Amanhã coemçam as aulas do Probabilistic Graphical Models. Vou usar o blog para registrar e organizar minhas anotações sobre o curso.

Segundo o calendário serão 10 semanas de aulas, com exercícios teóricos e práticos, além de uma prova final no começo de Junho.

Como a recomendação é dedicar de 10 a 15 horas semanais para estudo e provavelmente só conseguirei estudar aos finais de semana, decidi não fazer o curso de processamento de linguagem natural.

Como o material da primeira semana já está disponível, decidi me adiantar.

Revisão

Na série de vídeos “Introduction and Overview” são apresentados o conceito do PGM e suas aplicacões e são revisados conceitos básicos de probabilidade como funções de distribuição de probabilidade, variáveis aleatórias, probabilidade condicional.

São introduzidas definições que eu não conhecia: fatores (factors), que são funções que recebem como entrada todas as combinações dos valores de um conjunto de variáveis aleatórias e retornam um escalar. Esse conjunto é denominado escopo (scope).

Podemos pensar em fatores como sendo tabelas. Isso torna mais fácil entender a definição das três operações apresentadas sobre fatores: produto de fatores, marginalização de fatores e redução de fatores.

O produto de dois fatores A e B é um fator C cujo escopo é a união dos escopos de A e B. O valor retornado por C para uma dada entrada i é dado pela multiplicação dos valores retornados por A e B para as entradas que são subconjuntos de i.

A marginalização de um fator A consiste em gerar um fator A’ com um subconjunto do escopo de A. O valor de uma entrada i’ para A’ é dado somando-se os valores das entradas de A das quais i’ é subconjunto.

A redução de um fator A é um fator A’ com o valor de algumas das variáveis do domínio de A fixas. O valor da entrada i’ para A’ corresponde ao valor obtido de uma entrada de A correspondente a i’ mais os valores fixados. Parece uma generalização da distribuição de probabilidade condicional.


Redes Bayesianas

Uma rede bayesiana é um grafo direcionado acíclico (DAG). Os vértices são as variáveis aleatórias e existe uma aresta (u, v) se a variável aleatória v depende de u. Associado a cada vértice temos uma distribuição de probabilidade condicional (CPD).

Regra da cadeia para redes bayesianas. A regra da cadeia é utilizada para calcular a distribuição de probabilidade conjunta (joint probability distribution), ou seja, uma distribuição de probabilidade considerando todas as variáveis aleatórias da rede. Basicamente, o que a regra diz é esta distribuição pode ser obtida multiplicando-se os CPD’s usando produto de fatores.

Se uma distribuição P é obtida via multiplicação dos CPD’s dos vértices de uma rede bayesiana G, dizemos que P fatora (factorizes) G.

Note que dada a distribuição de probabilidade conjunto, podemos determinar a probabilidade de cada nó via marginalização.

Padrões de inferência

Inferência ocorre quando observamos (ou seja,fixamos o valor de) uma variável aleatória X e isso afeta a distribuição de probabilidade de outra variável Y. Em uma rede bayesiana, podemos classificar inferências de acordo com a relação entre as variáveis X e Y no grafo.

Inferência causal (causal reasoning) é quando a variável X observada é ancestral da variável Y.

Inferência probatória (evidential reasoning – tradução correta?) é quando a variável X é descendente da variável Y.

Inferência intercausal (intercausal reasoning) é quando as variáveis X e Y não estão conectadas por um caminho direcionado.

Fluxo de influência

Dizemos que existe um fluxo de influência de uma variável X para Y, se a observação de X influencia a distribuição de probabilidade de Y. Esse fluxo depende também de quais outras variáveis da rede além de X são observadas. Nos referimos então a conjunto de evidências como o conjunto das variáveis da rede observadas e que chamaremos de Z.

O fluxo de influência é representado por um caminho (não necessariamente direcionado) no grafo, o qual é chamado de caminho ativo (active trail). Sejam X, W e Y variáveis correspondendo a vértices consecutivos em um caminho. As possíveis relações entre elas são:

  1. X \rightarrow W \rightarrow Y
  2. X \leftarrow W \leftarrow Y
  3. X \leftarrow W \rightarrow Y
  4. X \rightarrow W \leftarrow Y

Vamos apresentar as condições em que há passagem de fluxo por X, W e Y. Para o caso 1, 2 e 3, temos passagem de fluxo se e somente se W não está em Z. Intuitivamente, se W é observado, ele mesmo exercerá influência daqui pra frente no caminho.

O caso mais contra-intuitivo é o caso 4, que é conhecido como estrutura em V. Em geral, se sabemos alguma coisa sobre X, isso não afeta nosso conhecimento sobre Y. Porém, se sabemos algo sobre W, um conhecimento sobre X, pode afetar o conhecimento sobre Y.

Um bom exemplo é dado no final da aula “Reasoning Patterns“. É dada a estrutura da Figura 1, onde y = x1 | x2. Se soubermos o valor de y, saber o valor de x1 vai alterar a probabilidade do valor de x2.

Figura 1: Rede bayesiana para um or

Assim, a regra para o caso 4 é que W e/ou algum de seus ancestrais estejam em Z. Finalmente, um caminho cujas triplas de vértices consecutivos respeitem as condições de fluxo, é um caminho ativo.

Independência

Independência condicional. Quando duas variáveis aleatórias X e Y são independentes para uma distribuição P, dizemos que P satisfaz X independente de Y, ou que P \models X \perp Y (latex: P \models X \perp Y). A independência entre X e Y dada a observação de uma variável Z é representada por (X \perp Y | Z) e caracteriza a indepndência condicional.

d-separação. Em uma rede bayesiana G, se não existe nenhum caminho ativo entre X e Y dado um conjunto de evidências Z, dizemos que há uma d-separação entre X e Y dado Z em G, ou de maneira mais compacta d\mbox{-}sep_G(X, Y | Z).

Mapa de independências. Seja I(G) o conjunto de independências condicionais (X, Y| Z) correspondentes a d-separações de G, para todo X, Y e Z. Se P satisfaz todas as indpendências em I(G), dizemos que G é um mapa de independências de P.

Dadas essas definições, temos o seguinte teorema:

Teorema: G é um mapa de indepências para P se, e somente se, P é uma fatoração sobre G.

Com esse teorema, temos dois modos de enxergar uma rede bayesiana: como fatores (CPD’s dos vértices) de uma distribuição P ou como um conjunto de independências que P deve satisfazer.

Bayes Ingênuo

Uma classe especial de redes bayesianas é o bayes ingênuo (naïve bayes), em que temos um nó com vários descendentes, conforme a Figura 2.

Figura 2: Bayes ingênuo

Essa estrutura é usada para casos simples de classificação. Os nós filhos são características e a raíz é uma variável aleatória correspondendo à classe. Assim, dada uma observação das características, deseja-se saber qual a classe mais provável.

Há dois tipos comuns de classificadores bayesianos ingênuos, que são o de Bernoulli, onde as características assumem valor binário e o multinomial onde elas podem assumir múltiplos valores.

Note que este modelo implica na independências entre as características dada a classe. Essa suposição pode ser muito simplista se as características do problema tiverem alta correlação.


Modelos Templates

Modelos templates visam representam de maneira genérica estruturas que se repetem. Com isso o modelo fica mais compacto e permite o re-uso em problemas com estruturas semelhantes.

Modelos Temporais

Há problemas que devem ser modelados considerando a passagem do tempo. Em geral discretizamos o tempo em pedaços de tamanho fixo e criamos variáveis aleatórias associadas a cada pedaço. Nesse caso costuma-se representar a variável por X^{(t)} e um conjunto de variáveis correspondendo a um intervalo t a t’ por: X^{(t:t')} = \{ X^{(t)}, \cdots, X^{(t')} \}.

Para simplificar modelos temporais, podemos fazer as seguintes suposições:

Suposição de Markov. diz que uma variável do instante de tempo t só depende do instante t-1, ou em termos matemáticos: (X^{(t+1)} \perp X^{(0:t-1)} | X^{(t)}).

Invariância em relação ao tempo, que supõe que as distribuições de probabilidade condicionais P(X^{(t+1)} | X^{(t)}) são as mesmas para todo t.

2TBN (2-time-slice Bayesian Network) é um modelo de transição entre dois fragmentos de tempo. Ele define um pedaço de rede bayesiana representando a transição de um conjunto de variáveis X_1, \cdots X_n para outro X'_1, \cdots X'_n no próximo instante de tempo. Nesse modelo, só o segundo conjunto de variáveis possuem CPD e este modelo define uma distribuição de probabilidade condicional conjunta para X'_1, \cdots X'_n.

Rede bayesiana dinâmica ou DBN (Dynamic bayesian network) consiste de uma rede que representa o estado inicial e um 2TBN representando a transição temporal. A expansão dessa rede, ou seja, a replicação do 2TBN para os instantes de tempo subsequentes forma a rede bayesiana espandida (ground bayesian network, que não sei traduzir).

Modelo de Markov Oculto

Também chamado de HMM (Hidden Markov Model) é um tipo de DBN que usa uma versão do 2TBN simplificado em que temos apenas uma variável S que muda ao longo do tempo e uma variável interna de observação, conforme a Figura 3.

Figura 3: 2TBN simplificado

Além disso, as possibilidades de transição de um estado para outro de S são limitadas. No exemplo da Figura 4, não podemos ir do estado s_1 para o estado s_3 ou s_4.

Figura 4: Transição limitada

Modelo de Placa

É um modelo que visa fatorar partes comum a vários elementos. A parte fatorada pode ser um CPD comum a todos os nós ou mesmo uma variável que está conectada a várias outras, como por exemplo a dificuldade de um curso estar ligada a todos os alunos desse curso.

A parte fatorada é representada fora da placa e os objetos que se repetem ficam dentro. A placa em si é desenhada através de um retângulo. É possível aninhar e também fazer sobreposição de placas.

Define-se uma variável template como um conjunto de variáveis aleatórias compartilhando uma certa propriedade. Uma limitação desse modelo é que os pais de uma variável template que engloba um conjunto U de variáveis, só podem englobar um subconjunto de U.


Relaxação Lagrangeana – Prática

Março 11, 2012

Em um post anterior, expliquei brevemente o conceito de relaxações, focando em relaxação lagrangeana. Hoje vamos apresentar uma heurística que encontra multiplicadores lagrangeanos.

Aplicaremos o algoritmo no problema da localização de instalações.

Algoritmo

O algoritmo mais conhecido para encontrar bons multiplicadores lagrangeanos é dado por Beasley [1], e é conhecido por método do subgradiente.

Geometricamente, se tivéssemos dois multiplicadores lagrangeanos, estes representariam pontos em um plano e os valores das soluções ótimas do dual lagrangeano para um desses pontos (multiplicadores) formariam curvas de níveis. O que o algoritmo faz é procurar um ponto com o valor mais próximo do da solução ótima primal e para isso anda em uma direção (gradiente) em que há melhoria dessa função.

Se não houver melhoras por um longo tempo, pode ser que o “passo” que estamos dando a cada iteração esteja muito grande e pode ser que haja uma solução melhor do meio desse passo. Por isso, vamos diminuímos gradativamente o passo, até que eventualmente este fique menor que um tamanho mínimo.

Onde a função Atualiza_multiplicadores é dada por:

Neste algoritmo é usado o valor de uma solução primal, que é obtida a partir da relaxação através de uma heurística.

Aplicação ao problema da Localização de Instalações

Vamos usar a relaxação das desigualdades que forçam os clientes a serem cobertos por pelo menos uma instalação (como descrito em um post anterior).

Heurística lagrangeana. Como estamos trabalhando com a versão sem restrição de capacidade, dado um conjunto de fábricas abertas é trivial encontrar a solução de melhor custo, bastando ligar cada cliente à instalação aberta mais barata. É essa heurística que usaremos para obter uma solução primal a partir de uma solução relaxada.

Multiplicadores lagrangeanos. Note que o algoritmo requer um conjunto de multiplicadores lagrangeanos inicial. No nosso caso, fizemos u_i = \frac{1}{n}, onde n é o número de desigualdades relaxadas.

Para os outros parâmetros do algoritmo usamos: \pi = 2, T_\pi = 0.2 e N_{stuck} = 30.

Fiz uma implementação em C++, tentado separar o problema (classe FacilityLocation implementando a classe virtual LagrangeanModel) do algoritmo (classe GradientMethod). Como de costume, o código está no github.

Resultados computacionais

Para testar o algoritmo, usei as instâncias do problema Capacitated Facility Location da OR-Library [3]. Como estamos lidando com a versão não restrita (uncapacitated), ignorei os dados de capacidade.

Há também este arquivo com os valores ótimos das soluções de forma que podemos observar a qualidade das soluções obtidas via relaxação empiricamente. A tabela a seguir contém o nome da instância, o número de instalações, o número de clientes, a distância percentual entre o ótimo e o melhor valor primal obtido (Gap), a distância percentual entre os melhores valores valores primal e dual (Gap DP) e finalmente o tempo.

Observamos que a solução ótima foi encontrada para boa parte das instâncias. O pior resultado foi para a instância capb, devido à dificuldade do algoritmo em encontrar bons multiplicadores lagrangeanos (note a distância entre os valores primal e dual).

Note que mesmo para instâncias grandes, provavelmente inviáveis de serem resolvidas de maneira exata, são resolvidas em menos de 6 segundos (processador i7 2.2GHz, sem paralelismo).

Conclusão

Embora tenhamos que lidar com uma formulação do problema para decidir quais restrições relaxar e obter o problema relaxado, geralmente para resolvê-lo não precisamos trabalhar com a formulação explicitamente (em geral resolver PL’s, principalmente de formulações grandes, não é muito rápido). Assim, dependendo da complexidade do problema resultante, a relaxação lagrangeana pode ser bastante eficiente.

Vimos que na prática as soluções obtidas via heurística lagrangeana podem ser muito boas. O principal problema é que a escolha dos parâmetros podem influenciar bastante a qualidade dessas soluções.

Eu já havia feito um trabalho sobre relaxação lagrangeana durante uma disciplina na faculdade, sobre um problema chamado Axis Parallel Minimum Stabbing Number Spanning Tree [2].

Referências

[1] J. E. Beasley – Modern Heuristics for Combinatorial Optmization Problem, Chapter 6 (Lagrangean Relaxation). Blackwell Scientific Publications, 1993.
[2] Relatório Programação Linear Inteira (MO420) – Guilherme Kunigami
[3] OR-Library


Kindle

Março 4, 2012

Faz algum tempo já que comprei um Kindle da Amazon. Embora não leia com muita frequência, das vezes que precisei (longas esperas em aeroportos, dentro do avião), ele foi uma aquisição útil.

Nesse post vou comentar minhas impressões e registrar respostas para dúvidas que tive ao comprar o aparelho.

Vantagens

A principal vantagem de um leitor como o Kindle sobre tablets é o uso do e-ink. Por causa dessa tecnologia o Kindle não precisa de luz para exibir o texto, mas por outro lado é necessário luz ambiente para poder usá-lo, da mesma forma que um livro de papel. Isso permite um maior tempo de leitura sem que a vista fique cansada.

O aparelho possui uma película protetora fosca para reduzir o reflexo. Entretanto, ainda acho um pouco incômodo quando há uma fonte de luz muito próxima incidindo diretamente na tela, como por exemplo uma luminária de mesa ou mesmo as lâmpadas dos aviões.

Outra grande vantagem do uso do e-ink é a duração da bateria. Se o wi-fi estiver desabilitado, um Kindle pode ficar mais de um mês sem recarregar.

Formatos aceitos

O Kindle possui um formato próprio, o .azw, enquanto o formato padrão dos livros não comprados pela Amazon é o .mobi, que também é aceito, além do .txt.

Ele aceita arquivos .pdf também, mas minha experiência não é muito boa com a versão de 6 polegadas. Como o Kindle não reconhece o texto do pdf, o melhor que ele pode fazer é diminuir a escala para a página caber na pequena tela. Outra possibilidade é manter o tamanho original, mas aí provavelmente será preciso scroll horizontal (mesmo visualizando no modo paisagem), o que dificulta o fluxo de leitura. Talvez com a versão DX, de 9.7 polegadas em modo paisagem esse problema seja evitado.

Rede Wi-fi

O Kindle usa wi-fi para baixar os livros armazenados na Amazon. Existe um navegador embutido onde é possível acessar alguns sites como Wikipedia e também fazer compras diretamente pelo site da Amazon. Existem versões que usam 3G.

É possível ainda fazer a transferência de arquivos por um cabo USB.

Funcionalidades

Além do navegador, existem algumas funcionalidades do software embutido no Kindle:

* Dicionário – procura o significado de uma palavra no dicionário simplesmente posicionando o cursor sobre a mesma (o dicionário inglês já vem instalado, mas é possível instalar dicionários em outras línguas);

* Conversor de texto para voz: funciona com quase qualquer formato no qual o Kindle seja capaz de reconhecer as palavras (por exemplo .txt, mas não .pdf). O som fica “robotizado”, mas não dá pra fazer milagre com um conversos automático;

Livros

Existem muitos títulos disponíveis gratuitamente na internet, principalmente aqueles mais antigos. Outra possibilidade é baixar textos na web longos demais para se ler em um computador. Alguns aplicativos como o instapaper fazem um trabalho razoável em converter em formato aceito pelo Kindle.

Adquirir livros pela Amazon é bem simples. A principal dificuldade para estrangeiros é a necessidade de um cartão internacional. Descobri que a Amazon também aceita cartões pré-pagos internacionais, como o travel money, que é uma opção mais segura.

Os livros comprados ficam armazenados na nuvem associados à sua conta, então você pode trocar de aparelho ou ler os livros no aplicativo Kindle para computador sem ter que adquirir novas cópias.

Leitura adicional

[1] Garota sem fio – Review Kindle