09. Learning

Che cos'è il learning?

E' l'insieme delle tecniche atte a far simulare alle macchine comportamenti umani tramite l'apprendimento.
Ad esempio costruire manufatti parzialmente completi che si completino da soli tramite apprendimento.

L'idea è quella di dotare l'agente1 di alcune competenze base e di meccanismi che permettano di far apprendere l'agente stesso, ma questo problema è di difficile implementazione (ancor più del planning).

Learning deduttivo

Date le conoscenze base più l'esperienza acquisita dall'ambiente deduciamo nuove conoscenze.

Learning induttivo

L'agente è dotato solo di meccanismi per estrapolare regole generali da esempi. Questo parte ad analizzare un set di esempi dati più un set di esempi visti nell'ambiente ed inizia ad indurre regole generali che valgono nell'ambiente in cui l'agente opera. Queste regole diventano parte della conoscenza "certa" dell'agente. Questo tipo di learning è più interessante in quanto l'uomo si muove per induzione.

Indipendenza dal modo di rilevare le informazioni

I tipi di learning prima esposti sono indipendenti dal modo in cui l'agente rileva le informazioni.

Learning deduttivo

Ci riferiamo al sistema AM. AM ha come base conoscitiva i concetti iniziali sulla teoria degli insiemi (espressi tramite lisp). Il meccanismo di apprendimento è fornito da una serie di funzioni (sempre in Lisp) che implementano le regole del libro "HOW TO SOLVE IT" che spiega "come fare matematica". Il libro contiene regole del tipo: "se vale la pena studiare f(x,y) allora è interessante studiare g(x) = f(x,x)".
Am ha riscoperto gli interi, l'addizione (questo sostanzialmente scoprendo che gli insiemi disgiunti sono interessanti, l'unione pure ed anche il conteggio degli elementi) e la moltiplicazione.
Dopodichè il sistema è stato fermato perchè la descrizione delle scoperte di AM era molto prolissa e ciò limitava sia l'uso (la memoria terminava) sia l'interpretazione delle scoperte. Quindi, dopo aver migliorato il sistema di rappresentazione delle regole (e dell'output) di AM per utilizzare meglio la memoria hanno riavviato il sistema che ha scoperto i numeri primi, la congettura di Goldbach, etc..
Am in sostanza genera funzioni Lisp e quelle interessanti le mantiene in memoria.

All'inizio dell'esperimento gli autori non potevano sapere cosa sarebbe successo, quindi c'è stato un vero processo di learning.

Perchè Am funziona? Perchè Lisp, il linguaggio usato per descrivere e far lavorare AM, è molto vicino alla descrizione insiemistica, quindi il sistema lavora con "semplicità" sugli insiemi. Se il linguaggio di rappresentazione dei concetti fosse stato più distante dal dominio (in questo caso gli insiemi) sarebbe stato molto più difficile implementare AM.
Per come è fatto Lisp, inoltre, è facile generare funzioni interessanti compatte, e quindi AM è riuscito a lavorare su queste in tempi ragionevoli. Ovviamente (vale anche per l'uomo) più funzioni interessanti si hanno più il tempo per l'elaborazione aumenta.

Han provato a creare un sistema simile ad AM per la progettazione di circuiti integrati ma l'esperimento è andato male.

Dunque il learning deduttivo, ad oggi, è troppo legato al dominio di applicazione (non si riesce a creare un agente general purpose), quindi sistemi che apprendono in domini generali sono rari. E' possibile crearli su domini ben definiti ma su questi è meno interessante poichè l'uomo vuole aiuto in casi generali o non ben definiti.

Learning induttivo

E' usatissimo in data mining. Si hanno un insieme di esempi classificati e si vuole indurre una regola generale che permetta di classificare correttamente nuovi casi. Ovviamente la regola indotta può non essere corretta sempre, ma l'importante è che funzioni bene sui casi "certi", dati come dataset di apprendimento (training set).

In pratica si accettano anche regole che funzionano in un ampio numero di casi certi, tipo: "la regola funziona per il 95% dei casi certi". Un problema che sorge è stabilire quale sia il concetto di qualità per le regole indotte.
Esempio: vedo 1000 funghi gialli tutti velenosi, con quale affidabilità posso dire che i funghi gialli siano velenosi in generale?

Procedura con cui si apprende una regola: PAC learning

Nota: questa è la procedura con cui si induce una regola, in alternativa si può vedere come "regola" (non indotta, ma data) per apprendere nuove regole.
PAC sta per: probably approximated correct learning.

Data una regola si dice che questa regola è approssimativamente corretta (AC) se è corretta nella maggior parte dei casi. Quindi di contesto in contesto si definisce cosa si intende per "maggior parte", altrimenti la procedura, in generale, potrebbe stabilire soglie non adatte a certi contesti.
Se una regola, in un certo contesto, soddisfa la soglia di errore definita come il rapporto 'casi errati/casi totali' allora in quel contesto la regola è PAC.

Come facciamo a verificare il tasso di errore se non conosciamo tutto il dominio? Ovvero il 'casi totali' è a noi sconosciuto. Si risolve mediante approssimazione statistica.

Definizioni più formali. Regole indotte PAC.

Dato un predicato p(x), sia questo una regola realmente vera per il contesto considerato. Questo predicato definisce un concetto con valenza binaria, cioè un oggetto 'x' può avere la proprietà 'p' oppure no.
Ora sia p_hat(x) la regola indotta tramite learning, definiamo:
err(x) se e solo se p(x) xor p_hat(x)
Ovvero si ha un errore sulla proprietà assegnata ad x se la regola indotta dice il contrario (lo xor è esclusivo, cioè restituisce vero se i valori sono opposti) della regola che è realmente valida.

Possiamo dire che p_hat è una regola indotta (probabilmente2) approssimativamente corretta (pac) con un'accuratezza $\varepsilon$ se è vero che:
$P(err(x)) < \varepsilon \ , \ \forall x \in \mbox{Dominio del problema}$ . (nota: deominio del problema o contesto)

Possiamo riscrivere la formula di sopra come segue. Dato un elemento m del dominio del problema (o contesto), possiamo dire che $P(m)$ è la probabilità che m si verifichi. Ad esempio se il dominio è quello delle previsioni metereologiche, m può essere l'evento "piove".
Ovviamene $\sum_{\forall m \in D} P(m) = 1$. (La probabilità di verificarsi è opportunamente distribuita su tutti gli eventi di D)
Data questa premessa si ha la definizione di regola pac, relativamente alla definizione dell'errore suddetta, come segue:
$\sum_{ \left \{ x | err(x) \right \} \subseteq D } P(x) < \varepsilon \ , \ varepsilon \in (0,1)$ (se epsilon valesse 0 sarebbe la fine perchè non c'è minore o uguale nella formula. Bisognerebbe avere precisione assoluta)
Ovvero che la somma degli elementi che determinano l'errore ha una probabilità cumulata di verificarsi minore di epsilon.

Procedure PAC.

Finora abbiam visto la procedura di learning per regole PAC. Vediamo come funziona su intere procedure.

Una procedura di induzione di regole, detta L, è pac se $P( \ P(err(r)) \ge \varepsilon \ ) < \delta$, ovvero se la probabilità di avere un errore di una regola 'r', indotta dalla procedura, è maggiore o uguale ad epsilon con una probabilità minore di delta. In altre parole, se la probabilità di indurre regole non pac è minore di delta.

Esempi da cui indurre regole pac devono formare un campione rappresentativo.

Se i casi noti su cui si inducono regole non sono un buon campione del dominio del problema, allora le regole indotte possono essere falsate o meglio le procedure di induzione possono essere sbilanciate ad indurre regole non corrette anche se la procedra è buona. Quindi la definizione di prima di procedura PAC è incompleta.
Dobbiamo essere ragionevolmente sicuri che le regole siano indotte su un campione di casi rappresentativo dell'intero dominio. In sostanza la probabilità di estrarre un elemento di tipo 'x' dal campione di casi deve essere all'incirca la stessa della probabilità di estrarre un elemento di tipo 'x' dall'intero dominio.

Limitare la struttura dei concetti imparati (BIAS, Pregiudizio). Forma congiuntiva.

Potremmo limitare la forma dei concetti da indurre. Ad esempio potremmo imparare solo regole in forma congiuntiva (restringendo quindi l'insieme delle regole corrette che possiamo scoprire). Tuttavia anche la sola forma congiuntiva permette di imparare, potenzialmente, $3^n$ regole se 'n' sono i predicati (o concetti) base. Perchè un predicato, in una regola congiuntiva, può esserci, esserci negato o non esserci (quindi ho, per ogni predicato, 3 possibilità e dunque 3 alla n).

Numero minimo di esempi per avere una procedura PAC

Come detto sopra, gli esempi devono essere un campione rappresentativo del dominio. C'è un altro problema, il loro numero. Potrebbero essere in un numero troppo limitato per indurre bene le regole. Quindi quanti esempi dobbiamo avere per avere la certezza che una procedura PAC funzioni (e di contro, avere una buona probabilità di dire che una procedura non è PAC)?
Se avessimo tutto il dominio come training set (insieme di casi d'allenamento) la procedura, nel caso lo sia, sarebbe PAC perchè potrebbe indurre le regole esatte. Ma quando possiamo restringere il training set per mantenere la procedura PAC?

Al minimo una procedura PAC deve classificare correttamente gli elementi del training set (anche nel caso in cui ci sia bias sulla forma delle regole). Quindi ogni procedura migliore quella che rispetta solo il requisito minimo appena espresso, sarà pac.

Probabilità di indurre regole non PAC , definizione formale delle procedure PAC e taglia minima del training set

Dato un concetto qualsiasi 'q' (concetto che tuttavia rispetta la limitazione sulla struttura o più semplicemente il bias), che probabilità c'è che questo concetto soddisfi il traning set, cioè sia valido per il training set, pur essendo questo nella realtà non corretto?

Posto che il training set ha taglia 'm', ovvero ci sono 'm' casi nel training set, la probabilità di indurre un 'q' errato (non pac) è:
$(1-\varepsilon)^m$
Questo perchè se induciamo un q corretto questo soddifa tutti gli m casi con una precisione $> 1 - \varepsilon$ (con la definizione dell'errore suddetta). Quindi per ogni caso la probabilità di sbagliare sarà $< \varepsilon$. La probabilità di non sbagliare sarà quindi $> \varepsilon$. Dunque un 'q' corretto su m casi stocasticamente indipendenti ha probabilità di non sbagliare $> (1-\varepsilon)^m$. Quindi un 'q' incorretto basta che abbia probabilità di non sbagliare uguale (e non maggiore) $(1-\varepsilon)^m$ .

Supponiamo che H sia il numero di concetti potenzialmente apprendibili (che rispettano il bias, che sono composti dai predicati disponibili, etc..) la probabilità di indurre un concetto che verifica il T.S. (training set) ma che non sia PAC è:
$H \cdot (1-\varepsilon)^m$
Ovvero se per ogni concetto ho una probabilità $(1-\varepsilon)^m$, la somma di queste H probabilità (che dà la prob complessiva) sarà giusto $H \cdot (1-\varepsilon)^m$ .

Date le ipotesi sopra espresse, la procedura di induzione di regole è PAC se $( H \cdot (1-\varepsilon)^m ) < \delta$ . Ovvero se la probabilità di indurre regole non pac è minore di delta.

Da qui ricaviamo m ovvero la taglia del training set, così possiamo dimensionare bene il training set per evitare di indurre regole errate. Dalla formula prima scritta si ottiene, usando il logaritmo naturale:

(1)
\begin{gather} m \cdot \log_e (1-\varepsilon) < \log_e \frac{\delta}{H} \end{gather}

Poi divido per $\log_e (1-\varepsilon)$ che è minore di zero (leggi dopo), quindi cambio segno.

(2)
\begin{gather} m \ge \frac{\log_{e}(\frac{\delta}{H})}{\log_{e}(1-\varepsilon)} \ , \ 0<\varepsilon<1 \end{gather}

da cui $\log_{e}(1-\varepsilon)<0$ poichè $0<(1-\varepsilon)<1$.

Si dimostra che $\log_{e}(1-\varepsilon) + \varepsilon<0$. Infatti derivando la formula rispetto ad epsilon si ottiene:

(3)
\begin{gather} - \frac{1}{1-\varepsilon} + 1 = - \frac{\varepsilon}{1-\varepsilon} < 0 \end{gather}

(il '- si ha perchè la variabile compare con il segno meno nel logaritmo ed il log è una funzione composta)
Quindi la derivata decresce. Ma se epsilon all'inizio è quasi 0 allora $\log_{e}(1-\varepsilon)$ è appena negativa, ma con epsilon crescente il valore tenderà a decrescere sempre di più ed inoltre il logaritmo è più veloce, nella decrescita, della epsilon (che è una funzione lineare).

Dalla dimostrazione si ha $\log_{e}(1-\varepsilon) < - \varepsilon$, da cui $\frac{A}{\log_{e}(1-\varepsilon)} > - \frac{A}{\varepsilon}$
Quindi:

(4)
\begin{gather} m \ge \frac{\log_{e}(\frac{\delta}{H}))}{\log_{e}(1-\varepsilon)} \ge \frac{\log_{e}(\frac{\delta}{H}))}{ - \varepsilon } = \frac{\log_{e}(\frac{H}{\delta}))}{ \varepsilon } \end{gather}

l'ultimo passaggio si ha per le proprietà dei log ( $-\log(\frac{a}{b}) = \log(\frac{b}{a})$ ) .

Dunque la taglia minima del training set dipende dalla precisione che si vuole delle regole indotte e dalla taglia dei concetti potenzialmente apprendibili.
Se abbiamo 'n' concetti base ed un bias congiuntivo (tipo a and b ), avremo $3^n$ possibili concetti apprendibili, quindi:

(5)
\begin{gather} m \ge \frac{n}{\varepsilon} \cdot \log_{e}(\frac{3}{\delta}) \end{gather}

In questo caso se volessimo grande precisione nell'induzione di regole, quindi delta ed epsilon piccoli, m sarebbe molto grande.

Se non fosse vera l'ipotesi che il training set sia un buon rappresentante del dominio allora nelle formule precedenti dovrebbero comparire anche le distribuzioni di probabilità di estrarre certi elementi piuttosto che altri.

Valutare la "pacness" di una procedura

Poichè non possiamo, come detto prima, valutare tutto il dominio perchè è troppo grande, rispettando la taglia dell'insieme di esempi calcolata prima creiamo un insieme di esempi già classificati (tramite regole che si sanno essere certe o con analisi ad occhio che però si è certi che funzionano. Analisi date ad esempio da medici, che non conoscono le vere regole del caso ma sanno che c'è un ragionamento non proprio definito che però funziona).
Quindi dividiamo questo insieme in due sottoinsiemi, uno è il training set (T.S.) e l'altro sarà il test set ( testS). Dunque sul T.S. applichiamo al procedura che indurrà le regole, dopodichè per verificare che le regole funzionino3, ovvero che siano pac, si applicano al testS per vedere se la classificazione indotta è in accordo con quella data a priori.

Il problema è che potremmo individuare un cattivo T.S. (non rappresentativo), o ancora l'intero insieme (T.S. unito a testS) potrebbe esser poco rappresentativo dell'intero dominio.

Per minimizzare questo problema si partiziona l'insieme degli esempi in molti modi diversi e poi si verifica che le regole indotte su ogni partizione siano sempre le stesse o quasi.

Algoritmo version spaces

Indica la struttura base degli algoritmi di induction learning.

Supponiamo di voler imparare una regola congiuntiva che descrive le carte da poker. I concetti che descrivono le carte da poker possono essere espressi in un reticolo o poset (partially ordered set). Ad esempio (vediamo parte del poset):

d19.jpg

Poset ordinato secondo l'operatore di inclusizione.

L'algoritmo è incremetale e di volta in volta mantiene un lower bound ed un upper bound in base agli esempi che trova.
L'upper bound è il concetto meno specifico consistente con l'insieme di esempi analizzati (cioè che non è in contraddizione).
Il lower bound è il concetto più specifico consistente con gli esempi visti.

Il concetto più specifico è uno solo

se p e q sono concetti congiuntivi (cioè possono essere congiunzioni di sottoconcetti) consistenti con il T.S., allora p and q è consistente con il TS poichè entrambi sono verificati e quindi la congiunzione è verificata.
Quindi il concetto più specifico è uno solo ed è la congiunzione di tutti quelli consistenti con il T.S. fino a quel momento selezionati.

Esempio di funzionamento

Sia il T.S.

A p y //picche
7 f y //fiori
8 c n
9 f y
5 c n
K q n
6 q n
7 p y

Dove y (yes) ed n (no) sono etichette che ci indicano che quella carta rappresenta il concetto congiuntivo che si vuole indurre (appunto, siamo nel training set). Ovvero l'algoritmo deve capire il concetto congiuntivo basandosi sulle informazioni di ogni esempio.

Allo start abbiamo: most specific (LB) -> nocard , least specific (UB)-> any card
Prendiamo il primo caso: A p y , è un caso positivo quindi deve essere consistente con il LB e l'UB, il LB non va bene quindi lo raffiniamo e diventa most (LB) = { A p } .
Secondo esempio: 7 f y . E' un altro esempio positivo che cozza con il LB, il concetto congiuntivo che racchiude entrambi gli esempi positivi è LB = {odd black} .
Terzo: 8 c n, è negativo quindi è una cosa da escludere, ovvero si raffina l'UB. least = {odd} union {black} cioè una carta positiva o è nera o è dispari. 8 c non rientra nei casi mentre gli esempi positivi visti si.
E poi si continua di questo passo.

Da notare che gli esempi positivi raffinano il LB (il most specific concept) perchè questo deve essere verificato per ogni esempio positivo. Mentre l'upper bound (il least specific concept) esclude gli esempi negativi e quindi viene modificato, eventualmente, ogni volta che si trovano esempi negativi.

Alla fine ci si ritroverà, se il T.S. è descrivibile con il bias imposto (solo concetti congiuntivi) con il least ed il most specific concept che combaciano e servono a descrivere esattamente un dato concetto del T.S. .
Ci sono dei casi in cui questa convergenza non c'è ed i due limiti sono vicini, in questo caso il concetto imparato è: il concetto reale è vicino a questi due estremi. Se la distanza, nel poset, tra questi due limiti è piccola, allora i casi che dovrebbero essere esclusi sono potenzialmente pochi (cioè gli errori son pochi) e quindi la procedura è probablmente pac.

Explanation base learning

E' un sistema di learning in parte già visto con il planning (Case based planning o memorizzazione con adversary search). Invece di memorizzare le regole indotte prodotte alla fine del processo di learning, memorizza anche le regole intermedie che funzionano da lemmi per le regole finali. Tuttavia per questo tipo di learning non c'è una linea guida.

Esempio di learning : regole associative nei DB

I problemi di learning sono potenzialmente più difficili degli altri problemi visti anche se in realtà molti problemi di learning risultano semplici mentre quelli di planning si mantengono piuttosto complessi. Vediamo un esempio reale di learning di regole associative in un DB.

In particolare vogliamo indurre regole che ci indicano la co-occorrenza di elementi in un carrello della spesa, per capire quali oggetti comprano assieme i consumatori.

Forma regole associative

Una regola associativa è nella forma hamb, fries -> ketchup ovvero è una regola associativa che ci dice che di solito (non è certo) le persone che comprano hamburgers e patatine comprano anche il ketchup.

Questa è una regola associativa di tipo dichiarativo, ovvero che è una regola che può essere o vera o falsa. C'è la possibilità di scrivere regole associative più flessibile, che sono vere in qualche caso. Queste regole sono dette quantitative (usano intervalli), quindi:
hamb in [2,4 units], fries in [100,300 gr] -> ketchup in [4,6 units]
Questa regola può esser vera per alcuni valori dell'intervallo.

In generale una regola associativa è fatta come segue:
$c_1 \wedge \ldots \wedge c_n \rightarrow c_{n+1} \wedge \ldots \wedge c_m$
Dove:

(6)
\begin{gather} c_i = \left\{\begin{matrix} A \in [a,b] \ or \ A \not \in [a,b]\\ B=a \ or \ B \ne a \end{matrix}\right. \end{gather}

Ovvero ci può esprimere intervalli o singoli valori. Se esprime singoli valori allora è uguale scrivere direttamente ci o not ci .

Inoltre la struttura della regola è astraibile in B -> H , dove B è il body o corpo della regola è H è la testa o head della regola.

Dominio di lavoro per indurre regole associative

Il dominio di lavoro è un database, in pratica un'unica tabella che racchiude tutte le transazioni (formate da tuple) che possono essere utili per fare analisi. Questa tabella è il Training set per indurre regole associative.

Quindi ad esempio:

hamb ketchup fries soda
2 4 100 no
1 0 100 si

Quello esposto sopra è un esempio di tabella con 2 transazioni qualitative.
La tabella può contenere anche valori ignoti o "nulli" (nulli da NULL in inglese, non zero. E' più calzante ignoti), ad esempio dati da errori di lettura, contrassegnati con il simbolo '?'.

Nel caso avessimo più tabelle che raccolgono i dati, potremmo sempre costruirne una che contenga tutti i dati necessari.

Gli oggetti considerati (o meglio "concetti" come hamburger, patatine, etc..) nelle transazioni qualitative fanno parte di un insieme I. Poi si introducono i simboli K ed S. K sta per min length, ovvero si vogliono indurre regole con una certa lunghezza minima poichè le regole troppo corte non sono molto informative e potrebbero essere tantissime se I ha una taglia considerevole. S sta per soglia minima (min threshold), ovvero la regola sarà indotta solo se il suo valore di qualità (l'equivalente della pacness) supera un certo livello. Tipo una regola dice che solo nell'1% dei casi chi compra 'a' e 'b' allora compra 'c', quindi questa regola non sarà indotta perchè poco affidabile.

Definizione del problema decisionale di indurre regole associative

Il problema è descritto da una quintupla: < I, T, i, k, s> , ovvero
I - attributi che formano una transazione (cioè le colonne, hamb, fries, etc..).
T - la tabella, cioè il DB.
i - indice di qualità.
k - il valore K prima esposto, la lunghezza minima delle regole
s - la soglia dell'indice da superare per indurre una regola.

Il problema decisionale è: Esiste una regola associativa 'r' che può essere indotta da 'T' che abbia dominio di attributi I tale che la lunghezza di 'r' sia maggiore o uguale di k ($length(r) \ge k$ ) e tale che l'indice i abbia un valore $i(r,T) \ge s$ (cioè l'indice i ha un valore maggiore della soglia per 'r' valutata su T)?

Inoltre la regola non deve essere banale. Una regola banale è quella che induce roba evidente, con grado di certezza 1. Del tipo: ogni volta che acquisto hamburger posso acquistare patatine o meno. Questa è sempre verificata perchè ci saranno i casi in cui acquisto patatine e casi in cui non acquisto patatine quando compro hamburger.

Che tipo di indici si usano?

Indice di supporto 'sup':

(7)
\begin{gather} sup(r) = \frac{ |T_{H \wedge B}|}{|T|} \end{gather}

Ovvero numero di transazioni dove occorrono sia gli attributi nel corpo che nella testa della regola sul numero di transazioni totali. In altri termini, per quante transazioni la regola potrebbe applicarsi, a prescindere dal fatto che sia corretta (ovvero sia reale, una regola che ha senso) o meno.

Ad esempio una regola che è sempre vera per i prodotti di nicchia (pad dell'xbox360) per l'intero training set potrebbe essere irrisoria.

Confidenza 'cnf':

(8)
\begin{gather} cnf(r) = \frac{ |T_{H \wedge B}|}{|T_B|} \end{gather}

Ovvero su quante transazioni può applicarsi la regola rispetto a tutte le transazioni su cui può applicarsi il corpo della regola.

Empiricamente si cercano valori: supporto magiore del 15% e confidenza maggiore del 75%.

Poi esistono indici combinati con coefficenti determinatu a priori.
Indice h-laplace (con h stabilito a priori).

(9)
\begin{gather} h-lap(r) = \frac{ |T_{H \wedge B}| + 1}{|T_B| + h} \end{gather}

Dubbio: da vedere cosa significa questo indice.

Indice theta gain. Con theta stabilito a priori.

(10)
\begin{gather} \theta gain(r) = \frac{ |T_{H \wedge B}| - \theta \cdot |T_B|}{|T|} \end{gather}

Questo vuol dire: non considerando un certo numero di transazioni a cui si applica il corpo della regola, quant'è il rapporto tra le transazioni rimanenti a cui si applica anche la testa della regola rispetto alle transazioni totali?

Complessità del problema.

Non è semplice stabilire la complessità nel problema di calcolo (cioè quello che calcola la soluzione), quindi si considera il problema decisionale corrispondente (che ci indica se una soluzione esiste) che dà un lower bound al problema di calcolo (nota: solitamente i problemi di calcolo sono più difficili dei problemi decisionali).

Senza valori nulli in T, si vuole sapere la complessità del problema precedentemente esposto. Questo problema si può ridurre al problema di trovare una clique di taglia almeno k su un grafo, cioè k-clique. Dunque il problema decisionale è NP completo. Questo vale se usiamo gli indici 'sup', 'hlap' e 'theta gain'.

Se usiamo l'indice 'cnf' vale una caratteristica di monotonicità rispetto a k ed s e quindi il problema diventa polinomiale. Ovvero si può usare una speciale algoritmo greedy per trovare le regole associative.

Se invece in T ci sono valori nulli? Con qualsiasi indice il problema rimane NP completo.

DB sparso

Un DB sparso è un DB con transazioni che hanno molti valori pari a zero (non "nulli" ma zero). Quindi c'è poca roba significativa ed in questo caso il problema diventa di complessità logspace (dentro PTIME) con qualsiasi indice.

DB booleano

Se il DB è booleano (solo valori si/no) ma NON sparso, con un k fissato oppure la taglia del DB è fissa e k può variare, il probelma rientra nella classe TC0 che è la classe delle funzioni aritmetiche (è dentro PTIME ed è più semplice di log space).

Conclusione

Questo è un esempio di come un problema di learning opportunamente "ristretto" ad un contesto pratico diventa abbastanza semplice.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License