# Apontamentos IC 1ª Freq
###### tags: `IC` `Teórica`
# Aula 2
> [name=pdpm19] Livro sec. 2
## Neurónio Artificial
### Modelo do Neurónio Artificial

- Função $g: \mathbb{R}^n -> \mathbb{R}$, que a cada vetor $x$, de dimensão $n$, de entrada faz corresponder um real $y$;
- Conta ainda com um **vetor de pesos** $[w0w1...wn]$ e da **função de ativação** $f(.)$.

### Cálculo da Saída do Neurónio
- Os valores de entrada $x$, são alvo de uma soma pesada
- $s = \sum_{i=0}^{n} x_{i}w_{i}$, tendo em conta que $x_{0} = 1$
- De seguida esse valor passa por uma função de ativação
- $y = f(s)$

### Funções de Ativação
Existem várias, que podem assumir várias formas, entre elas:
- linear $f(s) = \beta s$
- degrau $f(s) = (\beta2, s >= 0)$ || $(\beta1, s < 0)$
- rampa $f(s) = (\beta1, s >= \beta)$ || $(s, |s| < \beta)$ ||$(-\beta1, s <= -\beta)$
- sigmoid $f(s) = \frac{1}{1+exp(- \lambda s)}$
- tangente hiperbólica $f(s) = \frac{exp(\lambda s)-exp(-\lambda s)}{exp(\lambda s)+\exp(-\lambda s)}$
- ReLu $f(s) = max(0, s)$
- Por norma $\beta1 = 0$ e $\beta2 = 1$
- Por norma as funções de ativação são **monótonas crescentes**, e à exceção da função de ativação linear: $f(-\infty)=-1 ||f(-\infty)=0$ e $f(\infty)=1$

### Capacidade de Discriminância de um Neurónio
- Pontos do espaço de entrada que sejam **linearmente separáveis**;
- Um neurónio consegue implementar um **hiperplano** (**fronteira de decisão**) que separa os pontos em que a saída é $>=0$ daqueles em que a saída é $<0$

## Regras de Aprendizagem de um Neurónio
### Aprendizagem
- Para se encontrar os pesos são necessários **dados** relativos ao problema
- Os dois tipos de aprendizagem são:
- **Supervisionada**: os pontos contêm informação sobre a classe a que pertencem;
- **Não Supervisionada**: os pontos não contêm informação relativa à sua classe.
- Os pontos são: $P_{1}=(peso_{1}, altura_{1}, classe_{P_{1}})$, para o exemplo acima representado pela figura
- De uma forma mais genérica: $P_{i}=(x_{i,1},...., x_{i,n}, d_{i})$, onde os valores $x_{i,1},...., x_{i,n}$ são as **características** e $d_{i}$ a verdadeira **classe** do ponto $i$

### Descida do Gradiente
- Forma mais comum de aprendizagem utilizada em redes neuronais;
- Necessita de uma **função de custo** que permite saber quão próximo da verdadeira classe ficou a saída do neurónio;
- A mais comum é o quadrado do erro, _squared error_: $e_{j} = (d_{j} - y_{j})^2$, onde $d_{j}$ é a classe verdadeira e $y_{j}$ a saída do neurónio para o ponto $j$;
- A ideia consiste em encontrar os pesos que **minimizam o erro**, procurando no espaço dos pesos ao longo do sentido contrário ao do gradiente.


- Dado um ponto $j$:
- cada peso $w_{i}$ na iteração $t$ é ajudaste de acordo com \begin{equation} w_{i}(t) = w_{i}(t-1) + \Delta w_{i}(t) \end{equation} onde \begin{equation} \Delta w_{i}(t) = \eta (-\frac{\sigma e_{j}}{\sigma w_{i}}) \end{equation} e \begin{equation} \frac{\sigma e_{j}}{\sigma w_{i}} = -2(d_{j} - y_{j})\frac{\sigma f}{\sigma s_{j}}X_{j,i}\end{equation}
- $\eta$ é **taxa de aprendizagem**, $X_{j,i}$ é a característica $i$ do ponto $j$ e $f$ é a função de ativação
- Para que $\frac{\sigma f}{\sigma s_{j}}$ não anule esta derivada e percamos a informação relativa ao gradiente, **$f$ não pode ser o degrau**

- Se utilizarmos a funão de ativação sigmoid, temos:
- $\Delta w_{i}(t) = 2\eta(d_{j} - y_{j})\lambda f(s_{j})(1- f(s_{j}))X_{j,i} = 2\eta(d_{j} - y_{j})\lambda y_{j}(1-y_{j})X_{j,i}$

### Widrow-Hoff
- Esta regra, que considera a descida do gradiente a função identidade, $f(s_{j}) = s_{j}$, onde temos:
- $\frac{\sigma f}{\sigma s_{j}} = 1$
- $\Delta w_{i}(t) = 2\eta(d_{j} - y_{j})X_{j,i}$
- Também é conhecido por _Least Mean Squares_ ou _Delta Rule_.

---
# Aula 3
> [name=pdpm19] Livro sec. 3
## Perceptrão (_Perceptron_)
- Chama-se perceptrão a um tipo de rede neuronal em que os neurónios estão organizados numa única camanda.

## _Multi Layer Perceptron_ (MLP)
- MLP ou Percetrão multicamada, é a junção de vários perceptrões, ou seja, uma junção de vários neurónios em várias camadas;
- Sendo assim a 1ª camada trabalha com a informação bruta, mas as restantes camadas, trabalham com a saída das camandas anteriores, um _feedforward neural network_ (FFNN);
- Permite a aprendizagem de problemas não lineares;
- O treino é feito através da retropropagação do erro (_error backpropagation_).


### Arquitetura _MLP_
- Todas as camadas, menos a última são chamadas de camadas escondidas;
- A última camada, tem, ironicamente o nome de última camada, ou camada de saída;
- A **capacidade de aprendizagem** de uma rede, são o **nº de camadas escondidas**, devido à aprendizagem residir nos pesos;
- O nº de entradas e saídas são intrínsecos ao problema a resolver.
- Na imagem abaixo, temos um MLP com 2 camadas escondidas, 1 camada de entrada e 1 de saída.

### Propriedades _MLP_
- Uma rede com **uma camada escondida, consegue resolver funções contínuas diferenciáveis**;
- Uma rede com **2 camadas escondidas, consegue resolver qualquer função**, mas pode não ser a mais eficiente;
- Nos dias de hoje, estudam-se redes _FFNN_ com mais de 2 camadas escondidas, devido a poderem tornar a aprendizagem mais eficiente.

### Aprendizagem _MLP_
#### Retropropagação do erro
- Tem 2 fases:
1. **Passa os dados para a frente**: calcula os valores nas saídas da rede;
2. **Passa o erro para trás (retropropagação)**, propaga o erro vindo da camada de saída até à camada de entrada e no processo atualiza os pesos da rede em função deste erro.

