quarta-feira, 18 de março de 2015

Lema de Farkas

Lema de Farkas

Author: Igor dos Santos Montagner
Date: 25/02/2015

O lema de Farkas é parte importante da Teoria de Otimização Convexa pois apresenta uma "alternativa": dados um cone convexo e um ponto \(g \in R^n\), ou \(g\) pertence ao cone ou existe um hiperplano que os separa. Construindo um cone adequado podemos usar este resultado para provar as condições de otimalidade de primeira ordem KKT (que serão alvo do próximo texto).

Definição:

Sejam \(B \in R^{n\times m}, C \in R^{n \times p}\) duas matrizes que contém vetores de \(R^n\) em suas colunas e \(y \in R^m, w \in R^p\). O conjunto \(K\) definido abaixo é um cone convexo.

\[ K = \{ By + Cw | y \geq 0 \} \]

Lema:

Dado um ponto \(g \in R^n\) e um cone convexo \(K\), então somente uma das alternativas abaixo é verdadeira:

  1. \(g \in K\)
  2. Existe \(d \in R^n\) tal que:
    1. \(d^T g < 0\)
    2. \(B^T d \geq 0\)
    3. \(C^T d = 0\)

O interessante da prova do lema é que ela mostra como construir a direção \(d\) que satisfaz estas condições.

Prova:

Primeiro iremos provar que as duas alternativas não podem ocorrer juntas.

Suponha que as duas alternativas valham, ou seja, que \(g \in K\) e existe \(d \in R^n\) que satisfaz as condições acima.

Primeiramente, \(g = By + Cw\) para algum \(y \in R^m, y \geq 0\) e \(w \in R^n\). Logo, \(0 > g^T d = (By + Cw)^T d = y^T B^T d + w^T C^T d\). Porém, como \(C^T d = 0\), isto é igual a

\[ 0 > g^T d = (By + Cw)^T d = y^T B^T d \geq 0, \]

pois \(B^T d \geq 0\) e \(y \geq 0\). Logo, chegamos em uma contradição e as duas condições são disjuntas.

Vamos mostrar agora como construir a direção \(d\) no caso em que \(g \notin K\). Primeiramente, seja \(\hat{s} \in K\) o elemento do cone com menor distância euclidiana até \(g\). Logo, \(\hat{s}\) é a solução do seguinte problema de minimização:

\[ min_{s \in K} ||s - g||_2^2 \]

Definimos então \(d = \hat{s}-g\) e, consequentemente, \(g=\hat{s}-d\).

A direção d em relação a g e s
Figura: A direção d em relação a \(g\) e \(s\).

Condição 1:

Como o valor mínimo da função acima encontra-se em \(\hat{s}\), sabemos que a função \(|| t \hat{s} - g||_2^2\) possui mínimo em \(t=1\), pois \(t \hat{s} \in K, \forall t \geq 0\). Logo,

\[ \frac{||t\hat{s} - g||_2^2}{dt} |_{t=1} = 0 \\ \frac{t^2 \hat{s}^T \hat{s} - 2t\hat{s}^Tg + ||g||_2^2}{dt} |_{t=1} = 0 \\ 2t\hat{s}^T \hat{s} - 2\hat{s}^Tg |_{t=1} = 0 \\ 2\hat{s}^T(t\hat{s} - g)|_{t=1} = 0 \\ \hat{s}^T(\hat{s} - g) = 0 \]

Logo,

\[ d^Tg = d^T(\hat{s}-d) = d^T\hat{s} - d^T d = \\ \hat{s}^T(s - d) - ||d||_2^2 = -||d||_2^2 < 0 \]

Condições 2 e 3:

Para mostrar que \(d\) satisfaz as condições 2 e 3 vamos primeiramente analisar o que acontece quando consideramos, em vez de \(\hat{s}\), \(\hat{s} + \theta(\hat{s} - s), s \in K\).

\[ ||\hat{s} + \theta(\hat{s} - s) - g ||_2^2 \geq ||\hat{s} - g||_2^2 \\ ||\hat{s} - g||_2^2 +2\theta(\hat{s} - g)^T(\hat{s} - s) + \theta^2||\hat{s} - s||_2^2 \geq ||\hat{s} - g||_2^2 \\ 2\theta(\hat{s} - g)^T(\hat{s} - s) + \theta^2||\hat{s} - s||_2^2 \geq 0 \\ 2(\hat{s} - g)^T(\hat{s} - s) + \theta||\hat{s} - s||_2^2 \geq 0 \\ \theta \rightarrow 0 \\ 2(\hat{s} - g)^T(\hat{s} - s) \geq 0 \\ 2(\hat{s} - s)^T(\hat{s} - g) = \hat{s}^T(\hat{s} - g) - s^T(\hat{s} - g) \geq 0 \\ s^T(\hat{s} - g) = d^Ts \geq 0 \forall s \in K \\ \]

