07. ragionamenti non deduttivi ed outlier detection

Tipi di ragionamento

Fino ad ora abbiamo visto ragionamenti deduttivi. Un ragionamento deduttivo è quel ragionamento che dice "dato un modello è vero che la formula da dedurre è resa vera dal modello?" (nota: è vero che nei capitoli precedenti ho usato spesso la parola derivare, mentre invece la parola corretta sarebbe stata dedurre, devo correggere questo problema). Questa è la deduzione secondo semantica (usando una interpretazione che dice cosa è vero e cosa no). Poi c'è la derivazione che è una deduzione secondo sintassi. Ovvero c'è un set di regole che formano la regola di inferenza, queste regole indicano come elaborare le formule (o clausole) della teoria data per vedere se una di queste elaborazioni riesce a derivare la formula che si voleva derivare.

La deduzione, in generale, parte da leggi generali ("per ogni elemento nel dominio") per asserire qualcosa su casi particolari ("per questo sottoinsieme di elementi del dominio vale questo").
L'induzione invece "accumula" casi particolari per asserire qualcosa di generale ("se vale per x, y e z allora possiamo dire che vale per ogni x questa legge").
Altra forma di ragionamento è l'abduzione quella spesso usata in medicina.

Abduzione con la default logic

Un problema abduttivo è definito dalla seguente tripla:
(H, M, (D,W))
H : insieme di ipotesi.
M : insieme di manifestazioni.
(D,W) [o DELTA]: teoria di default (nel caso generale, cioè dell'abduzione con qualsiasi tipo di logica, è un formalismo di rappresentazione della conoscenza).

M è l'evidenza data dalla realtà, tipo "si è osservato che il mare è blu". (D,W) cerca di descrivere la realtà con relazioni tra proprietà (tipo "se pesce allora nuota") o singoli fatti. H sono le possibili spiegazioni, o i "perchè accade", alle manifestazioni M.

Un'explanation (non extension. Al solito è sempre un modello per questa sistema logico, ma in questo caso si chiama explanation) E con $E \subset H$ è la soluzione del problema abduttivo che rispetta le seguenti proprietà:

  • $\left ( W \cup E, D \right ) \models M$ . Se ritengo E come conoscenza certa, riesco a dedurre (e quindi a spiegare) le manifestazioni.
  • $\left ( W \cup E, D \right )$ deve essere consistente, cioè senza contraddizioni, perchè dalle contraddizioni "Ex falso quodlibet" ovvero posso dedurre tutto.
  • Che E sia minimale (non è proprio necessario, queata regola è opzionale) così da "risparmiare calcoli".

Outlier detection (rilevazione di anomalia)

Cos'è un outlier.

In statistica, data una popolazione di oggetti, raggruppiamo questi secondo certi criteri. Se esistono oggetti che non soddisfano i criteri per essere ascritti ad almeno un gruppo allora questi oggetti sono anomalie o outlier.

Outlier di default logic con ragionamento induttivo condizionato ad una manifestazione

Introduciamo il concetto con un esempio:

D = { b(x) : f(x) / f(x) ; o(x) : not f(x) / not f(x) }
  //f(x) vola x
W = { o(x) -> b(x) //uno struzzo (ostrich) è un uccello
      b(t)
      o(f)
      not f(t) //è una conoscenza "anomala" perchè la proprietà not f la dedurremmo dai default
        //ma non sappiamo se t sia uno struzzo.
        //Questa conoscenza è data dalla manifestazione
    }

Cerchiamo le possibili explanation (spiegazioni)

E1 = W UNION { b(f), f(t) }
E2 = W UNION { b(f), not f(t) }

Di conseguenza possiamo asserire che riusciamo a dedurre $\Delta \models_c \neg f(t)$ (con la semantica cauta) ma non c'è scritto da nessuna parte che 't' sia uno struzzo e che quindi non possa volare (conoscenza data dal default), semplicemente prendiamo per assodato che sia vero che not f(t) , ovvero l'unico modo per dedurre questa conoscenza sia di avere not f(t) in W per il fatto che sia una manifestazione osservata.
Se togliamo il fatto sopra citato, invece, si ottengono altre explanation e si deriva subito $\Delta \models_c f(t)$. Ovvero senza la manifestazione reale possiamo dedurre l'opposto, ovvero la manifestazione è come se fosse un'anomalia.

Se eliminiamo altre conoscenze certe riusciamo a non dedurre nè f(t) che not f(t) .
Dunque avendo la teoria:
DELTA = ( W - {not f(t), b(t) } , D ) abbiamo che $\neg ( \Delta \models_c f(t) \vee \neg f(t) )$ (da delta non deduciamo in modo cauto ne l'anomalia nè il suo contrario), infatti il default che ci dice se 't' vola o meno non si riesce ad applicare perchè il prerequisito non è soddisfatto.

Dunque not f(t) è un'anomalia in quanto 't' è un uccello ma non uno struzzo, quindi b(t) è l'outlier (infatti ci dà informazione ma non abbastanza per dedurre not f(t) ) e not f(t) è il witness ovvero la testimonianza o meglio la prova che ci sia un'anomalia.

In questo caso outlier e witness sono singoli letterali ma di solito sono insiemi (di letterali).

Facendo un paragone con le basi di dati durante il clustering, se W è la base di dati e D sono algoritmi di clusterizzazione, allora dopo aver applicato D su W si troveranno outlier nel risultato.

Belief revision

Prima si è detto che W fa parte della conoscenza certa e se qualche manifestazione cozza contro le regole originarie di W allora questa manifestazione è considerata un'anomalia. Questo significa ritenere le regole in W certe oltre ogni dubbio o manifestazione (insomma come se fossero dogmi). Invece un altro tipo di ragionamento è la belief revision che sostanzialmente modifica le regole in W se esistono manifestazioni che le rendono contraddittorie.

Alcune definizioni formali

Data una teoria di default DELTA = (W, D) . Sia $L \subset W$ un insieme di letterali (costanti o, nel caso delle teorie logiche, fatti), L si dice outlier se esiste un $S \subseteq W_L$ (con $W_L = W-L$ da cui $S \cap L = \emptyset$) tale che:

  1. $\left ( W_S, D \right ) \models \neg S$ (dove $W_S = W-S$) . Ovvero se tolgo il witness non deduco più le anomalie, ma addirittura l'opposto.
  2. $\left ( W_{S,L}, D \right ) \not\models \neg S$ (dove $W_{S,L} = W - (S \cup L)$) . Ovvero se tolgo sia le anomalie che la witness, non deduco più l'opposto della witness ovvero non deduco più la testimonianza della presenza delle anomalie (testimonianza di anomalie: se tolgo l'anomalia deduco il suo opposto).

L'insieme S sarà detto witness.

nota: S è un insieme di fatti e/o regole in W, ma normalmente sono fatti che testimoniamo l'esistenza di anomalia, infatti S è il witness.
nota2: Un insieme di clausole è dedotto se deduco tutti i suoi elementi.

Outlier detection per teorie di default semi normali collegate con problemi abduttivi.

Data la teoria dei default DELTA = (W,D) e presi due insiemi S,L tali che $S,L \subseteq W \wedge S \cap L = \emptyset$.

Definizione: S è witness per l'outlier L in DELTA se e sono se L è una explanation per not S in $\left ( L, \neg S, \left (W_{S,L}, D \right ) \right )$ . Ovvero $\left ( W_{S,L} \cup L, D \right ) \models \neg S$ con $\left ( W_{S,L} \cup L, D \right )$ consistente. In sostanza si applica la definizione sopra esposta (punto 1), cercando un L tale che $\left ( W_S, D \right ) \models \neg S$, infatti $W_{S,L} \cup L = W_S$

Complessità outlier detection

In problemi abduttivi S è data (le manifestazioni) quindi è più facile individuare L. In problemi normali bisogna individuare sia S che L ed è più difficile.

Supponiamo di eliminare le disgiunzioni (quindi le regole in W), quindi la complesità per trovare un'explanation o un'extension (insomma un modello) scende di livello perchè in W abbiamo solo i fatti. Questo ha implicazioni anche ell'outlier detection quando proviamo a verificare che S rispetto le caratteristiche di una witness (che necessitano di deduzione e quindi di modelli, vedi sopra).

Problema dell'outlier

Data una teoria di default DELTA, esiste in questa un outlier L ed il suo witness S?
Costo computazionale: teoria generale di default $\Sigma^P_3 \mbox{-compl}$ ; teoria con default senza digiunzioni $\Sigma^P_2 \mbox{-compl}$.

Problema dell'outlier K

Data una teoria di default DELTA, esiste in questa un outlier L ed il suo witness S, tale che la taglia di L sia minore o uguale di K? (i problemi limitati di solito sono più semplici rispetto a quelli "trovami tutti gli outlier").
Costo computazionale: teoria generale di default $\Sigma^P_3 \mbox{-compl}$ ; teoria con default senza digiunzioni $\Sigma^P_2 \mbox{-compl}$. (come si vede, in generale, la complessità rimane uguale a quella del problema precedente)

Problema dell'outlier dato L

Data una teoria di default DELTA, ed un possibile outlier L è vero che L è un outlier in DELTA per qualche witness S?
Costo computazionale: teoria generale di default $\Sigma^P_3 \mbox{-compl}$ ; teoria con default senza digiunzioni $\Sigma^P_2 \mbox{-compl}$.

Problema della witness data S

Data una teoria di default DELTA, ed una possibile witness S, è vero che S è la witness di qualche outlier L in DELTA?
Costo computazionale: teoria generale di default $D^P_2 \mbox{-compl}$ ; teoria con default senza digiunzioni $D^P_1 \mbox{-compl}$. (scendiamo a D perchè le manifestazioni sono date)

Problema dell'outlier K,S

Data una teoria di default DELTA, ed una possibile witness S, esiste un outlier L di taglia minore o uguale di K con witness S?
Costo computazionale: teoria generale di default $D^P_2 \mbox{-compl}$ ; teoria con default senza digiunzioni $D^P_1 \mbox{-compl}$.

Problema dell'outlier S,L

Data una teoria di default DELTA, e dati gli insiemi S ed L, è vero che L è un outlier con witness S?
Costo computazionale: teoria generale di default $D^P_2 \mbox{-compl}$ ; teoria con default senza digiunzioni $D^P_1 \mbox{-compl}$.

Problema dell'outlier min L

Data una teoria di default DELTA, ed un possibile outlier L, è vero che L è un outlier minimale in DELTA per qualche S?
Costo computazionale: teoria generale di default $D^P_3 \mbox{-compl}$ ; teoria con default senza digiunzioni $D^P_2 \mbox{-compl}$.

Problema dell'outlier min L, S

Data una teoria di default DELTA, ed un possibile outlier L, è vero che L è un outlier minimale in DELTA per qualche S?
Costo computazionale: teoria generale di default $D^P_2 \mbox{-compl}$ ; teoria con default senza digiunzioni $\Pi^P_2 \mbox{-compl}$.

Dubbio: chiedere se effettivamente le complessità son giuste.

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