#### Tipos de aprendizagem
- Permite os seguintes tipos de aprendizagem supervisionada:
- Aprendizagem **estocástica ou online**, onde a **atualização dos pesos é feita para cada ponto**;
- Aprendizagem por **lotes (_batch_) ou offline**, sendo que a **atualização dos pesos só é feita no fim de cada época** (Todo o conjunto de treino é uma lote);
- Aprendizagem **mini-lotes (_mini-batch_)**, sendo um misto das anteriores, pois a **atualização dos pesos é feita quando todos os pontos do mini-lote passam pela rede**. (Por norma divide-se o conjunto de treino em vários lotes);
- Obs:
- Do ponto de vista de computacional, é mais pesado de fazer o ajuste à rede na aprendizagem estocástica pois quando temos um conjunto de treino muito grande (fazemos muitos ajustes), ao invés dos lotes que só fazem 1 ajuste por iteração;
- A aprendizagem estocástica permite escapar mais facilmente a minimos locais;
- Por norma recorre-se mais vezes à mini-lotes por aproximar-se dos bons resultados da estocástica, mas evitando demorar-se demasiado tempo.

### Algoritmo da Retropropagação do Erro
Este algoritmo é para treino em lotes, visto que o erro só é atualizado no fim de cada iteração (época).
1. **Inicializar os pesos**, com valores entre -0.1 e 0.1;
2. **Calcular as saídas e os erros**
- na primeira camada
\begin{equation} s_{j} = w_{0j} + \sum_{i}{w_{ij}X{i}} \end{equation}
- restantes camadas
\begin{equation} s_{j} = w_{0j} + \sum_{i \in camanda anterior}{w_{ij}y{i}} \end{equation}

\begin{equation} y_{j} = f(s_{j}) \end{equation}
- camada de saída
\begin{equation} e_{j} = f'(s_{j}) = \frac{\sigma c}{\sigma y_{j}} \end{equation}
- restantes camadas
\begin{equation} e_{j} = f'(s_{j}) = \sum_{p \in camanda seguinte}{w_{jp}e_{p}} \end{equation}
3. **Atualizar os pesos**
\begin{equation}w_{ij} <- w_{ij} + \Delta w_{ij} \end{equation}
- primeira camada
\begin{equation} \Delta w_{ij} = - \frac{\eta}{N} \sum_{x_{i} \in X}{x_{i}e_{j}}\end{equation}
- restantes camadas
\begin{equation} \Delta w_{ij} = - \frac{\eta}{N} \sum_{y_{i} \in camada anterior}{y_{i}e_{j}}\end{equation}
4. **Verificar as condições de paragem**

#### Condições de paragem
- Número fixo de épocas;
- Atribuição de um valor pré-definido de erro (_loss_);

#### Algoritmo cont.
Necessitamos ainda de escolher as funções de ativação e custo $f$ e $c$
- Escolhendo a função de ativação sigmoid $f'(x) = f(x).(1- f(x))$;
- A função de custo sendo o erro quadrático médio (MSE _Mean Squared Error_), onde $m$ é o número de saídas da rede (usada para regressão):
\begin{equation}c(d(x), y(x)) = \frac{1}{m} \sum_{i=1}^{m}(d_{i} - y{i})^2 \end{equation}
- Logo,
\begin{equation} \frac{\sigma c}{\sigma y_{j}} = - \frac{2}{m}(d_{j} - y_{j}) \end{equation}

## Classificação
- É um tipo de problema em que pretendemos fazer corresponder a cada **ponto de entrada uma etiqueta chamada de classe**;
- Consiste em que a rede consiga **aprender, a partir do conjunto de treino, a distinguir os pontos de cada classe**, para que assim possa **classificar corretamente pontos não pertencentes ao conjunto de treino (generalizar)**;

### MLP na Classificação
- A ideia é que o MLP crie **fronteiras de decisão entre as diferentes classes do problema**;
- **Cada linha** nas fronteiras corresponde a **um neurónio da camada escondida**;
- No exmplo abaixo temos 10 fronteiras de decisão, logo são necessários 10 neurónios na camada escondida;
- Notando que ainda existem pontos mal classificados, iriamos necessitar de pelo menos mais 2 neurónios.

## Regressão
- É um tipo de problema em que se **efetua a aproximação de funções**, pois a cada **ponto na entrada** da rede pretendemos que a **saída seja a mais próxima possível de um valor dado por uma função**;
- A **função a apromixar** é muitas vezes **desconhecida** em termos analíticos, pois só se possui valores de amostras em determinados pontos;
- Os neurónios da camada escondida neste caso **servem para lidar com os pontos de inflexão da função a aproximar**, pelo que são **precisos tantos quantos os pontos de inflexão mais um**.

### MLP na Regressão
- Neste exemplo, deveriam de ser utilizados 5 neurónios na camda escondida, visto existirem 4 pontos de inflexão (são pontos na função, onde o sinal é trocado)

## Regularização
- É uma alteração feita ao algortimo de treino ou à arquitetura da rede para **reduzir o erro de generalização**;
- Pode ser feita de várias formas, algumas das quais consistem em alterações à função de custo com o objetivo de limitar a gama de soluções que se podem obter com o modelo;
- Esta limitação ajuda a simplificar o espaço de pesquisa, para que assim se possa obter uma solução rapidamente e mais adequada ao problema que se está a resolver;
- Por vezes estas alterações são feitas de forma a que seja introduzido conhecimento _à priori_.

### Decaimento dos Pesos
- O decaimento dos pesos (_Weight Decay_) é um tipo de regularização simples, que consiste em modificar a função de custo de forma a **penalizar valores de pesos elevados**: \begin{equation} E = MSE + \lambda w^{T} w = MSE + \lambda \sum_{i}w_{i}^2 \end{equation} onde $\lambda$ é uma constante positiva que controla a importância dada ao termo de regularização e no vetor $w$ colocamos todos os pesos do modelo;
- Ao treinar a rede com esta função de custo, estamos a exigir que a rede aproxime os dados (através do _MSE_) e ao mesmo tempo que os pesos tenham valores pequenos, através do decaimento;
- Este regularizador representa na realidade a norma $L_{2}$ do vetor de pesos, ou regularizador de _Tikhonov_;
- Utilizando a descida do gradiente para atualizar os pesos: \begin{equation} w <- w - \eta \nabla_{w}E \end{equation} onde $\eta$ é a taxa de aprendizagem (_learning rate_) e $E$ representa a função de custo;
- Introduzindo agora o decaimento dos pesos, a expressão passa a ser: \begin{equation}w <- w - \eta(\nabla_{w}E + \lambda w) = \end{equation} \begin{equation} w <- (1- \eta\lambda)w - \eta\nabla_{w}E \end{equation}

### Norma $L_{1}$
\begin{equation} E = MSE + \lambda \sum_{i} |w_{i}| \end{equation}
- O uso deste regularizador faz com que os pesos contenham muitos valores zero e poucos sejam diferentes de zero;
- Pode ser visto como um _feature selection_, pois entradas associadas a um peso zero são ignoradas.

## Conjuntos de Redes