Logo, \(d^Ts = d^T(By + Cw) \geq 0, y \geq 0\). Isto vale para todos os \(s \in K\) e, em especial para os casos abaixo:

  1. \(y = 0\), \(d^TCw \geq 0 \rightarrow d^TC = C^T d = 0\)
  2. \(w = 0\), \(d^TBy \geq 0 \rightarrow B^Td \geq 0\), pois \(y \geq 0\).

Portanto, a direção \(d = \hat{s} - g\) satisfaz as propriedades do lema se \(g \notin K\) e tudo está provado :)


quarta-feira, 11 de março de 2015

Teoria de W-operadores - Operações entre imagens

Teoria de W-operadores - Operações entre imagens

\[ \newcommand{\E}[0]{\mathbb{E}} \newcommand{\Z}[0]{\mathbb{Z}} \newcommand{\L}[0]{\mathcal{L}} \newcommand{\P}[0]{\mathcal{P}} \]

Imagens podem ser interpretadas como reticulados e operações entre imagens como operações entre reticulados. Neste texto procuro apresentar a relação os diversos aspectos de teoria de reticulados apresentados anteriormente e o processamento de imagens digitais. Em especial, mostrarei que o operador intervalo produz resultados visualmente intuitivos e como ele pode ser composto para produzir resultados mais complexos.

Imagens como elementos de reticulados

Dados um domínio \(\E \subset \Z^2\) e um intervalo \(K = [0, \dots, k]\), uma imagem em \(k+1\) níveis de cinza pode ser interpretada como um elemento \( I \in Fun[\E, K]\). Em outras palavras, \(I\) atribui para cada ponto do domínio um nível de cinza.

O conjunto \(Fun[\E, K]\) é um reticulado com a operação \(\preccurlyeq\) definida abaixo.

\[ f \preccurlyeq g \Leftrightarrow f(x) \leq g(x) \forall x \in \E \]

De maneira equivalente, uma imagem binária \(B \in Fun[\E, [0,1]]\) também pode ser interpretada como um subconjunto de \(B' \subseteq \E\), onde \(p \in B' \Leftrightarrow B(p) = 1\). Seguindo a interpretação de conjuntos, o reticulado \((\P(\E), \subseteq)\) das imagens binárias é formado pelo conjunto de todos subconjuntos de \(\E\), \(\P(\E)\), e pela relação de inclusão usual em conjuntos \(\subseteq\).

Note que a noção de ordem (parcial) entre imagens é fundamental para a interpretação de imagens como reticulados.

Muitas vezes é interessante selecionar um pequeno recorte da imagem, selecionando os pixels que pertencem à vizinhança, chamada de janela, de um pixel. Estas imagens são chamadas de imagens-janela e são elementos em \(Fun[W, K]\), onde \(W \subset \Z^2\) é um conjunto de pontos que define a vizinhança considerada. A imagem janela \(I_z^{(W)}\) obtida ao centralizar a janela \(W\) no pixel \(z \in \Z^2\) na imagem \(I\) é dada por

\[ I^{(W)}_z(p) = I(z + p) \forall p \in W.\]

Processamento de imagens como uma operação de reticulados

Um operador de imagens é uma função que transforma uma imagem em outra imagem diferente. Logo, um operador \(\Psi\) é um elemento de \(Fun[ Fun[\E, K], Fun[\E, K] ]\) e é tanto uma função entre reticulados quanto um elemento no reticulado dos operadores. Um classe de especial interesse entre os operadores de imagens é a classe dos \(W-\)operadores.

Um operador \(\Psi\) é u \(W-\)operador se ele possui as duas seguintes propriedades:

  1. invariante à translação: \(\Psi(t(I, p)) = t(\Psi(I), p)\), onde \(t(I, p)\) representa a translação da imagem \(I\) por \(p \in \Z^2\);
  2. localmente definido: existe uma janela \(W \in \Z^2\) tal que \(\Psi(I)(p) = \Psi(I_p^{(W)}), \forall I \in Fun[\E, K], p \in \Z^2\).

