Newer
Older
Unito / anno3 / apprendimento_automatico / preparazione.org
Francesco Mecca on 14 Jul 35 KB yes
* Esposito
** Tasks: Binary Classification
I modelli predittivi si occupano di inferire delle informazioni sulle
nuove istanze di problemi in base ai dati gia` consumati
*** Geometric classification 
Lo spazio delle istanze solitamente ha una struttura geometrica. Su
due o tre dimensioni e` facile visualizzare un classificatore che si
basi su questa struttura.
Quando esiste un boundary lineare fra le classi del dataset diciamo che i dati
separabili linearmente.
Il problema e` con i dati sparsi e con quali metriche decidiamo come
tracciare il boundary. Quando usiamo il margine ci riferiamo alle SVM.
Anche il KNN sfrutta il concetto geometrico di distanza.
*** Probabilistic classifier
Stima probabilita` dai dati e fornisce predizioni usando la seguente
regola:
- $Y_{map} = arg max_{Y}P(Y|X) = argmax_Y\frac{(P(X|Y)(PY)}{P(X))} =
  argmax_Y\frac{(P(X|Y)(PY)}{P(Y))}$
- $Y_{ml} = argmax_YP(X|Y)$ (se priori non importanti)
*** Features
Se vogliamo approssimare la funzione coseno e` inutile considerare
un'approssimazione lineare (y=0).
Pero` possiamo usare x come sia come splitting feature (due
approssimazioni diverse se x<0 o x≥0) e come variabile di regression
(l'approssimazione contiene x)
Delle volte si puo` mappare il feature space su nuovi spazi (e.g.:
scatter plot: renderlo al quadrato)
** Classification
ĉ: X → C
C = {C₁, C₂, ..., Cₖ}
example: <x, c(x)>
Learning is constructing ĉ 
*** Decision Tree
Un feature tree e` un albero sui quali nodi mappo ogni feature e
sulle foglie le classi delle istanze con quelle features.
Su ogni foglia posso considerare una classe (ad esempio usando la
majority rule) e costruire un classificatore che usi l'albero per
classificare le istanze. Si dice decision tree.
La ~contingency table~ si usa in statistica per visualizzare la
distribuzione delle variabile. Nel caso di un classificatore e` utile
per visualizzare la quantita` di istanze misclassificate e predette
correttamente: colonna (Predicted{⊕,⊖}), riga (Actual{⊕,⊖}).
*** Misure
- Accuracy:  $acc = \frac{1}{|T_e|}\sum I[\hat{c}(x)=c(x)] = P(\hat{c}(x) = c(x))$
- Error rate: $1-acc = P(\hat{c}(x) \ne c(x))$
- class ratio, clr: $\frac{Pos}{Neg} = \frac{\sum_{x\in{T_e}}
  I[c(x)=1]}{\sum_{x\in{T_e}} I[c(x)=0]}$
- recall, true positive rate: $\frac{TP}{Pos} = P(\hat{c}(x) =
  \oplus|c(x) = \oplus)$
- specificity, true negative rate = $\frac{TN}{Neg} =
  P(\hat{c}(x) = \ominus|c(x) = \ominus)$
- false positive, false negative = 1-tnr, 1-tpr
- Precision, confidence = $\frac{TP}{TP+FP} = P(c(x) =
  \oplus|\hat{c}(x) = \oplus)$
- Average recall: $\frac{Tp/Pos + Tn/Neg}{2}$
*** Coverage plot e roc plot
Tool per comparare la performance di piu` classificatori.
Possiamo mappare i 4 gradi di liberta` della contingency table: Pos,
Neg, TP, FP.
- coverage plot: y = Pos, x = Neg
- roc plot: y = tpr, x = fpr
Su entrambi un punto (un classificatore) e` indicato dal y = TP e x =
FP (rate nel caso del ROC).
Nel coverage plot:
- cᵢⁱ collegati da slope = 1 → accuracy
- parallela a diagonale → avg recall
Nel roc plot:
- Neg/Pos slope → accuracy
- parallela a diagonale → avg recall
*** Scoring Classifier
mapping ŝ: X → Rᵏ dove s e` un vettore s(x) = (s₁(x),
s₂(x), ..., sₖ(x)). i-th componente = score della classe Cᵢ
Nello scoring tree, in caso di classificazione binaria, si possono
usare nelle foglie il logaritmo del ratio fra lo score delle classi.
**** Margine e Loss f
Prendiamo la classe true come +1:
- z(x) = c(x)ŝ(x)
Il margine e` il valore assoluto della predizione, positivo se giusta,
negativo se errata.
La Loss function L(z(x)): R → [0, ∞); L(0) = 1 e L(z<0)≥1 e
L(z>0)∈[0,1)
La loss function e` importante nella fase di learning per cercare la
soluzione ottimale
- 0-1 Loss
- Hinge Loss
- Logistic Loss
- Exp Loss
- Squared Loss
**** Ranking
Una funzione di scoring puo` essere trasformata in una di ranking
ordinando le istanze in base allo score ottenuto.
Ranking-Error quando $\hat{s}(x)<\hat{s}(x') \wedge s(x') < s(x)$
- $\frac{\sum_{x\in{T^+_e},x'\in{T^-_e}}{I[\hat{s}(x) < \hat{s}(x')] +
  I[\hat{s}(x) = \hat{s}(x')]}}{Pos\cdot Neg}$
- Ranking accuracy: 1 - Rank-Err
*** Probability Estimator
Scoring classifier che per ogni classe restituisce la probabilita` che
l'istanza appartenga a quella classe
- p̂: X ↦ [0,1]²
- ∑ᵢᵏ p̂(x) = 1
- Squared Error: 1/2 ‖p̂(x) - Iᶜ⁽ˣ⁾‖₂² = ∑ᵢᵏ (p̂(x) - I[c(x) = Cᵢ])²
- Mean SE: 1/|Te| ∑ₓSE(x)
- Squared Error: $SE(x) = \frac{1}{2} \Vert \hat{p}(x) - I_{c(x)} \Vert
  ^2_2 = \frac{1}{2}\sum_{i=1}^{k}(\hat{p}(x) - I[c(x) = C_i])^2$
- Mean Squared Error: $MSE(T_e) =
  \frac{1}{|T_e|}\sum_{x\in{T_e}}SE(x)$
- Empirical Probability: Vettore dato dal numero di istanze sul totale
  per ogni classe (frequenza)
Solitamente si applica un coefficente di smoothing per queste
frequenze
- Laplace correction: $\dot{p_i}(S) = \frac{n_i+1}{|S|+k}$
- m-estimate: non uniform smoothing dato da pseudo-counts m e prior
  probs πᵢ $\dot{p_i}(S) = \frac{n_i+m\cdot\pi_i}{|S|+m}$
*** Beyond Binary Classification
Vedi 1-vs-rest, 1-vs-1 e cosi` via
- 1-vs-rest: solitamente il singolo classifier vede un dataset
  sbilanciato anche se il dataset originale e` bilanciato
- one-vs-one: 0 agli esempi delle classi non considerato; problematico
  quando pochi esempi
Output code deconding: output del classificatore: vettore w: riga
della matrice la cui distanza e` minore da w e` la classe risultante.
** Regression
Il regressor, chiamato anche function estimator, e` un mapping
| f̂: X → R
Gli esempi ∈X sono <x, f(x)> e il ruolo del regressor e` quello di
imparare la funzione. Si noti che ora il target ha risoluzione
infinita e quindi per evitare overfitting gli esempi vanno considerati noisy.
*** Overfitting, bias-variance
L'overfitting si evita avendo un numero di parametri ben piu` basso
dei data points.
Con un numero basso di parametri si introduce un bias che spesso anche
con un training elevato non si riesce a risolvere.
Invece con molti parametri si introduce una forte dipendenza dal test
set e quindi molta varianza.
- $E[(f(x)-\hat{f}(x))^2] = Bias^2(\hat{f}(x)) + Var(\hat{f}(x))$ 
Dim: (Var = E[x²] - E[x]²)
Loss of regressor: E[(fₓ-f̂ₓ)²]
| E[(fₓ-f̂ₓ)²] = E[f²ₓ - 2fₓf̂ₓ + f̂²ₓ] = f²ₓ - 2fₓE[f̂ₓ] + E[f̂²ₓ] =
|               f²ₓ - 2fₓE[f̂ₓ] + E[f̂²ₓ] - E[f̂ₓ]² + E[f̂ₓ]² =
|               { f²ₓ - 2fₓE[f̂ₓ] + E[f̂ₓ]² } + { E[f̂²ₓ] - E[f̂ₓ]² } =
|                (fₓ - E[f̂ₓ])²              +  Var(f̂ₓ)
|               Bias²(f̂ₓ) + Var(f̂ₓ)
** Descriptive Learning
Tasks and learning problem coincide. No separate training set, produce
a descriptive model of the data at hand. Learn a model describing the
data.
*** Clustering
Obbiettivo: trovare gruppi omegenei, trovare una labelling function da
dati senza label.
- q̂: X ↦ C (predictive)
- q̂: X ↦ L (descriptive)
*** Supervised subgroup discovery
Preso un dataset labelled (xᵢ, l(xᵢ))ⁱ trova:
- ĝ: D → {true, false}
- G = {x∈D | ĝ(x) = true}, la cui class distribution e`
  diversa marcatamente dalla popolazione originale
Solitamente un algoritmo di subgroup discovery:
- preferisce sottogruppi grandi
- sono solitamente simmetrici
*** Association Rules
Dato un dataset unlabelled D trova:
- un set di regole {b→h} tale che:
  + h solitamente e` soddisfatta quando b lo e`
  + b∪h e` frequente (high support: %n di elementi soddisfano la
    regola)
- Il powerset di un insieme di regole frequenti e` frequente a sua
  volta.
- Confidenza: support(a∪b)/suport(a)
** Models
*** Linear Models
**** Best fitting line
Problema di regressione: Least Squares
Cx + D = y
X w = y in matrix form, w = (C D)ᵀ
Se X quadrata e full rank: w = X⁻¹·y ma generalmente X non e`
invertibile 
| Errore: ‖e‖₂ = ‖y-p‖₂ = sqrt (∑ᵢ(yᵢ-pᵢ)²)
Possiamo inquadrare questo problema come un problema di minimizzazione
della norma di e; p = X·ŵ: L'intero problema consiste in:
| $minimize_{\hat{w}}\Vert X \hat{w} - y \Vert_2^2$
| minimize_ŵ ‖Xŵ-y‖²₂
La soluzione consiste nell'imporre l'ortogonalita` di e e C(X), ovvero
Xᵀ·e=0; quindi:
| Xᵀ·e = 0; e = y-X·ŵ
| Xᵀ(y-X·ŵ) = 0
| Xᵀy = XᵀXŵ
| ŵ = (XᵀX)⁻¹Xᵀy (LSE)
**** Regularization
Evitare l'overfitting applicando dei constraint sul weight vector.
Generalmente i pesi di w sono in media piccoli: ~shrinkage~.
La versione regolarizzata di LSE:
| w* = argmin_w (y-X·w)ᵀ(y-X·w) + λ‖w‖₂
Soluzione:
| ŵ  = (XᵀX + λI)⁻¹Xᵀy   (trick di I: aumenta stabilita` inversione)
si dice ~ridge regression~ e significa aggiungere λ alla diagonale di
XᵀX per migliorare la stabilita` numerica dell'inversione
Si puo` anche usare ~lasso~ nel caso di soluzioni sparse
(least absolute shrinkage and selection operator)
che sostituisce ‖w‖₂ con ‖w‖₁=∑|wᵢ|
| w* = argmin_w (y-X·w)ᵀ(y-X·w) + λ‖w‖₁
Minimizzare la norma significa immaginare che X sia affetto da errore
D e minimizzare l'errore:
| (X+D)w = Xw + Dw
Inoltre significa imporre un bias e quindi minimizzare l'effetto della
varianza dell'errore. LSE suscettibile alle piccole variazioni nei dati:
unstable regressor.
**** LSE per la classificazione
| ĉ(x) = 1 se xᵀŵ - t > 0 
| ĉ(x) = 0 se xᵀŵ - t = 0 
| ĉ(x) = -1 se xᵀŵ - t < 0 
Ovvero si rappresenta la classe positiva come 1 e la negativa come -1
t rappresenta gli intercepts.
ŷ = β̂₁x + β̂₀
β₁ e` la slope, β₀ l'intercept.
** SVM
Hyperplane:
| y = ax + b 
| y -ax -b = 0
| Aᵀx = 0
- A = (-b -a 1)ᵀ *x* = (1 x y)ᵀ
- Functional margins: soluzioni che non fanno errori
- Geometric margins: soluzioni che massimizzano la distanza fra i piu`
  vicini punti di classe opposta