- Conjuntos ou _ensembles_ de redes podem melhorar resultados;
- Um conjunto é normalmente composto por **várias redes idênticas**, com excessão de **serem inicializadas com pesos diferentes e treinadas independentemente umas das outras**;
- Estas redes, embora semelhantes, **irão produzir resultados diferentes**, mesmo tendo sido treinadas e testadas com o mesmo _dataset_ (devido aos diferentes pesos);
- Podemos então beneficiar do desempenho de cada uma destas redes.

### Combinar Saídas
- Tendo $n$ redes treinadas para resolver o mesmo problema;
- Num problema de classificação, com $m$ classes, podemos considerar que a saída do _ensemble_ corresponde à classe mais votada pelas $n$ redes;
- Num problema de regressão, podemos considerar que a saída do _ensemble_ corresponde:
- à média das saídas: $y_{m} = \frac{1}{m} \sum_{i=1}^{n}y_{i}$;
- à média pesada das saídas de cada rede: $y_{mp} = \sum_{i=1}^{n} w_{i}y{i}$, onde $w_{i}$ é o peso.
- Podemos sempre utilizar apenas a rede que apresentou melhores resultados, ignorando as restantes.

### Conjuntos de Redes
- Só faz sentido combinar a **informação de várias redes, se estas discordarem umas das outras**;
- Podemos também treinar **diversas redes, onde cada rede terá diferentes versões dos dados**;
- Pode-se obter **diferentes versões dos dados**, partindo o conjunto em sub-conjuntos diferentes, ou através de **_Bagging_**;
- O resultado destas redes é por fim agrupado **usando votação (classificação)** ou faz-se a **média das saídas (regressão)**;
- Outra forma de obter melhores resultados passa por fazer as **redes trocarem informação durante o treino**, _Boosting_, ao invés de serem **treinadas independentemente**;
- Outra forma de obter redes diferentes passam por alterar qualquer elemento constituinte da rede:
- Mudar a topologia;
- Mudar o algoritmo de treino;
- Mudar a taxa de aprendizagem;
- Mudar as funções de ativação,...


#### _Bagging_
- Consiste treinar cada rede com um sub-conjunto gerado, **através de repetições do conjunto de treino**, mantendo o **mesmo número de pontos do conjunto de treino original**;

#### _Boosting_
- Este método troca informação entre as redes durante o treino:
- As redes são treinadas sequencialmente;
- As primeiras tratão dos padrões mais fáceis e deixam os mais difíceis para as seguintes;
- Estes padrões mais difíceis estão associados a um custo de erro superior, fazendo as redes ficarem mais aptas a lidarem com os padrões mais difíceis.

## Redes Profundas
- Estas redes, que levam ao _deep learning_ são redes que contêm muitas camadas, na casa das dezenas;
- Mais camadas porquê?:
- Certas redes com várias camadas, tiram resultados melhores a processar imagens;
- Existem vantagens computacionais em usar mais camadas.

### Redes de Convolução: _CNNs_
- São as redes profundas mais comuns (_Convolutional Neural Networks_);
- Tem por base a ideia de **simular o funcionamento do sistema visual humano**;
- A **primeira parte** consiste em **extrair as características (_features_)** e a **segunda** em usar essas **características para classificar a imagem de entrada**;
- A parte que faz a extração tem dois tipos de camandas:
- **convolução**: aplicam um **filtro aos dados** que recebem e geram os **mapas de características (_feature maps_)**;
- **sub-amostragem (_pooling_)**: faz uma **redução no tamanho dos mapas** criados acima.
- Os **filtros aplicados**, na camada de convolução, servem só para **realçar determinadas características das imagens**;
- Na camanda de sub-amostragem, torna irrelevante a zona da imagem onde dada característica foi detetada. Gera assim uma **invariância** na deteção de características (não interessa o local exato da imagem onde tal característica foi detetada, apenas interessa que estão na imagem).

---
# Aula 4
> [name=pdpm19] Livro sec. 4
## Aprendizagem não supervisionada
- Consiste em **associar** elementos que são semelhantes no espaço de entrada (características), por norma estes agrupamentos tem o nome de _clusters_;
- Os $n$ pontos de entrada serão agrupados em $m$ _clusters_, tal que $m < n$. Estes pontos serão agrupados com os elementos mais parecidos entre si.

### Aprendizagem de _Hebb_
- Sempre que o **neurónio A ativa o neurónio B**, os pesos entre eles **são reforçados (aumentado)**;
- Consiste em **percetrões** (uma só camanda com neurónios);
- Padrões desconhecidos, valor baixos, são **coisas novas**. Pelo contrário, padrões conhecidos, apresentam um valor alto. Assim conseguimos criar um **detetor de novidades**.
- Segundo a imagem acima, a mudança nos pesos na iteração $t$, é dada por: \begin{equation}\Delta w_{ik}(t) = \eta x_{i}(t)y_{k}(t) \end{equation} onde $\eta$ é a taxa de aprendizagem
- A atualização dos pesos segue a fórmula: \begin{equation}w_{ik}(t) = w_{ik}(t-1) + \Delta w_{ik}(t) \end{equation}

#### Algortimo:
1. Inicializar os pesos a 0;
2. Para cada valor de x, achar o valor de y correspondente;
3. Ajustar os pesos;
4. Parar quando delta (mudanças nos pesos) é pequeno ou atinja o máximo de épocas.

#### Fator esquecimento:
- Por vezes os pesos atingem valores arbitrariamente elevados, $NaN$, então aplica-se um **fator de esquecimento**, $\alpha$, que limita o crescimento dos pesos: \begin{equation}\Delta w_{ik}(t) = \eta x_{i}(t)y_{k}(t) - \alpha y_{k}(t)w_{ik}(t-1) \end{equation} sendo $\alpha$ uma constante positiva.

#### Abordagem de Sejnowski
- Esta abordagem consiste em fazer o **crescimento dos pesos proporcional aos desvios** relativamente à média das quantidades que aparecem na expressão original de _Hebb_ : \begin{equation} \Delta w_{ik}(t) = \eta (x_{i}(t) - \bar{x_{i}})(y_{k}(t) - \bar{y_{k}})\end{equation} onde \begin{equation} \bar{x_{i}} = \frac{1}{m}\sum_{p=1}^{m} x_{i,p} \end{equation} e \begin{equation} \bar{y_{k}} = \frac{1}{m}\sum_{p=1}^{m} y_{k,p} \end{equation} sendo $m$ o número de pontos do conjunto de treino.

#### Exemplo
- Padrão conhecido (ligações vistas anteriormente) $\rightarrow$ saída com valores elevados;
- Padrão desconhecido $\rightarrow$ saída com valores pequenos;
- Pode-se então construir um **detetor de novidade**.


- Padrões de 150 a 200 são normais e de 201 a 300 anormais, visto que os valores normais retornam valores elevados e valores desconhecidos valores pequenos, recorreu-se à aprendizagem **anti-hebbiana**, que produz valores altos quando aparecem padrões desconhecidos ($\eta$ passa a ser negativo).

