[f41657]: INTROD.tex Maximize Restore History

Download this file

INTROD.tex    279 lines (228 with data), 27.1 kB

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
\chapter{Introdução}\label{pan}
Até os dias de hoje muito se tem estudado sobre a representação de objetos ou sistemas físicos e a questão relacionada referente à redução da dimensionalidade da representação. Neste último caso, podemos dizer de maneira simplificada que o que se quer é descobrir informações, padrões, ou estruturas significativas de dados mergulhados em espaços de altas dimensões que utilizem poucos parâmetros. Vê-se que esta questão continuará a ser central no desenvolvimento científico devido ao crescimento
da captação de dados numa sociedade cada vez mais digitalizada e da oportunidade e necessidade utilizá-los.
Em termos gerais o objetivo desta tese \'e investigar e avançar técnicas
recentes para a redu\cao\
de dimensionalidade de dados no contexto aplicado de modelagem computacional,
em especial o reconhecimento de padrões e o problema relacionado de
reconstru\cao\ a partir de poucos parâmetros.
Os dados que representam objetos, estados de sistemas físicos ou evolução nos
mesmos podem ser de alta dimensão. Por exemplo, quando se trata de imagens
podemos ter fotos com $1000 \times 1000$ píxeis ($10^6$ dimensões), ou de ordem
de grandeza ainda maior como fotos de alta resolução e vídeos. Outros exemplos podem ser encontrados nas distribuições genéticas humanas, nos padrões de clima global, na física, na química, nas redes sociais, na estatística de modo geral, dentre
outros~\cite{ghodsi2006dimensionality,borges2006reduccao,varini2006visual,carreira1997review}.
Várias técnicas têm sido estudadas com o intuito de diminuir a dimensão das representações de objetos ou sistemas físicos de modo a facilitar a leitura e interpretação dos dados ou dos modelos.
%
Diversos campos da pesquisa atual, como aprendizagem de máquina (\emph{machine learning}), análise de dados estatísticos, bio-informática, só para citar alguns exemplos, têm se dedicado a este tipo de
estudo~\cite{guyon2006feature,ihler2003nonlinear,ShaSaulMachineLearning2005,raymer2000dimensionality}.
Muitos algoritmos são desenvolvidos com o intuito de aprimorar as técnicas de redução de dimensionalidade já existentes e utilizá-los no reconhecimento e reconstrução de sinais.
De um modo geral os algoritmos de redução de dimensionalidade querem resolver o problema, muito vagamente definido neste momento, que consiste em:
Dados \emph{n} pontos de $\re^d,$ $X^1,X^2, \ldots , X^n,$ achar \emph{n} pontos de $\re^k,$ $Y^1,Y^2,\ldots , Y^n,$ tais que cada $Y^i$ “represente” o correspondente $X^i,$ com \emph{k}, de preferência, muito menor que \emph{d} % quando possível,
(pois estamos querendo reduzir a dimensionalidade dos dados) preservando tanto quanto possível a inter-relação dos pontos no novo conjunto, consoante a inter-relação existente no conjunto original.
Diz-se que $\re^d,$ ou um seu subconjunto (por vezes uma subvariedade), é o
\textit{conjunto de dados} e que $\re^k$ é o \textit{conjunto das
características} (\textit{features}) dos dados, e o mapeamento dos dados às suas
características chama-se de \textit{cálculo das características} ou das
\textit{features}. Dessa forma, pode-se dizer que métodos de redução de
dimensionalidade calculam \textit{features} baseando-se no conjunto de dados.
Em outras palavras, as \emph{features} fornecidas são \emph{data-driven}, no
sentido de que foram automaticamente ``aprendidas'' dos dados.
No espaço das {\em features}, de menor dimensão, teremos mais facilidade em analisar os dados e, se for o caso,
poderemos agrupá-los de acordo com as características que forem de interesse. Estes agrupamentos são conhecidos como
\emph{clusters} e estão intimamente ligados ao processo de redução de dimensionalidade uma vez que alguns algoritmos,
ao reduzir, automaticamente agrupam as imagens de acordo com alguma propriedade que esteja sendo preservada. Pode-se
dizer que clusterização e redução de dimensionalidade são duas faces da mesma moeda \cite{belkin2003laplacian}.
%Podemos classificar de modo geral estas técnicas como lineares ou não-lineares.
A seguir faremos um breve histórico das técnicas de redução de dimensionalidade mais comumente utilizadas nos últimos tempos e depois comentamos as contribui\coes\
da tese.
%e apresentamos os objetivos e a organização desta tese.
\section{Um panorama da situação}\label{sec1pan}
Começamos por uma poderosa técnica para extrair estruturas de um
conjunto de dados de alta dimensão, o método clássico da análise das componentes
principais (\textit{Principal Components Analysis} - PCA)\cite{smith2002tutorial} pode ser classificado
como linear embora muitas adaptações estejam sendo feitas no sentido de torná-lo também aplicável aos
casos não lineares, nomeadamente o kernel PCA, KPCA\cite{scholkopf1998nonlinear}. % Schölkopf et al (1998).
%
%
O PCA é essencialmente, após uma translação dos dados, uma transformação ortogonal
do sistema de coordenadas onde estão nossos dados, seguida duma projeção ortogonal.
As novas coordenadas podem descrever os dados em dimensão reduzida. As dire\coes\ principais do conjunto de dados
correspondem à base do subespaço sobre o qual os mesmos são projetados e são ordenadas segundo um critério de
relevância na sua capacidade explicativa dos dados, e as componentes principais de um dado correspondem aos coeficientes
da proje\cao\ na base das dire\coes\ principais.
% Em muitos casos um número pequeno destas componentes, as quais definem a referida projeção, é o suficiente para descrever o conjunto de entrada de maneira satisfatória.
%Em \cite{Socher2008} vemos um exemplo que mostra que
É conhecido que o método do PCA pode não lidar bem com dados cujo conjunto
apresenta uma estrutura não-linear complexa~\cite{Socher2008}. Exemplos são
fornecidos a seguir e no próximo capítulo,
como motivação para a busca de métodos não-lineares, também
conhecidos como métodos de aprendizagem de variedades (\emph{manifold
learning}). Nesses métodos,
% Peguei este parágrafo na pág. 6
assume-se que o conjunto de dados é uma amostra representativa de uma população
ou conjunto ideal de dados, o qual constitui (ou é contido em) uma variedade no sentido matemático (possivelmente em várias componentes conexas). Neste exemplo que aqui é apresentado na Figura \ref{pcaespiral}, a espiral seria o conjunto ideal de dados (uma variedade diferenciável de dimensão $1$ imersa em $\re^2),$ e os pontos representados seriam os dados, uma amostra representativa do conjunto ideal (neste caso uma amostra uniforme da espiral).
Tais dados ocorrem corriqueiramente no sensoriamento de fenômenos regidos por parâmetros contínuos. Vale notar que, mesmo para dados que não são explicitamente provenientes de fenômenos contínuos, pode-se ainda usar as técnicas não lineares como ferramentas de modelagem em diferentes graus de aproximação.
Ilustramos em seguida, neste exemplo elementar, a dificuldade do PCA com conjuntos não lineares de dados.
Plotamos num mesmo gráfico, na Figura \ref{pcaespiral}, uma espiral (uma sub-variedade não-linear unidimensional) como conjunto de dados iniciais em $2$ dimensões e sua imagem na primeira direção principal. A figura nos ajuda a ver que o PCA funciona como uma projeção na direção de maior variância dos dados. Note que as cores que estão na direção ortogonal a esta primeira direção principal estão misturadas sobre a reta principalmente no centro onde mais camadas da espiral estão sobrepostas. Podemos ver pela figura que dados próximos são mapeados em imagens próximas, mas dados afastados não preservam necessariamente este afastamento. Por exemplo, alguns pontos vermelhos da espiral no canto superior direito são projetados no centro juntamente com imagens de pontos amarelos diametralmente opostos.
Com isso vemos que uma redução de dimensionalidade por PCA aplicado a um objeto não-linear
intrinsecamente unidimensional, como a espiral, provoca uma perda grande de informação dos dados de entrada, já que não há representação linear global que represente bem o objeto com o mínimo número de parâmetros, um. (Note porém que o PCA pode ainda ser útil, em casos não lineares,
em problemas solúveis com uma única dimensão global, ou aplicando-o localmente, em partes, mesmo assim com menos eficiência.)
%\todo{ver qual é o exemplo disso - toro - Nadler???? - fls 5}
%
\begin{figure}[!httb]
\centering
\includegraphics[scale=0.45]{pca_espiral_principal.png}
\caption[PCA - espiral]{Uma espiral e sua projeção na primeira direção principal por PCA.}
\label{pcaespiral}
\end{figure}
O \textit{Multi-Dimensional Scaling} - MDS foi apresentado pela primeira vez no \textit{Journal Psychometrika}
em 1941 \cite{young1941note}. Este método substitui o PCA quando por algum motivo a matriz de covariância não pode ser calculada,
e somente uma distância ponto a ponto é conhecida ou quando o número de dados $n$ é muito menor que a dimensão $d$ do espaço dos dados \cite{etyngier2008statistical}.
A partir dos $n$ dados em $\re^d$ a ideia é que o MDS construa uma representação tal que as distâncias entre pontos em $\re^k$ reflitam as proximidades entre os dados
\cite{fodor2002survey}.
Ou seja, o MDS reduz a dimensionalidade utilizando-se de distâncias no espaço dos dados e das características~ \cite{trosset1993formulation}.
A redução é conseguida através da minimização de determinada função custo.
%
\begin{comment}
O MDS clássico utiliza a função custo
\begin{equation*}
\rho(D_X,D_Y)=\|J^\top(D_X^2 - D_Y^2)J\|^2_F \ ,
\end{equation*}
onde $D_X$ é a distância euclidiana entre os dados, $D_Y$ é a distância entre as características,
%
$J= \mathcal{I}-\frac{1}{n}\openone\openone^\top$
%
é a matriz centralizadora utilizada para subtrair médias e o índice $F$ se refere à norma de Frobenius para matriz.
\end{comment}
%
Minimizar esta função custo significa preservar as variações das distâncias e uma solução conveniente é dada pelos autovetores associados aos maiores autovalores de determinada matriz \cite{ihler2003nonlinear}.
%$-\frac{1}{2}J^\top D_X^2J$
O PCA junto com seu dual, o MDS, são métodos simples e diretos que recobram a estrutura verdadeira dos dados num subespaço linear do espaço de entrada que, em geral, é de alta dimensão \cite{Bah2008diffusion}, mas não conseguem capturar estruturas
não-lineares de baixa dimensão. Como estes métodos clássicos são eficientes muitas pesquisas se desenvolvem no sentido de adaptá-los para abranger também casos de dados mais complexos.
O popular \textit{Kernel-PCA} -- KPCA~\cite{scholkopf1997kernel} amplia a utilização do PCA tradicional.
No KPCA não estamos preocupados com as componentes principais no espaço de
entrada, mas sim nas componentes principais das variáveis, ou características
(\textit{features}), que são relacionadas de modo não-linear às variáveis de
entrada. Métodos mais recentes e não lineares de grande influência, o Isomap~\cite{tenenbaum2000global}, autofunções do grafo laplaciano (laplaciano definido num grafo)\cite{belkin2003laplacian} e imersão localmente linear (\textit{Locally Linear Embedding} - LLE)\cite{roweis2000nonlinear} podem ser vistos como métodos KPCA sobre matrizes de Gram especialmente construídas~\cite{ham2004kernel}.
O recente \textit{Isometric Feature Map} --
Isomap~\cite{tenenbaum2000global,ZhengComputationalGeometry2008} é uma
generalização do MDS; é construído utilizando-se o MDS clássico preservando as
distâncias geodésicas em lugar das euclidianas. Distâncias geodésicas para este
método são definidas como a soma dos pesos das arestas ao longo do caminho mais
curto entre dois vértices de um grafo.
O também recente LLE~\cite{roweis2000nonlinear}
% \cite{tenenbaum2000global}
elimina a necessidade de se calcular a distância entre pontos muito separados. Diferentemente dos métodos anteriores, o LLE reconstrói a estrutura não-linear global com `pedaços' localmente lineares.
%Assume-se que o conjunto de dados é uma amostra representativa de uma população ou conjunto ideal de dados constituindo uma variedade. No exemplo da Figura \ref{pcaespiral}, a espiral seria o conjunto ideal de dados, e os pontos representados seriam os dados, uma amostra representativa do conjunto ideal, a espiral.
A ideia é fazer uma diferente redução de dimensionalidade linear em cada ponto (pois localmente uma variedade parece linear) e então combiná-las minimizando os erros~\cite{Tibshirani:DataMining14_2009}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Ver se vou manter esta ideia de LE como caso particular do DIFF, pois não explico a diferença da REnormalização,ou sj, não explico claramente que o LE funciona para densidades uniformes dos dados iniciais e o diff não tem esta exigência. Tb não digo pq! }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
O mais recente métodos das autofunções do laplaciano de grafo ou auto-mapeamento (ou
auto-aplicação) do laplaciano (\emph{laplacian
eigenmaps})~\cite{belkin2003laplacian} pode ser visto como um caso particular do
recente método das
aplicações de difusão (\emph{diffusion maps}\cite{coifman2005geometric}).
Tanto o método das autofunções do laplaciano de grafo como o método da aplicação
de difusão utilizam autovetores de uma determinada matriz como um arremedo de
coordenadas (ou coordenadas em sentido mais amplo) dos dados esperando
encontrar redução de dimensionalidade, capturando a estrutura principal dos
dados em poucas dimensões \cite{coifman2005geometric}. As principais vantagens
destas técnicas é que são não-lineares, gerais, robustas a ruído e preservam estruturas locais, proximidades. Estes
métodos são o foco desta tese, dados seus grandes potenciais unificadores para
modelagem, e
voltarão a ser discutidos nos capítulos \ref{autolap} e \ref{ap_dif},
respectivamente.
Ainda com o intuito de explorar a redução de dimensionalidade para dados não-lineares, ultimamente processos de difusão definidos em grafos têm sido estudados com bastante afinco. Estes são úteis para modelar de maneira robusta fenômenos contínuos no espaço tempo mas que se manifestam e são sensoriados em dimensões mais altas e em diversas escalas. As referências
%\cite{lafon2004diffusion}-\cite{wang2012unsupervised}
%ou será melhor:
\cite{lafon2004diffusion,lafon2006diffusion,GoldbergKimJournalofAppliedMathematics2010,Israel2011difusao,wang2012unsupervised}
são apenas alguns exemplos de pesquisas nesta área.
Em parte esta \textit{difusão} do emprego da difusão em grafos pode ser decorrente da diversidade de áreas de aplicação deste tópico. Os processos de difusão do tipo aqui tratado são largamente explorados nas engenharias, principalmente da computação, na física, na economia, na biologia e, mais timidamente, até na área social.
A visão computacional, por exemplo, por lidar com conjunto de dados não-lineares de altas dimensões (multíplas imagens, múltiplos vídeos), vê no estudo dos processos de difusão uma ferramenta útil para reduzir a dimensionalidade dos dados e assim poder analisar de forma mais eficiente os padrões neles contidos. O estudo de imagens perpassa o âmbito da medicina, da geografia, das artes, só para citar alguns exemplos.
%\todo{ver toro paralelo entre processos de difusão e propagação - fls 6}
As ciências naturais são repletas de sistemas dinâmicos complexos que fornecem variáveis dinamicamente relevantes.
%\todo{toro - pagerank?}
%
% Vou tirar a explicação da figura do diff para a espiral em R^2 pois não estou entendendo bem.
\begin{comment}
Para finalizar esta seção vamos dar uma ideia rápida do comportamento do algoritmo da aplicação de difusão em relação ao PCA para dados não lineares. A figura \ref{diffespiral} apresenta um gráfico da mesma espiral acima só que desta vez consideramos a imagem pela aplicação de difusão reduzindo de duas para uma dimensão.
O tempo considerado foi $T = 40.$ Note em (a) que a imagem dos pontos da espiral se comprimem perto do centro de modo que parece que a espiral foi reduzida a um único ponto. Em (b) ampliamos a imagem para percebermos que o método consegue organizar as cores de modo que as informações dos dados de entrada não foram completamente perdidos e estão ali guardados numa outra escala.
\end{comment}
%
\begin{comment}
%\newpage
\begin{figure}
\centering
\subfigure[refespdiff][Escala original]{\includegraphics[scale=0.4]{diff_espiral.png}}
\subfigure[refespamplia][Escala ampliada]{\includegraphics[scale=0.4]{diff_espiral_reta.png}}
\caption{(a) A figura apresenta a espiral e sua imagem pela aplicação de difusão na escala original. Neste caso a imagem parece ser apenas um ponto. (b) Ampliamos a imagem da espiral e vemos uma reta separando as partes por cores diferentes.}
\label{diffespiral} % Para referenciar esta figura mais a frente caso sj necessário
\end{figure}
\end{comment}
\section{Contribuições da tese}
Nesta tese exploramos o método das aplicações de difusão como ferramenta ampla de
modelagem computacional para redução de dimensionalidade em especial com a finalidade de
clusterização/agrupamento, reconhecimento e reconstrução de sinais obtidos pela quantificação de qualidades do sistema físico.
Aqui buscamos de forma minuciosa relacionar de forma experimental e teorica
aspectos da técnica da difusão com aquela das autofunções do laplaciano e com o clássico PCA.
Tal técnica, que dá a vertente da tese, é estruturada sobre um grafo dos dados para o qual toda uma escolha de parâmetros se faz necessária.
Procuramos fazer uma investigação de tais escolhas
tendo em vista, porém, que não há como uniformizá-las uma vez que dependem de cada aplicação.
Na Figura \ref{arestaHel}, por exemplo, apresentamos um trecho de um grafo formado por pontos de uma hélice onde um importante parâmetro $\varepsilon,$ que dá o tamanho da vizinhança no processo de difusão, foi utilizado como $\varepsilon=0,001r^2,$ onde $r$ é o diâmetro do conjunto de dados, no caso, do conjunto de pontos da hélice.
%
\begin{figure} % Figura feita com todo_dado; X=X19; cplotamy(X, 0.1, 2,1)
\centering
\includegraphics[scale=0.7]{arestas_hel.png}
\caption[Grafo peso gaussiano $\varepsilon=0,001r^2$ - hélice]{Trecho de um grafo formado por alguns pontos de uma hélice ideal onde as retas vermelhas representam as arestas ligando os vértices. A gradação na tonalidade do vermelho se refere ao maior ou menor valor numérico destas arestas. O parâmetro usado para a vizinhança de difusão foi de
$\varepsilon=0,001r^2,$ onde $r$ é o diâmetro do conjunto de dados.}
\label{arestaHel}
\end{figure}
A Figura \ref{arestaHelc1} apresenta o mesmo trecho do grafo sendo que desta vez foi utilizado o parâmetro
$\varepsilon=0,01r^2.$ Ou seja, uma pequena variação num dos parâmetros pode tornar o método eficiente ou não em determinada aplicação. No caso da aprendizagem de variedade, \textit{manifold learning}, o grafo obtido na Figura \ref{arestaHel} é mais interessante pois resgata melhor a variedade matemática ideal que está por trás da nuvem de pontos dada.
Aumentando-se a vizinhança,
$\varepsilon,$ para o núcleo gaussiano da aplicação de difusão acarretará num grafo com mais arestas com pesos maiores
o que pode comprometer a utilização do método em algumas aplicações.
\begin{figure} % Figura feita com todo_dado; X=X19; cplotamy(X, 1, 2,1)
\centering
\includegraphics[scale=0.7]{arestas_hel_c1.png}
\caption[Grafo peso gaussiano $\varepsilon=0,01r^2$ - hélice]{Mesmo grafo anterior desta vez com vizinhança maior para o processo de difusão, $\varepsilon=0,01r^2.$}
\label{arestaHelc1}
\end{figure}
Uma das grandes contribuições da presente tese é a exploração das possibilidades das aplicações de difusão para resolver o problema ambientado na \textit{teoria dos padrões} que consiste na busca de uma estrutura de \textit{feedback} onde algoritmos de \textit{bottom-up} e \textit{top-down} sejam realimentados e modificados para melhor compreensão do sistema físico, conforme é exposto no capítulo \ref{carto}.
A novidade é investir na reconstrução para um algoritmo que não foi concebido originalmente com o ferramental completo para a construção de sistemas do aprendizado de máquina no estilo da teoria de padrões de
{\em reconhecimento por síntese}.
Os experimentos na forma que aqui são apresentados, ainda que utilizando técnicas anteriormente propostas, também consubstanciam uma contribuição importante.
A percepção da maior sensibilidade do PCA em relação a variações de iluminação no reconhecimento de imagens digitais em comparação com o mapeamento de difusão é outra contribuição significativa do presente texto.
O desenvolvimento matemático aqui proposto é meticuloso e procura preencher lacunas na literatura correspondente. A reconstrução de sinais através da proposta de pré-imagem aqui apresentada com a otimização de determinada função custo pretende ser útil em aplicações futuras.
\section{Organização dos capítulos}
O próximo capítulo discorre sobre ideias gerais de aprendizagem de máquina e
teoria de padrões, com foco em tópicos aos quais esta tese se vincula.
Como foi dito na seção \ref{sec1pan}, alguns métodos de redução de dimensionalidade são clássicos e merecem um estudo preliminar para motivar a necessidade de métodos mais gerais. Em especial o método da \emph{análise de componentes principais} (PCA), que estuda a redução da dimensionalidade através de projeções em subespaços ditados pelos maiores autovetores da matriz de covariância dos dados, não pode faltar por ser um método que traz grande intuição para todos os outros.
Por isso o capítulo \ref{1pca} apresenta um resumo do mesmo. A grande desvantagem deste método é a linearidade que distorce informações sobre dados não-lineares com alto grau de complexidade não permitindo redução eficaz,
conforme já exemplificado.
Os recentes algoritmos para redução de dimensionalidade nos quais o presente trabalho se baseia utilizam fortemente a \emph{teoria espectral dos grafos}. Para melhor aproveitamento desta ferramenta indispensável, alguns conceitos sobre a mesma serão dados no capítulo \ref{falando}.
O capítulo \ref{autolap} apresenta o método não-linear das \emph{autofunções do laplaciano} que no fundo é um caso especial muito utilizado da \emph{aplicação de difusão} \cite{Socher2008}, o método de interesse principal deste trabalho. A aplicação de difusão definida nos dados do problema baseia-se numa cadeia de Markov definida num grafo estruturado a partir dos dados disponíveis. %Este caso especial se aplica quando os dados estão distribuídos uniformemente sobre uma variedade o que raramente acontece nas tarefas reais de aprendizado de máquina.\\
Fazendo os parâmetros $\alpha = 0$ e $t=0$ no processo de Markov obtemos os mesmos resultados para \emph{autofunções do laplaciano} e para \emph{aplicação de difusão}. A exposição dada aqui procura enfatizar novas conexões e a organização dos conceitos espalhados na literatura tem por finalidade ajudar na investigação desta tese.
%Por isso o capítulo cinco indroduzirá conceitos básicos sobre passeios aleatórios e cadeia de Markov.\\
%\todo{ cap de M. Brown => retirá-lo!}
O capítulo \ref{ap_dif} apresenta de forma unificada o estado da arte referente à teoria e prática do método não linear das \emph{aplicações de difusão} que tem a grande vantagem de possibilitar uma análise geométrica dos espaços de dados em diferentes escalas. Este método acrescenta à simplicidade da teoria espectral dos grafos a beleza e robustez da aleatoriedade de processos de Markov.
Terminamos esse capítulo apresentando uma aplicação através de um experimento de imagens onde a redução de dimensionalidade é fundamental para qualquer tipo de análise já que lidamos com diversos vetores de 10000 entradas. %com matrizes da ordem $10000 \times 27.$
% Acrescentei em 07/01/14
O capítulo \ref{capluz} trata de um fenômeno de grande importância na análise e reconhecimento de imagens - a questão da variação de iluminação. Esta variação pode acarretar em dificuldade extra para algoritmos associados. Utilizamos dados sintéticos e imagens digitais para ilustrar o comportamento dos dados com relação ao mapeamento de difusão comparando-o com os resultados obtidos pelo PCA.
Os atuais problemas da extensão e da pré-imagem são abarcados no oitavo capítulo onde analisamos a existência de uma possível inversa para a aplicação de difusão permitindo o emprego desta técnica a problemas não trivialmente possíveis de aprendizagem de máquina supervisionados e semi-supervisionados, bem como a remoção de ruídos e reconhecimento na presença de oclusão parcial severa e modelagem mais robusta e fundamentada da dinâmica original dos dados a partir das coordenadas de difusão.
As conclusões desta tese são apresentadas no capítulo \ref{capconclui}.
Finalmente o apêndice apresenta algumas demonstrações de resultados relevantes mas que não foram colocadas na parte principal do texto para tornar a leitura do mesmo mais fluente.%já que não
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\todo{Ver se vou manter os apêndices velhos. Provavelmente não, principalmente o apêndice 2.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Os apêndices após a conclusão apresentam um pseudo código dos métodos dos capítulos $4$ e $5$ e alguns exemplos extras de aplicação que estão em fase de estudo.
%Apresentamos uma análise baseada em sua aplicação em exemplos de dados lineares e não lineares.
%\todo{fazer exemplo linear, ou retirar esta frase!}
\begin{comment}
\todo{Modificar esta frase abaixo! Ver se o foco principal será redução de dimensionalidade e tirar a palavra realidade social e substituir por outra aplicação. QUAL???? }
Um dos aspectos da tese seria investigar diversas circunstâncias relacionadas a métodos de redução de dimensionalidade tentando apreender suas características.
Finalmente gostaríamos de utilizar o método da aplicação de difusão a um conjunto de dados não lineares de algum processo dinâmico da realidade social e a partir daí extrair informações relevantes para pesquisa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555555555
(Wikipedia)The reduced-dimensional representations of data are often referred to as "intrinsic variables". This description implies that these are the values from which the data was produced.
\end{comment}