*** Margine funzionale
Valore dell'hyperplane al punto xᵢ:
| f(xᵢ) = w·xᵢ-t
possiamo usare f(xᵢ)>0 per discriminare fra classe positiva/negativa
- Functional margin:
  | μ(xᵢ) = yᵢ(w·xᵢ-t) = yᵢf(xᵢ)
  se l'esempio e` ben classificato: μ(xᵢ) > 0
*** Support Vectors
Possiamo richiedere che ogni istanza nel dataset soddisfi:
| yᵢ(w·xᵢ-t)≥ 1
Istanze nel decision boundary (chiamate ~support vectors~):
| yᵢ(w·xᵢ-t) = 1
*** (w₀,w₁) ortogonali
La linea discriminante si trova all'intersezione del piano con z=0.
Il piano ha equazione: w₀x + w₁y + w₂z + d = 0
La linea ha equazione: w₀x + w₁y + d = 0
∀r₁,r₂ ∈ linea: (w₀,w₁)·(r₁-r₂) = 0
r₁ = (x₁, -(w₀x₁ + d)/w₁)
r₂ = (x₂, -(w₀x₂ + d)/w₁)
*** Ottimizzazione:
Margine geometrico: μ/‖w‖
e` invariante rispetto al rescaling dei parametri e quindi ci da una
modo di massimizzare il margine.
(x₊-x₋)·$\frac{w}{\Vert{w}\Vert}$
Margin size:
| μ = (x₊-x₋)·w/‖w‖
| x₊·w-t = 1 -> x₊·w = 1+t
| -(x₋·w-t) = 1 -> x₋·w = t-1
| $\mu = \frac{1+t-(t-1)}{\Vert{w}\Vert} = \frac{2}{\Vert{w}\Vert}$
μ va massimizzato, il che significa minimizzato ‖w‖
| $minimize_{w,t} \frac{1}{2}\Vert{w}\Vert^{2}$
| yᵢ(w·xᵢ-t)≥1; 0≤i≤n
minimizzaₓ: f₀(x)
soggetto a: fᵢ(x) ≤ 0     i = 1, ..., m
            gᵢ(x) = 0     i = 1, ..., p
Formulazione duale di Lagrange:
| g(α, υ) = infₓ ⋀(x,α,υ) = infₓ(f₀(x) + ∑₁ᵐαᵢfᵢ(x) + ∑₁ᵖυᵢgᵢ(x))
Nel caso della SVM:
| ⋀(w, t, α₁,...,αₙ) = 1/2 ‖w‖² - ∑αᵢ(yᵢ(w·xᵢ-t) - 1) =
|                    = 1/2 w·w  - w·∑αᵢyᵢxᵢ + t·∑αᵢyᵢ + ∑αᵢ
dobbiamo prendere l'infimum rispetto a w e t della lagrangiana 
e settarle a 0:
| d⋀/dt = ∑αᵢyᵢ = 0  ;  d⋀/dw = w - ∑αᵢyᵢxᵢ = 0
tornando alla lagrangiana:
| g(α) = -1/2 ∑ᵢ∑ⱼαᵢαⱼyᵢyⱼxᵢxⱼ + ∑αᵢ
| maximize_α -1/2 ∑ᵢ∑ⱼαᵢαⱼyᵢyⱼxᵢxⱼ + ∑αᵢ
| subject to αᵢ≥0 ∧ ∑yᵢαᵢ = 0
La soluzione e` sempre un algoritmo numerico.
Abbiamo imparato che:
- w e` combinazione lineare dei support vectors
- positive Lagrange multipliers associato a SV:
  + KKT: αᵢ(yᵢ(w·x-t)-1) = 0
- sia learning che classification e` compiuto in termini di
  dot-product