### Aprendizagem por Quantização Vetorial (LVQ)
- Cada neurónio na camada de saída vai representar um grupo, _cluster_;
- Baseada na competição entre grupos;
- Ganha o **vetor de peso** que seja mais **próximo do ponto de entrada**;
- Por norma, a medida de proximidade é a distância Euclidiana: \begin{equation} d_{p,k} = \sqrt{\sum{i=1}^{n} (x_{i,p}(t) - w_{ik}(t-1))^2} \end{equation}
- A atualização dos pesos é feita de acordo com: \begin{equation} \Delta w_{ik}(t) = \begin{cases}\eta (t)(x_{ip}(t)-w_{ik}(t-1)), & k \in K_{p}(t) \\ 0\end{cases} \end{equation} onde $\eta (t)$ é a taxa de aprendizagem e $K_{p}(t)$ o conjunto de vizinhos do neurónio vencedor.
- **Número de neurónios é igual ao número de grupos que quero apresentar**;
- As **condições de paragem** para este algoritmo podem ser:
- Atingir o número máximo de épocas;
- Ajustes dos pesos são muito pequenos;
- Erro da quantização seja suficientemente pequeno: \begin{equation}EQ = \sum_{p=1}^{P} d_{p,k}^2\end{equation}

#### Algoritmo
1. Incializar a rede:
1.1 Escolher número de grupos a obter ( -> cada grupo é 1 neurónio);
1.2 Pesos inicializados com valores pequenos e aleatórios || Utilizar os primeiros pontos de entrada para o efeito;
1.3 Inicializar a taxa de aprendizagem e o raio da vizinhança.
2. Aprendizagem:
2.1 Cada ponto p fazer:
2.1.1 Achar a distância Euclidiana entre o ponto de entrada e os pesos de cada neurónio da rede;
2.1.2 Achar a saída para a qual a distância Euclidiana é a menor;
2.1.3 Atualizar todos os pesos da vizinhança.
2.2 Atualizar a taxa de aprendizagem;
2.3 Reduzir o raio da vizinhança;
2.4 Parar se as condições de paragem forem atingidas, senão voltar ao ponto 2.1.

#### Fator de consciência
- Por vezes um grupo, ao ganhar muito, faz com que de 2 ou mais neurónios, só 1 é que fica preenchido com os dados todos, e os restantes vazios;
- Ao se introduzir um **fator de consciência, evitamos que um neurónio domine na decisão do vencedor**;
- As saídas são então determinadas: \begin{equation}y_{k,p}= \begin{cases}1 & min_{\forall k}(d_{p,k}-b_{k}(t)) \\ 0 \end{cases} \end{equation} onde \begin{equation}b_{k}(t)= \gamma (\frac{1}{n} - g_{k}(t)) \end{equation} e \begin{equation}g_{k}(t)=g_{k}(t-1) + \beta (y_{k,p}- g_{k}(t-1)) \end{equation}
- $n$ é o nº de características e $g_{k}(0)=0$;
- Inicialmente temos $b_{k}(0) = \gamma/n$, isto dá a todas as saídas a mesma probabilidade;
- $b_{k}(t)$ é o fator de consciência para cada saída $k$;
- Quantas mais vezes $k$ sair, maior será $g_{k}(t)$, tornando $b_{k}(t)$ mais negativo;
- $\beta=10^{-4}$ e $\gamma = 10$.

#### Exemplos
:::info
Ver melhor exemplos deste método
:::

### _Self Organizing Maps_ (SOM)
- É uma rede em que **todos os neurónios estão ligados a todas as saídas**, estando organizados numa **malha bidimensional** que é ajustada ao longo da aprendizagem;


#### Aprendizagem
- É baseada numa **estratégica competitiva**;
- Consideramos que $x_{,p}$ são os vetores de dados;
- A dimensão do espaço de entrada é $m$ e o número de neurónios $n$, e $n <m$;
- Duas formas de inicializar os vetores de pesos são:
- Forma aleatória;
- Valores de pontos de dados escolhidos de forma aleatória.
- A forma de treino é **estocástica** (os pesos são ajustados após a exibição de cada ponto do conjunto de dados);
- O ajuste de pesos é dado: \begin{equation} w_{kj}(t+1) = w_{kj}(t) + \eta (t)h_{qn,kj}(t)(x_{,p}(t)-w_{kj}(t)) \end{equation} onde $qn$ represam a linha e coluna do neurónio vencedor;
- O **neurónio vencedor** é aquele cujo **vetor de pesos possui a menor distância ao vetor de entrada** $x_{,p}$;
- A **função de vizinhança**, $h_{qn,kj}$, onde determina quais os neurónios de coordenadas $kj$ terão os seus pesos ajustados \begin{equation}h_{qn,kj}(t) = exp(- \frac{||c_{qn}-c_{jk}||}{2 \sigma (t)^2}) \end{equation}
- O **tamanho da vizinhança**, $\sigma (t)$, é menor quanto menor for o tamanho da vizinhança a considerar\begin{equation}\sigma (t) = \sigma (0)exp(-t/T1) \end{equation}
- A **taxa de aprendizagem** \begin{equation} \eta (t)= \eta (0)exp(-t/T2)\end{equation}
- As condições de paragem para este algoritmo podem ser:
- Atingir o número máximo de épocas;
- Ajustes dos pesos são muito pequenos;

##### Algoritmo
1. Inicializar a rede:
1.1 Definir a grelha de neurónios (mapa) -> por norma é bidimensional e de forma retangular ou quadrada;
1.2 Vetor de pesos, m-dimensional de cada neurónio é associado ao centro dum cluster;
1.3 Inicializar os pesos;
2. Aprendizagem:
2.1 Para cada ponto:
2.1.1 Exibição de cada ponto ao conjunto de treino;
2.1.2 Verificar qual é o neurónio vencedor;
2.2 Ajustar os pesos;
2.3 Atualizar a taxa de aprendizagem;
2.4 Reduzir o raio da vizinhança;
2.5 Parar se as condições de paragem forem atingidas, senão voltar ao ponto 2.1.

#### SOM Vs. LVQ
- **SOM** apresente or neurónios organizados como uma **malha**;
- **SOM** tem uma **taxa de aprendizagem variável** e não **estática como o LVQ**;
- **LVQ necessita do número de _clusters_**, face ao **SOM** que através do seu algoritmo faz o **agrupamento por si** (mapeia).

### _Autoencoders_ (AE)
- É uma **rede não supervisionada** que através da **retropropagação aprende**, assemelhando-se a uma MLP;
- Usamos como **valores desejados os mesmo valores de entrada**;
- Os valores de entrada, $d{_i}$ são utilizados como etiquetas desejadas à saída, $x{_i}$ , ou seja, $x{_i}=d{_i}$;
- Os valores $\hat{x_{i}}$ são as estimativas produzidas pela rede;
- Quanto mais **bem treinada estiver a rede**, **mais próximos os** valores de $\hat{x_{i}}$ estão de $x_{i}$;
- Ao aprender os **dados de entrada** e simultaneamente estar a ser **alvo de uma redução no número de neurónios** na camada escondida, a rede é forçada a **fazer compressão da informação**;
- Esta compressão poderá **remover ruído presente nos dados**;
- Um AE pode ser utilizado para criar **novas representações dos dados** (mais compactas), como se pode ver na figura abaixo.