Todo \(W-\)operador \(\Psi\) pode ser unicamente caracterizado por uma função \(\psi \in Fun[ Fun[W, K], K]\), de maneira que

\[ \Psi(I)(p) = \psi(I_z^{(W)}) \forall I \in Fun[\E, L], p \in \Z^2.\]

Como \(\psi\) é um operador entre um reticulado (\(Fun[W, K]\)) e uma cadeia (\(K\)), \(\psi\) pode ser expresso utilizando a decomposição canônica:

\[\psi(I)(p) = \sum_{y=0}^m \vee \{ \lambda[A,B](I_p^{(W)} : [A,B] \in \textbf{B}_\psi(k) \}.\]

Lembrando que o operador \(\lambda[A,B] \in Fun[ Fun[W, K], \{0, 1\}]\) tem a seguinte forma:

\[ \lambda_{A,B}(I) = \begin{cases} 1 \textrm{, if } I \in [A,B] \\ 0 \textrm{, otherwise. } \end{cases} \]

Por um lado, o operador de imagens \(\Psi\), não importa tão complexo ele seja, pode ser decomposto em uma série de operadores de imagens fundamentais. Por outro lado, qualquer operação de imagens pode ser desenvolvida ou aprendida se for possível determinar quais intervalos devem ser usados para representar o operador.

O operador intervalo em imagens

Nesta seção mostrarei como utilizar operadores intervalo para construir um operador que detecta bordas em imagens binárias como a imagem abaixo.

O operador intervalo é parametrizado por dois extremos \(A\) e \(B\). Todos os pontos cuja imagem janela contem o primeiro e está contida no segundo extremo terão como saída um pixel branco. Para identificar os cantos superiores direitos podemos utilizar os seguintes intervalos:

De maneira similar, os seguintes intervalos podem ser utilizados para detectar os extremos verticais esquerdos das formas:

O mesmo raciocínio pode ser aplicado para os outros cantos e extremos verticais e horizontais, resultando no seguinte conjunto de intervalos:

Veja abaixo o resultado da união dos operadores intervalo acima na imagem de exemplo.

Note que este conjunto de intervalos não é capaz de detectar todas as bordas diagonais, pois elas possuem uma variação maior que as bordas em 90 graus.


segunda-feira, 2 de março de 2015

Teoria de W-operadores - Reticulados e Operadores entre reticulados

\[ \newcommand{\L}[0]{\mathcal{L}} \newcommand{\P}[0]{\mathcal{P}} \]
A revisão de teoria continua, desta vez com aspectos fundamentais do treinamento de \(W-\)operadores. Neste documento irei apresentar algumas definições importantes de reticulados e operadores entre reticulados.

Conjuntos parcialmente ordenados e Reticulados completos

Seja \(\mathcal{L}\) um conjunto e \(\leq\) uma relação binária entre elementos de \(\mathcal{L}\). Se a relação \(\leq\) for:
  1. reflexiva (\(x\leq x \forall x \in \mathcal{L}\));
  2. anti-simétrica (\(x \leq y\) e \(y \leq x\) implica \(x = y\));
  3. transitiva (\(x \leq y\) e \(y \leq z\) implica \(x \leq x\)),
então \((\mathcal{L}, \leq)\) é chamado de conjunto parcialmente ordenado ou poset (de partially ordered set). A relação \(\leq\) é chamada de relação de ordem parcial (pois não requer que todos elementos estejam relacionados).
Sejam \(L, U \in \mathcal{L}\) e \(\Xi \subseteq \mathcal{L}\), então \(L\) e \(U\) são chamados de limite superior e limite inferior de \(\Xi\) se \(X \leq U \forall X \in \Xi\) e \(L \leq X, \forall X \in \Xi\), respectivamente. O menor limitante superior de \(\Xi\), se ele existir, é chamado de supremo. Da mesma maneira, o maior limitante inferior de \(\Xi\) é chamado de ínfimo. Tanto o ínfimo quanto o supremo são únicos, se existirem. O ínfimo e o supremo entre dois elementos \(X\) e \(Y\) são denotados \(X \wedge Y\) e \(X \vee Y\).
Um subconjunto \(\Xi \subseteq \mathcal{L}\) é um intervalo se e somente se existem dois elementos \(A,B \in \mathcal{L}\) tal que
\[ A \leq X \leq B \Leftrightarrow X \in \Xi, \forall X \in \mathcal{L}.\]
Intervalos são denotados por \([A,B]\), sendo que \(A\) é a extremidade esquerda e \(B\) a extremidade direita do intervalo. O conjunto de intervalors \(\{[A,B] : A,B \in \L, A \leq B\}\) junto com a operação \(\preccurlyeq\) é um reticulado completo.
\[ [A,B] \preccurlyeq [A',B'] \Leftrightarrow A \leq A' \textrm{ e } B \leq B' \]
O conjunto \(Max(\{[A,B]\})\) contém todos os intervalos maximais.
Um poset \(\mathcal{L}\) é um reticulado completo se todo subconjunto de \(\L\) possui um ínfimo e um supremo. Reticulados completos sempre possuem um máximo \(I\) e um mínimo \(O\). Quando todos os elementos de um reticulado completo são comparáveis ele é chamado de cadeia.

Operadores entre reticulados

Dados reticulados \(\L_1\) e \(\L_2\), o conjunto \(Fun[\L_1,\L_2]\) contém todas as funções de \(\L_1\) a \(\L_2\). Elementos deste conjunto são chamados de operadores ou mapeamentos. Elementos de \(\L_1\) serão denotados \(A, B\) e \(X\) e elementos de \(\L_2\) serão denotados \(V\) e \(Y\). Operadores serão denotados por letras gregas minúsculas \(\alpha, \beta, \dots\).
Defina \(\lambda_{A,B}\) um operador (chamado de sup-gerador) de \(\L_1\) para \(\{0, 1\}\) da seguinte maneira:
\[ \lambda_{A,B}(X) = \begin{cases} 1 \textrm{, if } X \in [A,B] \\ 0 \textrm{, otherwise } \end{cases} \]
O kernel \(K_\psi \in Fun[L_2, \P(L_1)]\) de um operador \(\psi \in Fun[\L_1, \L_2]\) é dado por
\[ K_\psi(Y) = \{X \in \L_1 : Y \leq \psi(X) \}. \]
Essencialmente, \(K_\psi\) contém, para cada elemento \(Y\) todos os elementos de \(L_1\) que são maiores ou iguais a \(Y\) após a aplicação de \(\psi\).

Teorema (Decomposição Canônica):

Todo operador \(\psi \in Fun[\L_1, \L_2]\) pode ser decomposto em função de operadores sup-geradores:
\[ \psi(X) = \vee \{ Y \in \L_2 : \vee\{\lambda_{A,B}(X) : [A,B] \in K_\psi(Y) \} = 1\}, \forall X \in \L_1 \]
A representação de um operador utilizando a decomposição acima é redundante, pois se \(X \in [A,B]\) e \(X \in [A',B']\) tal que \(A\leq A'\) e \(B\leq B'\) então o intervalo \([A,B]\) é redundante. Desta forma, definimos
\[ \textbf{B}_\psi(Y) = Max(K_\psi(Y)) = \{[A,B] : \nexists [A',B'] \textrm { s.t. } [A,B] \preccurlyeq [A', B']\} \]
e o teorema acima se torna
\[ \psi(X) = \vee \{ Y \in \L_2 : \vee\{\lambda_{A,B}(X) : [A,B] \in \textbf{B}_\psi(Y) \} = 1\}, \forall X \in \L_1 \]
e a representação de \(\psi\) em termos de \(\textbf{B}_\psi\) é chamada de decomposição por um conjunto de operadores sup-geradores.

Caso específico: Operadores entre reticulados e cadeias

Suponha que \(\L_2 = M = [0, m]\). Então o conjunto \(K = \{K_\psi(y) : y \in M\}\) também é uma cadeia em \((\P(\L_1), \subseteq)\) para todo \(\psi \in Fun[\L_1, M]\). Logo, o teorema da decomposição canônica se torna:
\[ \psi(X) = \sum_{y=1}^m \vee \{\lambda_{A,B}(X) : [A,B] \in \textbf{B}_\psi(y)\} \]
Se \(m=1\), o teorema se torna:
\[ \psi(X) = \vee \{\lambda_{A,B}(X) : [A,B] \in \textbf{B}_\psi(1)\} \]

Caso específico II: Imagens

Este outro texto explica o caso específico que interpreta imagens como reticulados e contextualiza a decomposição canônica como uma composição de operações de imagens.