- possiamo usare i kernel nella formulazione duale
Duality: forma organizzata per per formare bound non triviali in un
problema di ottimizzazione
In problemi convessi il bound e` solitamente ~strict~ e massimizzare
il bound porta alla stessa soluzione che minimizzare la funzione
originale: ~strong duality~.
KKT conditions needs to hold for strong duality. 
**** Margin errors
Massimizzare 2/‖w‖ equivale a minimizzare ‖w‖²/2.
Si possono introdurre errori nei margini attraverso delle ~slack
variables~:
| minimizza_{w, t, ε} 1\2 ‖w‖² + C∑εᵢ
| soggetto a yᵢ(w·xᵢ-t)≥1-εᵢ  ;   εᵢ≥0
| ⋀(w,t,εᵢ,αᵢ,βᵢ) = 1/2 ‖w‖ + C∑εᵢ - ∑αᵢ(yᵢ(w·x-t) - (1-εᵢ)) - ∑βᵢεᵢ
|                 = ⋀(w,t,αᵢ) + ∑Cεᵢ - ∑αᵢεᵢ - ∑βᵢεᵢ =
|                 = ⋀(w,t,αᵢ) + ∑εᵢ (C - αᵢ - βᵢ)
Impostando la derivata su epsilon a 0:
| ⋀(w,t,εᵢ,αᵢ,βᵢ) = ⋀(w,t,αᵢ)    (C-α-β = 0)
ovvero
| maximize_α -1/2 ∑ᵢ∑ⱼαᵢαⱼyᵢyⱼxᵢxⱼ + ∑αᵢ
| subject to C≥αᵢ≥0 ∧ ∑yᵢαᵢ = 0         ———> Cambia C≥α≥0 invece di α≥0
C e` un parametro definito dall'utente: maggiore C maggiore la
penalita` per il margin error. Con C basso possiamo avere un numero
minore di support vectors e quindi ridurre la complessita` della SVM.
** Kernels
Trick usato per adattare degli algoritmi lineari a ipotesi non
lineari.
Idea: linear decision surface su uno spazio trasformato puo`
corrispondere ad una superficie non lineare sullo spazio originale.
Esempio:
| ϕ(x) = (x₁², sqrt(2)x₁x₂, x₂², c)
| ĉ(x) = sign(w·x-t)
| ĉ(x) = sign(K(w,x)-t) = sign(ϕ(w)·ϕ(x)-t)

Una kernel function K: V×V→R per la quale esiste un mapping ϕ:V→F, F
spazio di Hilbert, tale che:
K(x,y) = <ϕ(x), ϕ(y)>
Ovvero una kernel function calcola l'inner product di x e y dopo
averli mappati su un nuovo spazio di Hilbert (possibilmente highly
dimensional)

Restituiscono un intuizione della similarita` (proporzionalmente)
**** Mercer condition 
Come ci si assicura che una funzione K(x,y) che implementa una
similarita` fra x e y sia un kernel valido?
Ovvero, come ci si assicura che ci sia uno spazio di Hillbert H tale
che K permetta di calcolare il dot product in H?
Condizione di Mercer:
- K is a valid kernel iff ∀{x₁, ..., xₘ} the matrix ~K~ is symmetric
  and positive semi-definite
(~K~ is defined as Kᵢⱼ = K(xᵢ, xⱼ))
POSITIVE SEMIDEFINED MATRIX:
| ∀z: zᵀKz≥0
| zᵀKz = ∑ᵢ∑ⱼzᵢzⱼKᵢⱼ = ∑ᵢ∑ⱼzᵢzⱼK(xᵢ,xⱼ) = ∑ᵢ∑ⱼzᵢzⱼ<ϕ(xᵢ),ϕ(xⱼ)> =
|        ∑ᵢ∑ⱼ<zᵢϕ(xᵢ),zⱼϕ(xⱼ)> = <∑ᵢzᵢϕ(xᵢ),∑ⱼzⱼϕ(xⱼ)> = <∑ᵢzᵢϕ(xᵢ),∑ᵢzᵢϕ(xᵢ)> ≥ 0

**** Inner product
generalizzazione del dot product su piu` spazi.
| Simmetrico: <x,y> = <y,x>
| lineare sul primo argomento: <ax+by,z> = a<x,z> + b<y,z>
| definito positivamente: <x,x>≥0; <x,x> = 0 ⇔ x = 0
Comodi perche`:
- linear classifier possono lavorare su problemi non lineari
- similarity function in highly dim. space senza calcolare i feature
  vectors
- composizione, nuovi kernel da vecchi

**** Kernel importanti
Polinomiale:
K(x,y) = (x·y)ᵈ or K(x,y) = (x·y+1)ᵈ
- d = 1 → identity
- d = 2 → quadratic
- feature space esponenziale in d

Gaussian Kernel:
$K(x,y) = exp(-\frac{\Vert{x-y}\Vert^2}{2\sigma^2})$
σ e` deciso tramite cross validation su un altro set indipendente
il feature space ha dimensionalita` infinita.

* Meo
** Concept learning
Assunto base: ogni ipotesi che approssima bene la target function
sugli esempi di training, approssimera` bene anche la target function
con esempi mai visti.
Inoltre D e` consistente e senza rumori ed esiste un'ipotesi h che
descrive il target concept c.
Un'ipotesi h e` una congiunzione di constraint sugli attributi.
- Ipotesi piu` generale:
  siano hⱼ, hₖ due funzioni booleane (ipotesi) definite su X.
  Si dice che hⱼ e` almeno generale quanto hₖ, scritto hⱼ≥hₖ iff
  | ∀x∈X: hₖ(x) = 1 → hⱼ(x) = 1
  La relazione ≥ impone un ordine parziale (rifl, trans, antisimm).