---
# Aula 5
> [name=pdpm19] Livro sec. 7
## Erro de Generalização
### Objetivo da Aprendizagem
- Queremos que a nossa RN tenha o **menor erro possível em novos dados**, que provenham duma distribuição idêntica à utlizada pelos dados de treino;
- Um classificador com erro no conjunto de treino teria que decorar as classes (usar uma tabela), mas obviamente **não iria generalizar** bem.

### Conjuntos de Treino e de Teste
- Para se saber o erro de generalização, divide-se o conjunto de dados em 2 subconjuntos: conjunto de treino e teste;
- **Conjunto de treino** é utilizado para **treinar o classficador**;
- **Conjunto de teste** é utilizado para estimar o **erro de generalização do classficador**.

### Erro de Treino e Teste
- O erro medido em cada um dos conjuntos anteriores é **erro de treino** e **teste**;
- O **erro de treino** é utilizado para **guiar o processo de aprendizagem**;
- O **erro de teste** é a **estimativa do erro de generalização**;
- Quando se inicia o treino, ambos erros decrescem, mas após algum tempo, o erro de teste poderá começar a aumentar, mesmo que o erro de treino vá diminuíndo. Quando isso acontece, estamos perante o **_overfitting_**.

### _Overfitting_
- Acontece quando a RN **memoriza os padrões de treino e perde assim a capacidade de generalizar**;
- Os pesos da RN estão em excesso relativo aos que seriam necessários para aprender o problema;
- A **RN memoriza** portanto a **informação do conjunto de treino (inclusive ruído)**.

#### Como Evitar o _Overfitting_
- Existem várias formas de evitar _overfitting_ através de **regularização**:
- Utilizar uma RN de dimensões apropriadas face ao problema -> utilizar a arquitetura da rede mais apta;
- Parar o treino antes de o _overfitting_ ocorrer (_early-stopping_) -> evita que o treino se prolongue demasiado;
- Fazer alterações à função de custo.
- O uso de um **conjunto de validação** também ajuda.

#### Conjunto de Validação
- Estimando o **erro do conjunto de validação** conseguimos obter que quando **este aumenta**, o **treino deve de parar**;
- Este é utilizado, pois durante o treino não se pode utilizar informação do conjunto de teste.

#### Validação Cruzada (CV)
- A _Cross Validation_ é uma forma de obter estimativas do erro de generalização;
- Consiste em dividir o total dos dados em $k$ dobras (_folds_) disjuntas obtidas de forma aleatória (faz _k-fold CV_);
- Na imagem acima temos $k = 3$, onde as regiões a vermelho são o conj. de treino e as a amarelo o conj. de teste;
- Para cada classficador, neste caso temos 3, obtemos a estimativa do erro de generalização, testando a respetiva área amarelo;
- Por fiz, faz-se a média das $k$ estimativas do erro para assim podermos obter a estimativa final do erro de generalização;
- Consegue lidar bem com problemas com poucos dados;
- Pode ser apresentada indicando quantos pontos se deixa nos conjuntos de teste (_leave-p-out CV_);

#### Amostras Estratificadas
- A **amostragem estratificada** garante que a proporção das **classes nos conjuntos se mantém igual**, em cada experiência ($k$), à **proporção original presente nos dados**;
- Dá portanto uma estimativa mais realista do desempenho do classificador;
- Imaginando que temos um problema de classificação binário, numa experiência podemos ter uma distribuição $50/50$, mas noutra $10/90$. Isto numa seleção aleatória dos padrões.

## Construção da Rede
### Arquitetura da Rede
- Sabemos que devemos de colocar **um neurónio para cada classe do problema na camada de saída**;
- Também uma rede com 2 camadas escondidas é suficiente para qualquer problema (devemos sempre tentar com 1 camada e se não for suciente migrar para 2 camadas);

#### Nº de Neurónios na Camada Escondida
- Não existe fórmula mágina para calcular o número de neurónios na camanda escondida, sendo que existem 2 abordagens que nos podem ajudar:
- **Abordagem Construtiva**:
- Começar com um nº pequeno de neurónios na camada escondida e vai-se progressivamente aumentando o seu nº até que o erro de validação não decresce;
- É mais atrativa computacionalmente pois começamos com rede menores;
- É mais fácil, à partida, especificar um valor inicial de neurónios.
- **Abordagem Demolidora (_pruning_):**
- Começar com um nº de neurónios elevado e vai-se reduzindo o seu nº até que o erro de validação pare de decrescer;
- Computacionalmente mais exigente, pois começamos com redes enormes;
- À partida é dificil especificar um valor inicial de neurónios.

### Neuroevolução

- Consiste em **cruzar** a **computação evolucionária com as redes neuronais**, para que assim se possa fazer **evoluir potenciais redes para resolver um dado problema**;
- Continua a ser computacionalmente exigente.

### Inicializar Pesos
- A descida do gradiente é sensível aos valores iniciais dos pesos;
- Uma posição inicial próxima de um mínimo apresenta uma convergência rápida;
- Uma posição inicial numa região plana ou com pouco declive apresenta uma convergência muito lenta;
- É sugerido, utilizar pesos no intervalo $[-1/a, 1/a]$

### Codificação das Saídas da Rede
- Tendo em conta que um problema com $L$ classes deve ser resolvido por uma rede com $L$ neurónios na camada de saída, implicando assim que um vetor $y$ de saída contenha $L$ componentes;
- Este vetor vai depois ser mapeado para as $L$ classes através de um codificador 1-em-$L$, onde das $L$ possíveis saídas apenas uma deve conter o valor $1$ e as restantes o valor $0$;
- Na figura abaixo podemos observar que exisitam $L=3$, pelo que após a codificação das saídas, as classes passaram a ser representadas por vetores e não por números inteiros.

## Dados: questões práticas
### Aumento do Número de Dados
- Por norma quantos mais dados (conjunto de treino maior), mias informação terá a rede para aprender, obtendo melhores resultados;
- Por vezes é humanamente impossível etiquetar um conjunto de dados de milhares ou milhões de exemplos;
- Criamos então **novos dados a partir dos existentes**, para que assim o conjunto de treino aumente também;
- Esta criação de novos dados deve-se à aplicação de transformações aos dados;
- No exemplo de dados em imagens, podemos aplicar:
- rotações à imagem;
- alterações aleatórias às cores;
- fazer _flip_ horizontal e vertical à imagem;
- aplicar ruído aleatório à imagem.
- No exemplo abaixo, a partir de 1 imagem, gerou-se 35 novas imagens.

### Normalização dos Dados
- As características do nosso problema podem provir de sensores diferentes, com diferentes grandezas;
- Estas características com valores em escalas diferentes levam a que a sua influência na rede seja diferente (valores maiores influênciam);
- Deve-se portanto **normalizar as características para que todas estejam compreendidas na mesma gama de valores**;
- Pode-se fazer utilizando uma das seguintes possibilidades:
- Mudar de uma escala linear para valores que se encontrem no intervalo [-1,1];
- Obrigar as características a terem valor médio e variância unitária.
:::info
A gama [-1,1] permite-nos utilizar pesos relativamente pequenos
:::

