<style>
.reveal section img { background:none; border:none; box-shadow:none; }
.reveal {
font-size: 30px;
}
.reveal p {
text-align: left;
}
.reveal ul {
display: block;
}
.reveal ol {
display: block;
}
</style>
<h1> Optimització</h1>
## Taller Nous Usos de la Informàtica
<h1><img width="150" src="https://i.imgur.com/vvZMy0I.png"></h1>
---
## Que és l'optimització?
En matemàtiques, estadística, ciències de la computació o economia, el concepte d'**optimització** correspon al procés de selecció del **millor element** (o conjunt d'elements), respecte d'un **criteri** determinat, entre un conjunt (potser infinit) d'elements disponibles.
Moltes vegades, els problemes d'optimització es redueixen a la cerca del màxim (o el mínim) d'una funció que representa el criteri.
<center><img width="350" src="https://i.imgur.com/LFrS302.png"></center>
---
## Exemples (problemes d'optimització)
<center><img width="500" src="https://hackmd.io/_uploads/HyBkXZula.png"></center>
La funció a minimitzar és el cost total (distància) acumulat de les arestes recorregudes en el tour.
---
## Exemples (problemes d'optimització)
<center><img width="350" src="https://hackmd.io/_uploads/ByHof-ula.png"></center>
<center>Quin problema optimitza?...</center>
---
## Exemples (problemes d'optimització)
<center><img width="550" src="https://hackmd.io/_uploads/HJu2zW7RR.png"></center>
<center>... La predicció de la paraula més probable donat un text.</center>
---
### Mètodes clàssics
+ Per funcions **unimodals** contínues podem usar mètodes basats en la derivada (o el gradient). En aquest cas tenim garanties sobre la solució trobada.
+ Per funcions **multimodals** contínues podem usar mètodes estocàstics basats en les derivades, però no hi ha garanties sobre la solució trobada (pot ser un extrem local).
+ Per funcions **discretes** o amb valors enters, hi ha mètodes específics. Per exemple, l'algorisme del simplex.
+ També hi ha mètodes estocàstics que poden servir per qualsevol tipus de funció. Per exemple, els algorismes **genètics** són una bona solució pel problema TSP.
---
### Les dades
Durant tot aquest curs representarem els **conjunts de dades** de $m$ elements en forma matricial, amb valors definits sobre $n$ **característiques**:
<center><img width="400" src="https://i.imgur.com/jQvsA9K.png"></center>
Suposem de moment que totes les característiques de les dades són numèriques (hi ha mètodes per transformar-les a numèriques quan no ho són).
---
### Quina és la relació entre optimització i dades?
L'objectiu de molts mètodes d'anàlisi de dades és convertir aquesta matriu de dades en un **model**.
Un **model** és una expressió matemàtica $f_w$ que depen d'uns quants paràmetres $w$ i que representa fidelment i de forma compacte algun aspecte de la matriu de dades.
:::info
:bulb: El valor mitjà d'una (o d'un conjunt) característica la representa de forma compacte i aproximada, però és un **estadístic**, no un **model** (perquè no depen de cap paràmetre).
:::
---
### Exemple
Suposem que les nostres dades representen els pisos de Barcelona amb dues característiques, els metres quadrats ($X$) i el preu de venda d'aquests pisos ($Y$).
<center><img width="450" src="https://i.imgur.com/AV8Qv6U.png"></center>
---
### Exemple
Enlloc de tenir una gran taula $D$ amb moltes files, podriem usar un **model linial**, $y=ax+b$, que només depen de 2 paràmetres $a$ i $b$, que representi el preu en funcio dels metres quadrats.
Aquest model pot ser útil per moltes coses. Per exemple, per **predir** el preu d'un pis qualsevol.
---
### Exemple
Evidentment, a la realitat, per trobar un bon model, cal que $X$ representi tots els aspectes relacionats amb el preu d'un pis: barri, alçada, carrer, habitacions, etc, i per tant el model ha de tenir més característiques i conseqüentment més paràmetres:
$$y=a_1x_1+a_2x_2+\dots+a_nx_n+a_{n+1}$$
Els mètodes d'optimització serveixen per buscar els valors dels paràmetres $(a_1,\dots,a_{n+1})$ que minimitzen els errors de representació del model!
---
### Quina és la relació entre optimització i dades?
Per fer-ho seguirem aquest mètode:
+ Definirem una familia de funcions, el **model**, que pugui representar el conjunt de dades. En el nostre exemple triem un model linial $f(x)$ amb dos paràmetres $y = ax+b$.
+ Llavors definirem una **mesura de l'error** que cometem al representar cada fila de la matriu de dades amb aquest model. Per exemple $(a x_i + b - y_i)^2$, on $x_i, y_i$ són dades de la fila $i$ que representen els $m^2$ i el *preu* del pis $i$ (d'un conjunt amb $N$ pisos).
+ Sumarem tots els termes de mesura d'error per obtenir un valor $L(f)$ (que anomenarem **funció de pèrdua**) que representa la "qualitat" del model $f$:
$$
L(f) = \frac{1}{N}\sum_{i \in D} (a x_i + b - y_i)^2
$$
---
### Quina és la relació entre optimització i dades?
<center><img width="650" src="https://i.imgur.com/mFQYqSz.png"></center>
---
### Quina és la relació entre optimització i dades?
+ Finalment, usarem un **algorisme d'optimització** per trobar els paràmetres $a$ i $b$ òptims, és a dir, els que fan que $L$ sigui el més petit possible:
$$
\arg_{min}^{(a,b)} \frac{1}{N} \sum_{i \in D} (a x_i + b - y_i)^2
$$
---
### Quina és la relació entre optimització i dades?
El **model** resultant representa el conjunt de dades des del punt de vista que si sabem els metres quadrats, podem obtenir el preu (aproximat) aplicant una fòrmula, sense necessitat de tenir la taula.
:::info
:bulb: També podriem fer un model per predir els $m^2$ a partir del preu.
:::
---
### Optimització i aprenentatge de dades
:::info
:bulb: **Compte!** Aplicar un algorisme d'optimització directament pot ser perillós: podem trobar un model que aproximi molt bé les dades i que predigui el preu d'un pis que no està al conjunt de dades molt malament.
:::
<center><img width="450" src="https://i.imgur.com/mgCmcoW.png"></center>
Aquest fenòmen es diu sobre-estimació (*overfitting*). Si l'objectiu del nostre model no és simplement **representar** el conjunt de dades sinó que volem **generalitzar** (predir el valor de dades $x$ que no estan al conjunt d'aprenentatge), ho hem de controlar!
---
### Optimització i aprenentatge de dades
En general **aprendre de les dades** vol dir **inferir** (construir de baix cap a dalt, de les dades cap el model) un model que ens permeti representar-les de forma **compacte** i també ens permeti **generalitzar**.
---
### Aprenentatge de dades no supervisat
+ Donat un conjunt de dades $\{\mathbf x_i\}_{i=1,\dots,n}$, volem construir un funció $f$ tal que $\mathbf y_i = f(\mathbf x_i)$ és una representació *compacta* (més simple, de menys dimensions, etc.) del conjunt, que ens permeti realitzar tasques tals com **predir la probabilitat** d'una mostra, **mostrejar** de forma aleatòria elements del conjunt, etc.
+ Per exemple, $\mathbf x_i$ són els pixels d'una imatge de gatets i $f(\mathbf x_i)$ és un model probabilistic que ens pot retornar la $p(\mathbf x_i) \in \mathcal Gat$ o ens pot retornar una imatge d'un gat.
---
### Aprenentatge de dades supervisat
+ Donat un conjunt de dades etiquetades $\{\mathbf x_i,y_i\}_{i=1,\dots,n}$, on la variable $y$ representa una etiqueta o valor d'interès, volem construir un funció $f$ tal que quan rebem una nova dada $\mathbf x_j$, no vista anteriorment, el càlcul de $y_j = f(\mathbf x_j)$ és **probablement correcte**.
+ L'exemple del preu dels pisos vist anteriorment n'és un bon exemple.
---
### El problema de la **sobre-estimació**
La solució del problema de la **sobre-estimació** és usar una metodologia d'aprenentatge adequada durant l'optimització: la **validació encreuada** (*cross-validation*).
Aquesta estrategia consisteix a dividir en dos subconjunts complementaris el conjunt de dades $D$, determinant el model sobre un subconjunt (anomenat dades d'entrenament o *training set*), i validant-lo en l'altre subconjunt (anomenat dades de prova o *test set*).
El model només s'ajusta amb el conjunt de dades d'entrenament i a partir d'aquí calcula els valors de sortida per al conjunt de dades de prova (valors que no ha analitzat abans). Si el resultat sobre les dades de prova no és prou bó, hem de canviar la forma de trobar el model o la familia del model!
---
### Optimització i aprenentatge de dades
Una gran part dels algorismes que "aprenen" de les dades estan basats en la **resolució iterativa** d'un problema d'optimització que construeix un model $f_w$ a partir de les dades seguint els passos que hem vist abans i per tant minimitzant:
$$
\arg_{min}^{w} \frac{1}{N} \sum_{i \in D} (f_w(x_i) - y_i)^2
$$
on $w$ són els paràmetres del model $f$.
Si existís una solució directa (no iterativa) que derivés la fòrmula de la solució, adoptariem aquesta estratègia, però no és el cas...
La metodologia més emprada per resoldre aquest problema és el **descens del gradient** sobre la funció $\frac{1}{N} \sum_{i \in D} (f_w(x_i) - y_i)^2$.
---
### Notebook
https://colab.research.google.com/drive/1gSF8kVQOo3cWs2KskTku8DMosSVypXsD?usp=sharing
{"metaMigratedAt":"2023-06-16T09:54:34.800Z","metaMigratedFrom":"YAML","breaks":true,"slideOptions":"{\"theme\":\"white\",\"transition\":\"fade\"}","title":"Optimització","description":"En matemàtiques, estadística, ciències de la computació o economia, el concepte d’optimització correspon al procés de selecció del millor element (o conjunt d’elements), respecte d’un criteri determinat (amb o sense restriccions), entre un conjunt d’elements disponibles.","contributors":"[{\"id\":\"27c1cf26-ef2c-44cb-8ae1-2edc488d3f8e\",\"add\":14158,\"del\":4888,\"latestUpdatedAt\":1758208468006}]"}