- Version Space:
  Si chiama version space il set delle ipotesi consistenti con il dataset.
*** Algoritmo Find-S
#+BEGIN_SRC
h ← most specific hyp. in H
foreach x∈X:
    foreach aⱼ in h:    (attribute constraint)
    if h(x)⊧aⱼ:
        continue
    else:
        h ← next more general hyp that satisfies aⱼ
output h
#+END_SRC
Advantages:
- Hyp. space defined through conjunction of constraints
- will output most specific hyp. that is consistent
- will be consistent with negative examples as well
Svantaggi:
- non si sa se il learner converge al target concept (non sa se e`
  l'unica ipotesi valida)
- non sa se il training data e` consistente: ignora esempi negativi
*** Version Space
Definiamo il Version Space come:
| VSₕ_D = {h∈H|Consistent(h,D)}
| Consistent(h,D) = ∀<x,c(x)>∈D: h(x) = c(x)
General and specific boundary of VS: set of maximally g/s members
| VSₕ_D = {h∈H| ∃s∈S, ∃g∈G: g≥h≥s}
**** List then Eliminate
#+BEGIN_SRC
Version Space ← list of every hyp. in H
foreach <x,c(x)> in X:
    foreach h in Version Space:
        if h(x) ≠ c(x) : remove h from VS
output VS
#+END_SRC
**** Candidate Elimination
#+BEGIN_SRC
G ← max. general hyp.
S ← max. specific hyp.
foreach d=<x,c(x)> ∈ D:
    if d is ⊕:
        remove from G any inconsistent hyp.
        foreach inconsistent hyp. s in S:
            remove s from S
            add to S all minimal generalizations h of s:
                - h consistent with d
                - some members of G is more general than h
                - S is a summary of all members cons. with positive examples
            remove from S any hyp. more general than other hyp. in S
    if d is ⊖:
        remove from S any inconsistent hyp.
        foreach inconsistent hyp. g in G:
            remove g from G
            add to G all minimal specialization h of g:
                - h consistent with d
                - some members of S is more specific than h
                - G is a summary of all members cons. with negative examples
            remove from G any hyp. less general than other hyp. in G
#+END_SRC
- converge allo stesso VS qualsiasi l'ordine iniziale di D
- puo` convergere a VS diversi se non ci sono abbastanza membri nel
  training set
**** Inductive Leap
Assumiamo che H contenga il target concept c. Ovvero che c puo` essere
descritto tramite una congiunzione di literals.
Unbiased learner: H esprime ogni concetto imparabile, ovver
Powerset(X).
S e G sono i due insiemi ⊕  ⊖ (con congiunzioni logiche, vedi slides).
Futile perche` un learner che non fa assunzioni a priori
sull'identita` del target concept non ha basi per classificare istanze
mai viste.
- Bias induttivo:
  | ∀xᵢ∈X: (B ∧ D_c ∧ xᵢ) ⊧ L(xᵢ,D_c)
  L(xᵢ, D_c) e` la classificazione assegnata dal concept learning
  algorithm L dopo il training su D_c
  B set minimo di asserzioni
  Permette di trasformare un sistema induttivo in deduttivo
** Trees
I decision tree sono molto espressivi e corrispondono a proposizioni
logiche in DNF.
Per evitare l'overfitting bisogna scegliere un linguaggio
restrittivo per le ipotesi e penalizzando la complessita` di ogni
ipotesi nella funzione target.
*** Feature tree
Nei feature tree ogni nodo interno e` segnato con una feature e ogni
arco con un literal.
L'insieme dei literals in un nodo e` chiamato ~split~.
Dalle foglie possiamo costruire un'espressione logica tramite
congiunzione dei literals risalendo alla root.
Il set di istanze coperto dall'espressione e` chiamato ~instance space
segment~.
Tree learners eseguono una ricerca top-down di tutti i concetti.
*** Algoritmo Grow Tree
Procedura generica
- Homogeneous: D → bool; true if hom. enough to be labelled with a
  single label
- Label: D → label; most appropriate label for a set of instances
- BestSplit: D×F → set of literals; best set of literals to be put at the
  root of the tree
#+BEGIN_SRC
Input: Dataset D, set of features F
if Homogeneous(D) then return Label(D)
S ← BestSplit(D, F)
split D in Dᵢ secondo i literals in S
foreach i do:
    if Dᵢ ≠ ∅ then Tᵢ ← GrowTree(Dᵢ, F)
    else Tᵢ is a leaf labelled with Label(D)

return tree whose root is labelled with S and whose children are Tᵢ
#+END_SRC

*** Purity
La bonta` di uno split e` determinata dalla purezza.
Per esempio nel caso di due classi ⊕ e ⊖, la purezza puo` essere
definita partendo dalla probabilita` empirica.
La purezza misura i figli negli alberi, in rule learning la purezza e`
di un solo figlio il literal e` true. Si possono usare le purity
measure degli alberi ma senza bisogno di fare la media.
In the case of classes definiamo l'impurity come una di queste funzioni:
| minority-class, anche error rate: min{p̣, 1-p̣}
| Gini-index: ∑p̣ᵢ(1-p̣ᵢ); expected error rate if examples on leaves were labelled randomly
| Entropy: -∑p̣ᵢ·log₂(p̣ᵢ)
Impurity of a set: $Imp(D_1, D_2, ..., D_l) = \sum_{j=1}^l
\frac{|D_j|}{|D|} Imp(D_j)$
*** Decision Trees
Separa il dataset in partizioni disgiunte usando l'objective function
(ogni partizione e` pura nel suo target attribute).
L'objective function misura la purezza delle partizioni ottenute dopo
lo split.
- Information of an event
I(E) = log₂(1/p)
Se un evento e` molto probabile (p≊1), l'informazione che ne ricaviamo e`
poca, e viceversa.
Se un esperimento ha n outcomes ognuno con probabilita` pᵢ la
quantita` di informazione media ricavata e` esattamente l'entropia:
| ∑pᵢlog₂(1/pᵢ) = -∑pᵢlog₂(pᵢ)
MAIN TAKEAWAY: information gain = entropia
**** BestSplit-Class Algorithm
#+BEGIN_SRC
input: dataset D, set of features F
Iₘᵢₙ ← 1
foreach f∈F:
    split D into subsets D₁,...,Dₗ secondo i valori υⱼ of f
    if Imp({D₁, ..., Dₗ}) < Iₘᵢₙ:
        Iₘᵢₙ ← Imp({D₁, ..., Dₗ})
        f_{best} ← f
return f_{best} (feature f to split on)
#+END_SRC
Il best split minimizza l'impurita` dei subset D₁, ..., Dₗ.
*** Ranking Trees
- Spazio diviso in segmenti
- Gli alberi possono diventare rankers se imparano un ordinamento per
  i segmenti
- Le foglie devono essere ordinate
Sfruttando la distribuzione delle classi nelle foglie possiamo
trasformare il feature tree in:
1. ranking tree: se ordiniamo le foglie in base alle probabilita`
   empiriche: curva di slope p̣/(1-p̣) -> convessa sul ROC plot
2. probability estimator: si calcola la prob. in ogni foglia, usando smoothing
3. classifier: scegliendo le condizioni operative come conseguenza
   della proporzione della frequenza sulle classi:
   + clr = Pos/Neg (class ratio)
   + c = Cfn / Cfp (cost ratio)
   + slope: 1/(c·clr)
*** Prune Tree
Pruning puo` rovinare l'accuracy. Essere sempre guidati da clr e c.
- PruneTree(T,D)
#+BEGIN_SRC
inputs: decision tree T; labelled data D
for every INTERNAL node N ∈T, partendo dal basso:
Tₙ ← subtree of T with N as root
Dₙ ← {x∈D | x is covered by N}
se l'accuracy di Tₙ su Dₙ e` peggiore della majority class in Dₙ :
    sostituisci Tₙ in T con una foglia marcata con la maj. class di Dₙ

ritorna versione pruned di T
#+END_SRC
Invece di fare pruning si puo` introdurre un'errore di
generalizzazione (penalita` k su foglie) calcolato sul training set.
Non viene generata una foglia se non decrementa l'errore del padre di
almeno k+1.
TODO: Vedi come vengono stimati gli errori di generalizzazione sul
libro
TODO: dimostrazione sqrt gini
TODO: vedi conseguenze inflation
*** Regression Trees
Possiamo inquadrare il problema del tree learning come un problema di
minimizzazione della varianza (o standard deviation nel caso di sqrt
GINI) sulle foglie:
| Var(Y) = 1/|Y| ∑(y-y̱)²     y̱ e` y_predict
l'average della varianza e` la varianza moltiplicata per la
frequenza (|Yⱼ|/|Y|).
- Nei problemi di regressione i valori del dominio di Y sono continui
- in BestSplit possiamo sostituire l'impurezza con la varianza
  + Label(Y) = mean value dei valori di Y raccolte dalla foglia
  + Homogeneous(Y) = true se la varianza e` sotto la soglia
- i regression tree son suscettibili all'overfitting in caso di pochi
  esempi
*** Clustering Trees
- usiamo Dis: X×X ↦ R
- BestSplit usa l'average di Dis su ∀x₁,x₂
- Dissimilarity: 1/|D|² ∑∑Dis(x₁,x₂)
- nel caso di vettori di features X⊆Rᵈ la somma della varianza sulle
  features puo` essere interpretata come la distanza euclidea media fra
  vettori nello spazio multidimensionale.
- Complessita`:
  + average squared distance = 2 volte la varianza
  + Var(x)
  + average vector delle distanze e Varᵢ(X)
  + O(|D|)
Note:
- Cluster piccoli: overfitting 
- outliers possono essere rimossi
- si possono rimuovere degli splits nei livelli piu` bassi
  dell'albero: ~pruning~
- label attraverso most representative instance: medoid (lowest total
  dissimilarity)
** Rules
Ordered rules are a chain of /if-then-else/.
#+BEGIN_SRC
1. Keep growing the rule antecedent by literal conjunction (high purity)
2. Select the label as the rule consequent
3. Delete the instance segment from the data, restart from 1
#+END_SRC
Rules evaluated in order.
Nei decision tree la purity si riferisce ad entrambi i figli e siamo
interessati alla goodness di tutto lo split.
Nei rule learners la purity che ci interessa e` solo quella per cui il
literal e` true. No need for average.
*** LearnRuleList
learn an ordered list of rules
- LearnRuleList:
#+BEGIN_SRC
Input: Labelled training dataset D
R ← ∅
while D ≠ ∅ :
    r ← LearnRule(D)
    append r to end of R
    D ← D \ {x∈D | x is covered by r}
return R
#+END_SRC
- LearnRule(D):
#+BEGIN_SRC
b ← true
L ← set of available literals
while not Homogeneous(D):
    l ← BestLiteral(D,L)      ;; like highest purity
    b ← b ∧ l
    D ← {x∈D | x is covered by b}
    L ← L \ {l'∈L | l' uses same fetures as l}
C ← Label(D)
r ← if b then Class = C
return r
#+END_SRC
*** Unordered rules
Rules can also refer to the same class and we can collect them in a
rule set.
- LearnRuleSet(D):
#+BEGIN_SRC
Input: Labelled training data D
R ← ∅
for every class Cᵢ :
    Dᵢ ← D
    while Dᵢ contains examples of class Cᵢ:
        r ← LearnRuleForClass(Dᵢ, Cᵢ)
        R ← R ∪ {r}
        Dᵢ ← Dᵢ \ {x∈Cᵢ | x is covered by r} ;; remove only positives
return R
#+END_SRC
- LearnRuleForClass(Dᵢ, Cᵢ):
  Stesso che LearnRule(D) ma usa Cᵢ invece che C←Label(D).
Il problema con queste regole e` che si concentrano troppo sulla
purezza quando ci sono regole quasi pure che pero` non possono essere
generalizzate: usa lo smoothing.
- Laplace correction: $\dot{p}_i^+ = \frac{n_i^+ + 1}{n_i + 2}$
Solitamente rulesets hanno una performance di ranking maggiore (n
contro 2ⁿ istanze riconoscibili) ma possono restituire una curva di
coverage non convessa.
** Subgroup discovery
I sottogruppi sono un subset dell'instance space la cui class
distribution e` differente da quella di D.
Mapping ĝ: X → {true, false}; D = (xᵢ, l(xᵢ))ⁱ
Precisione e average recall non sempre coincidono sulla
classificazione dei sottogruppi:
- Precision: focalizzato sui positivi
- avg recall: no fuoco
Nella subgroup discovery siamo interessati a imparare piu` di una
regola per individuare un gruppo omogeneo:
- Weighted covering: Si da un peso ad ogni esempio e lo si riduce ogni
  volta che si trova una regola che lo copre.
*** Item Sets
We say that a set of items covers a transaction.
- Itemset: set of items che appartengono alla stessa transazione
- frequent ItemSet: alto supporto (maggiore di threshold)
- maximal itemset: IS al bordo, ¬∃I⊆Iₘ | support(I) > t
- closed IS: ¬∃I⊆Iₛ | f(I) = f(Iₛ) (same support)
Quando li ritorno:
- frequent: alto volume, no information loss
- maximal: basso volume, information loss

Si possono anche rappresentare su una matrice.
Se plotto l'item set come un albero, vediamo che il supporto muovendoci
verso i livelli piu` bassi e` monotonico.
Questo significa che aggiungere elementi ad un item set puo` solo che
rendere il numero di transazioni coperte uguale o minore.
Il set dei frequent items set e` convesso, ovvero:
| ∀S₁,S₂: S₂⊆S₁, ∀Sₓ: S₂⊆Sₓ⊆S₁ ∧ Sₓ ∈ Convex Set
- FrequentItems
#+BEGIN_SRC
Input: D⊆X; threshold f₀
M ← ∅
Q = { {} }
while Q ≠ ∅:
    I = pop(Q)
    max ← true
    foreach superset I' of I:
        if Supp(I') > f₀:
            max ← false
            Q.append(I')
    if max = true:
        M ← M ∪ I
return M
#+END_SRC
Possiamo costruire association rules dagli IS.
#+BEGIN_SRC
Inputs: D⊆X ; f₀ (threshold for support) ; c₀ (confidence threshold)
R ← ∅
M ← FrequentItems(D, f₀)
foreach m ∈ M:
    foreach h⊆m and b⊆m such that h∩m=∅:
        if support(b∪h)/support(b) ≥ c₀ then R←R∪{if b then h}
return R
#+END_SRC
**** Post processing of association rules
Stage to filter superfluos rules which don't have more confidence than
general case.
- lift (if b then h) = n·supp(b∪h)/(supp(b)supp(h))
a lift of 1 means that b and h have no interaction (statistically
independent), so we are
interested in association rules of lift > 1.
** Distance models
La distanza e` una misura di similarita`: minore la distanza, maggiore
la similarita`.
Se X∈Rᵈ definiamo la Minkowsi distance: $Dis_p(x,y) =
(\sum_{j=1}^{d}{|x_j-y_j|^p})^{\frac{1}{p}} = \Vert{x-y}\Vert_p$ (‖z‖
e` la p-norm).
- Se p = 2 -> distanza euclidea.
  | Dis₂(x,y) = sqrt ((x-y)ᵀ(x-y))
- Manhattan:
  | Dis₁(x,y) = ∑|xⱼ-yⱼ|
- Chebyshev: $Dis_{\infty}(x,y) = max_j|x_j-y_j|$
- 0-norm:
  | ∑ I[xⱼ≠yⱼ]
- Jaccard distance for aysmmetric problems
- Mahalanobis (elliptical?): $Dis_M(x,y|\sum) = \sqrt{
  (x-y)^T\sum^-1(x-y) }$
  Dis₂ = Disₘ quando ∑ e` l'identity matrix. Normalmente ∑ e`
  l'inverso della matrice di covarianza: M = ∑⁻¹.
- La distanza di Mahal. tiene conto della distanza fra le features e
  grazie a ∑ riduce le distanze nella direzione di spread.
Generalizzando:
Dato un'instance space X una metrica della distanza Dis: X×X→R e` tale
che ∀x,y,z∈X:
- Dis(x,x) = 0
- Dis(x,y) > 0 if x≠y
- Dis(x,y) = Dis(y,x)
- Dis(x,z) ≤ Dis(x,y) + Dis(y,z) (no detours)
*** Distanze e medie
Si dimostra (slide 343) che μ e` il punto nello spazio Euclideo che ha
∑distanza minimo.
Il centroide rispetto al medoide puo` anche essere un punto fittizio.
Un classificatore lineare molto basico si puo` costruire classificando
ogni istanza.
*** KNN
A KNN cls takes a vote for each of the k nearest exemplars and
predicts the class.
In pratica il cls prendere k voti dai piu` vicini. All'aumentare di K
aumenta il bias e diminuisce la varianza. Con basso k sono simili ad aggregatori.
Non efficienti negli spazi con molte dimensioni.
I voti possono anche essere pesati in base alle distanze.
*** DBScan
Usare NN non per la predizione ma per la classificazione.
- Density: numero di punti nel raggio ~Eps~
- Core point: ha minimo ~MinPts~ nel raggio (interior del cluster)
- Border point: meno di MinPts punti in Eps, ma vicino di CorePoint
- Noise point: ne` border point ne core point.
#+BEGIN_SRC
Label all point as Core, Border, Noise
Elimina i Noise points
Metti un arco fra i core-points nel raggio Eps l'uno dall'altro
- ogni gruppo di punti connessi e` un cluster
Assegna ogni Border point ad un cluster
#+END_SRC
Buono per classificare cluster di differente grandezza e forma.
Non funziona bene sulle densita` variabili e sui punti ad alta
dimensionalita`.
*** Misure
- Coesione: quanto gli oggetti son closely related nel cluster
- Separazione: quanto distinto o ben separato il cluster dagli altri
Dato Sum of Squared Error
- Within cluster Sum of Squares: $WSS = \sum_i \sum_{x\in
  C_i}(x-m_i)^2$
- Between cluster Sum of Squares: $BSS = \sum_i |C_i|(m-m_i)^2$
BSS + WSS e` costante (Varianza). Il problema dei K-Means consiste nel trovare
una soluzione che minimizza WSS (o massimizza BSS): cluster coesi.
*** Algoritmo di Lloyd
- Itera partizionando in base al centroide e ricalcola il centroide.
- Converge ad un punto stazionario ma non garantisce che la soluzione
  sia il minimo globale.
- KMeans(K,D) usando Dis₂
#+BEGIN_SRC
Input data D⊆Rᵈ; numero di cluster k.
Inizializza casualmente K vettori μ₁, ..., μₖ ∈Rᵈ
do:
    assegna ogni x∈D a argminⱼ Dis₂(x,μⱼ)
    for j = 1 to k:
        Dⱼ ← {x∈D| x assigned to cluster j}
        μⱼ = 1/|Dⱼ| ∑x    (x∈Dⱼ)
until (no change in μ₁, ..., μₖ
ritorna μ₁, ..., μₖ
#+END_SRC
*** K-Medoids clustering
#+BEGIN_SRC
Input: input data D⊆X; k \#clusters; Distance metric Dis: X×X→R
Inizializza casualmente k punti μ₁, ..., μₖ ∈D
repeat
    assign each x∈D to argminⱼ Dis(x,μⱼ)
    for j=1 to k do:
        Dⱼ ← {x∈D| x assigned to cluster j}
        μⱼ = argmin_{x∈Dⱼ} ∑_{x'∈Dⱼ} Dis(x,x')
until no change in μ₁, ..., μₖ
return μ₁, ..., μₖ
#+END_SRC
*** Proximity graph for measuring clusters (Silhouettes)
- a(xᵢ) = distanza media di xᵢ da punti del cluster di appartenenza
- b(xᵢ) = distanza media di xᵢ da punti del cluster vicino
non e` garantito che a << b.
| (b(xᵢ) - a(xᵢ)) / b(xᵢ)   → indica quanto ben clusterizzato sia xᵢ
- Silhouette
| (b(xᵢ) - a(xᵢ)) / max(a(xᵢ), b(xᵢ))    (garantisce normalizzazione anche quando a >> b)
Maggiore s(xᵢ) meglio clusterizzato xᵢ
*** Hierarchical clustering
Non richiede di fissare k.
Il ~dendrogram~ e` un albero binario con gli elementi di D come
foglie.
- Linkage function: L: 2ˣ×2ˣ→R: calcola la distanza fra due subset
  dell'instance space data una metrica per la distanza.
  + Single linkage: smallest pairwise distance fra elementi
  + Complete linkage: largest pointwise distance
  + Average linkage: average pointwise distance
  + Centroid linkage: distanza fra i centroidi
- HAC(D, L)
#+BEGIN_SRC
Input: D⊆X; linkage function L
Inizializza clusters di singleton
creae una foglia a livello zero per ogni punto
repeat:
    trova la coppia <x,y> con il minore linkage e merge
    genera parent di <x,y>
until si ottiene un solo cluster
return constructed dendrogram
#+END_SRC
** Kernels
Disₖ(x,y) = sqrt K(x,x) + 2K(x,y) + K(y,y)
| pseudo metric quando k e` un kernel semidefinito
- Kernelized K-Means
#+BEGIN_SRC
inputs: D⊆X; k
randomly initialize D₁, ..., Dₖ; (D₁ ∪ ... ∪ Dₖ = D)
repeat
    assign each x to argminⱼ 1/|Dⱼ| ∑_y Disₖ(x,y)
    for j = 1 ... k:
        Dⱼ ← {x∈D | x assigned to cluster j}
until no change in D₁,...,Dₖ
return D₁, ..., Dₖ
#+END_SRC
- Cosine similarity: $cos \theta = \frac{x\cdot y}{\Vert{x}\Vert \cdot
  \Vert{y} \Vert} = \frac{K(x,y)}{\sqrt{K(x,x)\times K(y,y)}}$
** 5-cross validation
dividi il dataset in 5 partizioni, 4 per il training set 1 per il test
set e permuta.


* Domande
hⱼ ≥ hₖ
iff
∀x∈X hₖ(x) = 1 → hⱼ(x) = 1

** FindS
h ← ipotesi piu` specifica in H
foreach x ∈X:
    foreach aⱼ (constraint):
         if h(x) ⊧ aⱼ:
             continue
         else:
             h ← generalizza aⱼ in h

** List-then-eliminate
VS = {h | h e` consistenti}

foreach x∈X:
    foreach h ∈VS:
        if h(x) ≠ c(x):
           rimuovi h da VS

** Candidate eliminatio
G = {g | g e` piu` generale}
S = {s | s e` piu` specifico}

foreach x∈X:
    if x = ⊕:
        rimuovere da G ogni ipotesi incostente con x
        foreach h ipotesi incosistente in S:
            h ← minima generalizzazione consistente con x
            rimuovo da G ogni ipotesi meno generale di h
    if x ⊖:
        rimuovi da S ogni ipotesi incosistente con x
        foreach h ipotesi incosistente in G:
           h ← minima specificazione consistente con x
           rimuove da S ogni ipotesi meno specifica di h

* SVM
Xw + d= y

f(xᵢ) > 0 → x = ⊕
f(xᵢ) < 0 → x = ⊖
μ(xᵢ) = yᵢf(xᵢ)  Positivo quando la classificazione e` corretta

Support vectors: x | μ(x) = 1
(x₊w - x₋w) · 1/‖w‖

x₊w - d = 1     
x₋w - d = -1

x₊w = (1+d)
x₋w = (-1+d)

(1+d+-d+1)/‖w‖  = 2/‖w‖

massimizzare 2/‖w‖ corrisponde a minimizzare 1/2 · ‖w‖ 
minimizzare 1/2 · ‖w‖²
soggetto  yᵢ(xᵢw - d) ≥ 1