### Valores em Falta
- Por vezes os dados fornecidos podem conter alguns valores em falta de características, $NaN$;
- Pode acontecer por vários motivos;
- As possíveis soluções são:
- remover o padrão em que existem valores em falta;
- substituir o valor em falta pela média dos valores (caso estes sejam contínuos) ou pelo valor mais frequente (caso sejam discretos).

### Codificação dos Valores
- Características não numéricas, p.ex. $N$ profissões, têm de ser representadas através de características binárias.
- No exemplo abaixo temos $N = 3$ características, onde foram codificadas para que apenas uma delas valha $1$ e as restantes $0$.

### _Outliers_
- Um **_outlier_ é um padrão cujas características se desviam grandemente das apresentadas pelos restantes padrões**;
- Podem levar a rede a fazer ajustes nos **pesos de grande amplitude**, podendo alterar significativamente o **resultado da aprendizagem**.

- Estes podem ser removidos através:
- Remover os _outliers_ antes do início do treino;
- Com a desvantagem de poder remover alguns pontos que aparentemente são _outliers_ (falso-positivo).
- Modificar a função de erro, que limite assim o efeito de erros muito elevados \begin{equation}e_{p} = \begin{cases}(d_{p}-y_{p})^2 & (d_{p}-y_{p})^2 < \alpha \\ \alpha \end{cases} \end{equation} onde $\alpha$ é um valor máximo a aceitar para o erro de um ponto.
---

# Aula 6
> [name=pdpm19] Livro sec. 8
## Computação Evolucionária (CE)
- Esta simula a abordagem no âmbito dos problemas de pesquisa (**só os indivíduos mais aptos é que sobrevivem e estes combinam os seus cromossomas através da reprodução**);
- Por vezes existem mutações que de forma aleatória alteram os cromossomas;
- Estas mutações podem ser negativas ou positivas;
:::info
Aprender a jogar o _Hill Climb_ através de várias gerações/populações $\rightarrow$ lembra-te do _Code Bullet_.
:::
- Qualquer algoritmo desenvolvido dentro da CE é um Algoritmo Evolucionário (AE);
- Consiste num algoritmo que de certa forma faz uma **pesquisa estocástica por uma solução ótimo de um problema**;

## Componentes dum AE
- Elementos que influenciam o AE são:
- Codificação das soluções do problema como **cromossomas**;
- Função que avalia a **aptidão** dos indivíduos;
- **Inicialização** da população;
- Operadores de **seleção**, do qual permite seleccionar certos indivíduos;
- Operadores de **reprodução**, do qual permite juntar $2$ indivíduos para dar $1$.

### Cromossomas
- Cada **indivíduo**, da população, **representa uma possível solução do problema**;
- As **características de cada indivíduo** são representadas por **um cromossoma**;
- As características podem ser divididas em:
- **Genótipos**: descreve a composição genética de um indivíduo como foi **herdada dos seus progenitores**;
- **Fenótipos**: guarda os traços comportamentais de um indivíduo **aprendidos no seu ambiente**.

#### Representação do Cromossoma
- Cada **cromossoma** é visto como **um ponto no espaço de pesquisa**, sendo este constituído por um conjunto de **genes**;
- Cada **gene** representa **uma característica** do indivíduo, sendo o seu valor chamada de **alelo**;
- Cada gene representa um parâmetro a otimizar;
- No exemplo dos retângulos, em 2D, e caso queiramos colocar 8 retângulos no retângulo maior:
- Temos 2 coordenadas (x,y do centro) para otimiar (características);
- A sua orientação (vertical ou horizontal);
- Temos então 8 * (2 + 1) = 24 parâmetros a otimizar (genes).
- A eficiência da pesquisa depende da forma de representar o cromossoma;
- Formas de representar o cromossoma:
- **Algoritmos Genéricos (AGs)** utilizam **_strings_ binárias**, suportanto no entanto variáveis reais;
- **Programação Genética (PG)** utiliza **árvores**;
- **Estratégias Evolucionárias** utiliza **variáveis reais**.
- No exemplo dos retângulos, cada cromossoma pode ser representado como vetor com $24$ números reais, ou $16$ reais e $8$ _bits_ ($1$ _bit_ para indicar a orientação).

### Função de Aptidão
- Serve para **mapear um cromossoma num número real**: \begin{equation} F_{ap}: C \rightarrow R \end{equation} onde $R$ representa o conjunto dos números reais e $C$ o espaço dos cromossomas.
- Esta função diz-nos qual é a **qualidade de um determinado cromossoma** (quão perto está ele da solução ótima);
- É de extrema importância, devendo **conter todos os critérios a serem otimizados**;
- Deve também conter as **restrições**;
- No exemplo dos retângulos:
- Critério principal a otimizar: nº de retângulos B dentro de A;
- Restrições:
- Não podem estar parcialmente nem totalmente sobrepostos;
- Têm que ficar contidos em A.

### População Inicial
- A população inicial tem os seus genes **inicalizados por valores aleatórios**;
- Conhecimento **_à priori_** é benéfico para criar **mais genes em regiões que se crê existir boas soluções para o problema** (mas **pode levar ao aparecimento de ótimos locais**);
- O seu tamanho inicial implica:
- **População Pequena:** custo computacional baixo em cada geração, mas vai **necessitar de muitas gerações para convergir**;
- **População Grande:** custo computacional elevado em cada geração, mas em princípio **necessita de menos gerações para convergir**;
- De forma a ficar no meio das duas abordagens atrás, se aplicarmos uma taxa de mutação elevada....

### Operadores Evolucionários
- Existem 2 tipos de operadores:
- Seleção;
- Reprodução.

#### Operadores de Seleção
- **Cada geração produz novos indivíduos**, necessitamos de uma forma de **selecionar quais os melhores a serem mantidos para gerações futuras**;
- Ao passarem só os melhores, damos **mais relevância** aos que se encontram mais perto da **solução ótima**;
- Devemos também escolher quais se vão reproduzir, através de _cross-over_ ou de mutação.

##### Seleção aleatória
- Escolhemos um sub-conjunto da geração atual ao acaso (ex.: Temos 100 indivíduos e escolhemos 10 ao acaso);
- **Não tira partido da função de aptidão**.

##### Seleção proporcional
- Fazemos agora seleção, mas de **forma proporcional ao valor da função de aptidão** (ex.: Escolhemos os 10 indivíduos, mas estes serão os mais aptos deste conjunto de 10);
- A **probabilidade** de um invidíduo ser selecionado será tanto **maior quanto maior for o valor de função de aptidão para o seu cromossoma**;
\begin{equation}P(C_{i}) = \frac{F_{ap}(C_{i})}{\sum_{k=1}^{N}F_{ap}(C_{k})} \end{equation} onde $N$ representa o número de indivíduos nesta geração.
###### Algortimo:
1. Sortear um número, Csi U(0,1);
2. i = 1;
3. s = P(Ci); (= P(1))
4. Enquanto s < Csi
1. i = i + 1;
2. s = s + P(Ci); (= s + P(1))
5. O cromossoma escolhido é o i

###### Exemplo:
|$i$ | 1 | 2 | 3 |
| --- | --- | --- | --- |
|$P(i)$ |0.5 |0.2 |0.3 |
1. $\xi = 0.62$
2. $i = 1$
3. $s = P(C_{i}) = P(i) = P(1) = 0.5$
4. $0.5 < 0.62$, sim
1. $i = i + 1 == 2$
2. $s = s + P(2) = 0.5 + 0.2 = 0.7$
5. $0.7 < 0.62$, não
6. Número escolhido será o $i = 2$

##### Seleção por torneio
- São selecionados $k$ indivíduos de forma aleatória;
- Dentro desse grupo, será **escolhido o melhor indivíduo** ($> F_{ap}$);
- Vantagens:
- Os piores indivíduos não são escolhidos;
- O melhor indivíduo não vai dominar (nota que não é escolhido o melhor da geração, mas sim do subconjunto);

##### Seleção baseada em ordenação (_rank_)
- **Ordenamos os cromossomas** pelo seu **valor de aptidão** (do menor para o maior);
- A probablidade de seleção fica **menos dependente** do valor da **função de aptidão**, importando só a ordem dos cromossomas;
- **Evita que um cromossoma** com valor de aptidão muito elevado **domine o processo de seleção**;
\begin{equation} P(C_{i})=\frac{R(C_{i})}{\sum_{k=1}^{N}R(C_{k})} \end{equation}

###### Exemplo:
- No exmplo abaixo é possível notar-se no domínio que o $C_{1}$ tem na sua probabilidade de ser selecionado através de uma seleção proporcional. O mesmo não ocorre na seleção ordenada.

F: 5, 2, 3

|F | R | P |
|---|---|---|
|2 | 1 | 0.5 |
|3 | 2 | 0.3333|
|5 | 3 | 0.1666|

##### Seleção por elitismo
- Escolher **os melhores indivíduos de uma geração** para passarem para a seguinte, **sem sofrerem alteração por mutação**;
- Quantos **mais indivíduos forem escolhidos, menor será a variabilidade**.
- Se tivermos 100 indivíduos e 50 foram gerados, mas só 100 passam para a seguinte geração, pegamos nos 150 e desses escolhemos os melhores 100;

##### Seleção da população da nova geração
- Escolher os $k$ melhores: garante que a **aptidão da próxima geração não será menor que a geração seguinte**;
- Escolher os $k$ indivíduos através dos métodos vistos atrás.

#### Operadores de Reprodução
- Tem como objetivo a **obtenção de novos indivíduos a partir de indivíduos préviamente selecionados**;
- **_Cross-over_**: criação de um novo indivíduo a partir dos genes dos progenitores;
- **Mutação:** criação de novos indivíduos a partir de indivíduos existentes;
- As mutações devem de ocorrer com baixa probabilidade (não é benéfico alterar grande parte da informação genética).

## Algortimo Evolucionário Genérico
- Critérios para convergência são variados;
- Como se atinge convergência:
- Parar quando for atingido o número máximo de gerações definido _à priori_;
- Parar quando se encontrar uma solução aceitável;
- Para quando a aptidão (máximo ou média) não variar, entre 2 ou mais gerações consecutivas;
- Parar se a mudança nos cromossomas for reduzida (em várias gerações consecutivas).
### Algoritmo
1. Inicializar o contador de gerações g=1;
2. Inicializar a população Cg com N indivíduos;
3. Enquanto não houver convergência fazer:
3.1 Avaliar a função de aptidão para cada indivíduo da população;
3.2 Efetuar Cross-over;
3.3 Efetuar Mutações;
3.4 Selecionar a nova geração;
3.5 Fazer g = g + 1 e voltar a 3.

### CE vs Otimização Clássica

---
# Aula 7
> [name=pdpm19] Livro sec. 9 & 10
## Algoritmos Genéticos (AGs)
- Permitem resolver **problemas de otimização codificando soluções em cromossomas**.

## Representação dos Cromossomas
### Variáveis com Valores Binários
- Representação original para os cromossomas.

### Variáveis com Valores Nomiais
- Informação to tipo nomial, p. ex. {advogado, professor, outra}, tem de ser passado para uma _string_ binária (advogado = 00, professor = 01, outra = 10);
- Tendo $N$ valores, temos que os codificar em $2^N$.

### Variáveis com Valores Reais
- Variáveis reais tem de ser mapeadas em _strings_ binárias;
- Uma variável $z$ que varia entre $[z_{min}, z_{max}]$ e representada por 16 _bits_ temos que seguir a fórmula: \begin{equation}z_{bin}=(2^{16}-1)\frac{z-z_{min}}{z_{max}-z_{min}}\end{equation}
- Exemplo:
- $[40,250]$;
- $z=160$;
- $z_{bin}=(2^{16}-1)\frac{160-40}{250-40} = 37449 \rightarrow 1001001001001001$
### Problemas com a Codificação Binária
- Dois números consecutivos variam em muitos _bits_;
- Por norma utiliza-se a Distância de _Hamming_, que faz uma contagem do número de _bits_ que diferem entre dois números;
- Exemplo:
- Distância entre $3$ e $4$;
- $d_{Hamming}(011,100)=3$

#### Código _Gray_
- Números consecutívos diferem apenas de $1$ (relativa à distância de _Hamming_);
- Código _Gray_, vê os _bits_ diferentes, pelo que a representação de números consecutivos difere sempre em 1:

|Decimal | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|
|Binário | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 |
|_Gray_ | 0000 | 0001 | 0011 | 0010 | 0110 | 0111 |

\begin{equation}
g_{i} =
\begin{cases}
b_{1} & i=1 \\
b_{i-1} \overline{b_{i}} + \overline{b_{i-1}}b_{i}
\end{cases}
\end{equation}

:::info
Binário para Gray Code
https://www.youtube.com/watch?v=cbmh1DPPQyI&ab_channel=TheOrganicChemistryTutor
:::

## _Cross-Over_
- Produz descendentes a paritr de progenitores selecionados;

### Algoritmo
1. Criar 2 novos cromossomas inicializados com o material genético dos pais, alpha = Ci1 e beta = Ci2 (Ci1 e Ci2 são os progenitores);
2. Achar a máscara m;
3. Para cada gene j do cromossoma, se mj = 1, trocar o material genético:
3.1 alphaj = Ci2,j;
3.2 beta = Ci1,j.
4. Devolver os descendentes alpha e beta.
### Máscara
- Especifica quais os genes alvo de troca durante o _cross-over_;
- Pode ser calculada:
- uniforme;
- um ponto;
- dois pontos;
- aritmético.

### _Cross-Over_ Uniforme
- A máscara é criada de forma aleatória;
- _bit_ a $1 \rightarrow$ alelo deve ser trocado;
- _bit_ a $0 \rightarrow$ alelo não é trocado;

#### Algoritmo
1. mi = 0, i = 1,....,N (N = nº de genes);
2. Para cada gene i
2.1 Obter Csi U(0,1);
2.2 Se Csi < p então mi = 1 (p é a probabildade de cross-over)

### _Cross-Over_ num Ponto
- A máscara é criada escolhendo $1$ ponto no cromossoma de forma aleatória, onde todos os pontos a partir desse serão trocados (inclusive).

#### Algortimo
1. mi = 0, i = 1,....,N (N = nº de genes);
2. Obter Csi UI(1, N)
3. Para cada i >= Csi,..., N fazer mi = 1


### _Cross-Over_ em dois Pontos
- A máscara é criada escolhendo $2$ pontos no cromossoma de forma aleatória, onde todos os pontos nesse intrevalo serão trocados (inclusive).

#### Algortimo
1. mi = 0, i = 1,....,N (N = nº de genes);
2. Obter Csi1 e Csi2 UI(1, N), Csi1 < Csi2
3. Para cada i no [Csi1 e Csi2] fazer mi = 1

### _Cross-Over_ Aritmético
- Utilizado quando os genes tem **valores reais**;
- Geramos os descendentes $\alpha_{i}$ e $\beta_{i}$ dos progenitores $C_{i1}$ e $C_{i2}$
\begin{equation} \alpha_{i,j}=\xi_{1}C_{i1,j} + (1-\xi_{1})C_{i2,j}\end{equation}
\begin{equation} \beta_{i,j}=(1-\xi_{2})C_{i1,j}+\xi_{2}C_{i2,j}\end{equation}
onde $\xi_{1}, \xi_{2} \sim U(0,1)$
- Exemplo:
- $C_{i1,1} = 74.20$;
- $C_{i2,1} = 71.30$;
- $\xi_{1} = 0.22$;
- $\xi_{2} = 0.51$;
- $\alpha_{i,1} = 71.94$;
- $\beta_{i,1} = 72.72$.

## Mutação
- Introduz novo material genético num indivíduo de forma aleatória;
- Taxa de mutação, $p_{m}$, deve de ser um valor baixo para não distorcer as boas soloções encontradas;
- Pode-se também começar com um valor elevado e faz-se o decrescer de forma exponencial com as gerações.

### Mutação Aleatória
- As variáveis a codificar são binárias.
#### Algoritmo
1. Para cada i = 1,..., N de Cj:
1.1 Obter Csi U(0,1);
1.2 Se Csi <= pm fazer Cj,i = negação(Cj,i)

### Mutação _inorder_
- Escolher 2 posições aleatoriamente, e apenas os _bits_ entre elas é que poderão sofrer mutação.

#### Algoritmo
1. Obter Csi1 e Csi2 U(1,N) e Csi1 <= Csi2;
2. Para cada i = Csi1,...., Csi2 fazer:
2.1 Obter Csi U(0,1);
2.2 Se Csi <= pm fazer Cj,i = negação(Cj,i).

### Mutação para Variáveis não Binárias
- **Valores nomiais** obrigam a que os operadores de mutação sejam modificados de forma a que os $D$ _bits_ representados sejam aleatoriamente substituídos por outros $D$ _bits_ que representem um valor válido diferente;
- Variáveis com **valores reais**, a mutação ocorre através da **adição de um valor aleatório** (utilizamos a distribuição Gaussiana).

#### Algoritmo para alelos reais
1. Para cada gene real j fazer:
1.1 Obter Csi U(0,1)
1.2 Obter um valor eta N(0, sigma^2) (signa^2 é inversamente proporcional à aptidão do indivíduo)
1.3 Se Csi <= pm fazer Cij += eta
## Programação Genética (PG)
- É uma especialização dos AGs;
- Esta representa os indivíduos através de árvores (face aos AGs que utilizam uma _string_);
- Cada indivíduo é um **programa executável**.

### Representação dos Cromossomas
- Cada cromossoma é representado na forma de uma árvore.

#### Gramática
- Necessitamos de definir dois conjuntos:
- **terminal**:contém todas as variáveis e constantes;
- **funções**: contém todas as funções aplicáveis ao conjunto terminal.
- As folhas da árvore $\rightarrow$ elementos do conjunto terminal;
- Os nós da árvore $\rightarrow$ elementos do conjunto das funções.

##### Exemplo
- Programa $y = x*ln(a)+sin(z)/exp(-x)-3.4$
- Conj. terminal = $\{x,a,z,3.4\}$;
- Conj. funções = $\{+,-,*,/,ln(),sin(),exp()\}$

#### Representação
- **Espaço de pesquisa**: são todos os programas que podem ser gerados a partir da gramática definida para o problema;
- **Objetivo**: encontrar qual cromossoma se aproxima mais da função desejada;
- As árvores tem tamanhos:
- fixo: profundidade igual para todas;
- variável: é definida apenas uma profundiade máxima.

#### População Inicial
- É gerada aleatoriamente, mas obdece às restrições impostas pela gramática e pela profundidade máxima;
- O nº de filhos da raiz e restantes nodos não terminais são dados pelo nº de parâmetros que a função requer;
-
##### Exemplo
- Dados: $\{x,a,z,3.4\}, \{+,-,*,/,ln(),sin(),exp()\}$
- Com a sequência 7,8,1,8,2,1,4;
- Obtemos: $y = \frac{x}{x/a}*3.4$;


### Funções de Aptidão
#### Avaliação da Aptidão
- **Avalia o programa**, requerendo assim que o **programa corra com diferentes parâmetros**;
- A **média dos resultados da aptidão** do indivíduo em cada execução é utilizada para **medir a aptidão**;
- A aptidão de um indivíduo pode ser alvaliada executando o programa em todos os padrões do conjutno de dados e **medindo o erro quadrático médio nesse conjunto**.

#### Penalização
- Pode incorporar **termos que permitam penalizar determinadas propriedades não desejadas**;
- Por exemplo, podemos penalizar árvores que tenham elevado grau (muitos filhos).

### _Cross-over_
#### 1 filho
- Seleciona-se aleatoriamente um nodo em cada progenitor e a sub-árvore de um dos progenitores substitui a do outro a partir dos nodos selecionados.

#### 2 filhos
- Seleciona-se aleatoriamente um nodo em cada progenitor e as respetivas sub-árvores são trocadas.


### Mutação
- Temos o seguinte programa: $y = exp(3.4*a)+ \frac{a}{z}$

#### Mutação de Nodos Funcionais
- É selecionado um nodo funcional e este é substituído por um da mesma aridade.


#### Mutação de Nodos Terminais
- Idêntico ao anterior, mas substitui as folhas por um elemento do conjunto terminal.

#### Mutação por Troca
- São trocados os elementos de um nodo funcional.


#### Mutação por Crescimento
- É selecionado um nodo e substituído por uma sub-árvore gerada aleatorimente;
- A nova sub-árvore tem algura máxima limitada.

#### Mutação Gaussiana
- Um nodo terminal, que representa uma constante é escolhido ao acaso e o seu valor é substituído pela sua soma mais outro valor proveniente de uma distribuição Gaussiana.


#### Mutação por Truncatura
- Um nodo funcional é substituído por um nodo aleatorio do conjunto terminal;
- Permite encurtar a árvore.