Zagadnienia

5. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1.1. Metody wnioskowań Boolowskich w szukaniu reduktów

5.1.1.1. Algebry Boola

\columns\column

9cm Algebra Boola Jest to struktura algebraiczna \definition

B=(B,+,,0,1)

spełniająca następujące aksjomaty

- Przemienność:

a+b=b+a oraz ab=ba

- Rozdzielność:

ab+c=ab+ac, oraza+bc=a+ba+c

- Elementy neutralne:

a+0=a oraz a1=a

- Istnienie elementu komplementarnego:

a+a¯=1 and aa¯=0

*) Czasem negacja jest dodana do sygnatury algebry Boola.

  1. <+-> Algebra zbiorów: P(X)=(2X,,,-,,X);

  2. <+-> Rachunek zdań

    ({zdanialogiczne},,,¬,,)
  3. <+-> Binarna algebra Boola B2=({0,1},+,,0,1) to jest najmniejsza, ale najważniejsza algebra Boola w zastosowaniu.

    xyx+yxy0000011010101111x¬x0110

    Przykłady zastosowań:

    • projektowanie układów scalonych;

    • rachunek zdań.

Łączność (ang. Associative law):

x+y+z=x+y+z oraz xyz=xyz

Idempotence:

x+x=xorazxx=xdual

Działania z 0 i 1:

x+1=1orazx0=0dual

Pochłanienie (ang. Absorption laws):

yx+x=xorazy+xx=xdual

Inwolocja (ang. Involution laws):

x¯¯=x

Prawa DeMorgana (ang. DeMorgan's laws):
¬x+y=¬x¬yoraz¬(xy)=¬x+¬y(dual)
Prawa konsensusu (ang. Consensus laws):
x+yx¯+zy+z=x+yx¯+z oraz 
xy+x¯z+yz=xb+x¯z
Zasada dualności:

Każda algebraiczna równość pozostaje prawdziwa jeśli zamieniamy operatory + na , na +, 0 na 1 oraz 1 na 0.

5.1.1.2. Funkcje Boolowskie i wnioskowanie Boolowskie

  • <+-> Każde odwzorowanie f:0,1n0,1 nazywamy (zupełną) funkcją Boolowską.

  • <+-> Funkcje Boolowskie formuły Boolowskie:

    • Stałe, zmienne, operatory ¯, + oraz .

    • Literały, mintermy (jednomiany), maxtermy, …

    • Kanoniczna postać dyzjunkcyjna (DNF), np. f=xyz¯+xy¯z+x¯yz+xyz;

    • Kanoniczna postać koniunkcyjna (CNF), np. f=x+y+zx¯+y

  • <+-> Term t=xi1ximxj1¯xjk¯ nazywamy implikantem funkcji f jeśli

    a0,1nta=1fa=1

  • <+-> Implikant pierwszy: jest to implikant, który przestaje nim być po usunięciu dowolnego literału.

  • <+-> Kanoniczna postać Blake'a: każdą funkcję Boolowską można przedstawić jako sumę wszystkich jej imlikantów pierwszych:

    f=t1+t2++tk

Wiele formuł reprezentuje tę samą funkcję;

ϕ1=xyz¯+xy¯z+x¯yz+xyz

ϕ2=x+y+zx¯+y+zx+y¯+zx+y+z¯

ϕ3=xy+xz+yz

xyz¯ jest implikantem

xy jest implikantem pierwszym

x y z f
0 0 0 0
1 0 0 0
0 1 0 0
1 1 0 1
0 0 1 0
1 0 1 1
0 1 1 1
1 1 1 1
  • <+-> Niech oznacza relację częściowego porządku w 0,1n

  • <+-> Funkcja f jest monotoniczna (niemalejąca) wtw, gdy dla każdych x,y0,1n jeśli xy to fxfy

  • <+-> monotoniczne funkcje Boolowskie można zapisać bez użycia negacji.

  • <+-> term f=xi1xi2xik nazywamy implikantem pierwszym funkcji monotonicznej f jeśli

    • fxfx dla każdego wektora x (jest implikantem)

    • każda funkcja większa od f nie jest implikantem

  • <+-> Np. funkcja

    fx1,x2,x3=x1+x2x2+x3

    posiada 2 implikanty pierwsze: f1=x2 i f2=x1x3

 

 

  1. Modelowanie: Kodowanie problemu za pomocą układu równań Boolowskich;

  2. Redukcja: Sprowadzenie układu równań do pojedynczego równania postaci f=0lubf=1

  3. Konstrukcja: Znalezienie wszystkich implikantów pierwszych funkcji f (konstrukcja kanonicznej postaci Blake'a);

  4. Dedukcja: Zastosowanie pewnej sekwencji wnioskowań transformujących implikanty pierwsze do rozwiązań problemu.

\columns\column

6cm <1-> \onslide 

Problem:

A,B,C,D are considering going to a party. Social constrains:

  • If A goes than B won't go and C will;

  • If B and D go, then either A or C (but not both) will go

  • If C goes and B does not, then D will go but A will not.

 

\onslide

<2-> Problem modeling:

AB¯CAB+C¯=0
BDAC+AC¯=0
B¯CA+D¯=0
\column

6cm

  • <3-> After reduction:

    f=AB+C¯+BDAC+AC¯+B¯CA+D¯=0

  • <4-> Blake Canonical form: f=BC¯D+B¯CD¯+A=0

  • <5-> Facts:

    BDC
    CBD
    A0
  • <6-> Reasoning: (theorem proving)

    e.g., show that

    ”nobody can go alone.”

\columns\column

7cm

  • <+-> Problem SAT: czy równanie

    fx1,,xn=1

    posiada rozwiązanie?

  • <+-> SAT odgrywa ważną rolę w teorii złożoności (twierdzenie Cooka, dowodzenie NP-zupełności …)

  • <+-> Każdy SAT-solver może być używany do rozwiązywania problemu planowania.

  • <+-> Blocks world problem: Po redukcji formuła boolowska nadal zawiera Otk2 zmiennych i Otk3 klauzuli (k,t - liczby bloków i kroków).

  • <+-> Np. Dla k=15, t=14, mamy 3016 zmiennych i 50457 klausuli

\column

5cm<4->\only

\only

<3->

  1. <+-> Konstrukcja funkcji odróżnialności:

    • Zmienne boolowskie: atrybuty a1,,ak;

    • Klauzula:

      ϕu,v=aA:auav
    • Funkcja rozróżnialności:

      FSa1,,ak=x,yU:decxdecyϕx,ya1,,ak
  2. <+-> przekształcenie funkcji rozróżnialności do postaci DNF

  3. <+-> każdy implikant pierwszy odpowiada jednemu reduktowi;

Hurt. Jakość obsługi Jakość towaru Obok autostrady? Centrum? decyzja
ID a1 a2 a3 a4 dec
1 dobra dobra nie nie strata
2 dobra dobra nie tak strata
3 bdb dobra nie nie zysk
4 slaba super nie nie zysk
5 slaba niska tak nie zysk
6 slaba niska tak tak strata
7 bdb niska tak tak zysk
8 dobra super nie nie strata
9 dobra niska tak nie zysk
10 slaba super tak nie zysk
11 dobra super tak tak zysk
12 bdb super nie tak zysk
13 bdb dobra tak nie ?
14 slaba super nie tak ?
M 1 2 6 8
3 a1 a1,a4 a1,a2,a3,a4 a1,a2
4 a1,a2 a1,a2,a4 a2,a3,a4 a1
5 a1,a2,a3 a1,a2,a3,a4 a4 a1,a2,a3
7 a1,a2,a3,a4 a1,a2,a3 a1 a1,a2,a3,a4
9 a2,a3 a2,a3,a4 a1,a4 a2,a3
10 a1,a2,a3 a1,a2,a3,a4 a2,a4 a1,a3
11 a2,a3,a4 a2,a3 a1,a2 a3,a4
12 a1,a2,a4 a1,a2 a1,a2,a3 a1,a4
f=α1α1α4α1α2α1α2α3α4α1α2α4
α2α3α4α1α2α3α4α2α3α2α4
α1α3α3α4α1α2α4
f=α1α1α4α1α2α1α2α3α4α1α2α4
α2α3α4α1α2α3α4α2α3α2α4
α1α3α3α4α1α2α4
  • <+-> usuwanie alternatyw regułą pochłaniania (t.j. ppqp):

    f=α1α4α2α3
  • <+-> sprowadzanie funkcji f z postaci CNF (koniunkcja alternatyw) do postaci DNF (alternatywa koniunkcji)

    f=α1α4α2α1α4α3
  • <+-> Każdy składnik jest reduktem! Zatem mamy 2 redukty: R1=A1,A2,A4 i R2=A1,A3,A4

5.1.1.3. Heurystyka Johnsona

  • <+-> Atrybut jest ważniejszy jeśli częściej występuje w klauzulach;

  • <+-> Selekcja: W każdym kroku wybierzmy atrybut, który najczęściej występuje w funkcji rozróżnialności;

  • <+-> Usuwanie: Usuwamy z tej funkcji te klauzule, które zawierają wybrany atrybut;

  • <+-> Powtarzamy Selekcja i Usuwanie dopóty, póki funkcja rozróżnialności zawiera jeszcze jakąś klazulę.

 

Heurystyka Johnsona

  1. Znaleźć atrybut, który występuje najczęściej w macierzy rozróżnialności;

  2. Usuwnąć wszystkie pola zawierające wybrany atrybut;

  3. Powtarzamy kroki 1 i 2 dopóki wszystkie pola macierzy są puste.

 

M 1 2 6 8
3 a1 a1,a4 a1,a2,a3,a4 a1,a2
4 a1,a2 a1,a2,a4 a2,a3,a4 a1
5 a1,a2,a3 a1,a2,a3,a4 a4 a1,a2,a3
7 a1,a2,a3,a4 a1,a2,a3 a1 a1,a2,a3,a4
9 a2,a3 a2,a3,a4 a1,a4 a2,a3
10 a1,a2,a3 a1,a2,a3,a4 a2,a4 a1,a3
11 a2,a3,a4 a2,a3 a1,a2 a3,a4
12 a1,a2,a4 a1,a2 a1,a2,a3 a1,a4
  • W macierzy nierozróznialności z poprzedniego przykładu

    a1 - występuje 23 razy a2 - występuje 23 razy

    a3 - występuje 18 razy a4 - występuje 16 razy

  • Jeśli wybieramy a1, to po usunięciu pól zawierających a1 zostało 9 niepustych pól macierzy nierozróżnialności. Wśród nich:

    a2 - występuje 7 razy a3 - występuje 7 razy a4 - występuje 6 razy

  • Jeśli wybieramy tym razem a2 to zostały 2 niepuste pola i wśród nich a4 jest zdecydowanym faworytem.

  • Możemy dostać w ten sposób redukt: R1=a1,a2,a4.

  • Niech X=u,vU2:decudecv;

  • Niech Sai=u,vX:aiuaiv;

  • Niech C*A będzie minimalnym reduktem, lecz C=a1,,ak będzie reduktem znalezionym przez heurystykę Johnsona;

  • Załóżmy, że heurystyka Johnsona musi płacić 1zł za każdym razem, gdy dodała ai do C.

  • Rozłóżmy ten koszt tym elementom, które zostały po raz pierwszy pokryte przez zbiór Sai

  • Niech cx = koszt ponoszony przez x. Jeśli x jest pokryty po raz pierwszy przez ai, to

    cx=1Sai-Sa1Sai-1
  • Heurystyka Johnsona ponosi łączny koszt =C. Mamy

    C=xXcxaC*xSacx
  • Gdybyśmy pokazali, że dla dowolnego altrybutu aA

    xSacxHSa

    gdzie Hn=i=1n1i, wówczas możemy oszacować dalej:

    CaCA*xSacx|C*|H(max{|Sa:aA|})
    |C*|H(|X|)|C*|ln(|X|+1)

 Lemat:

Dla dowolnego altrybutu aA

xSacxHSa

 

Dowód:

  • Niech ui=Sa-Sa1Sai-1, mamy:

    u0=Saui-1uiuk=0;

    gdzie k jest najmniejszym indeksem t., że Sa=Sa1Sak

  • Zatem

    xSacx=i=0kui-1-ui1Sai-Sa1Sai-1
    i=0k(ui-1-ui)1ui-1i=0k(H(ui-1)-H(ui))=H(|Sa|)

5.1.1.4. Inne heurystyki

  • ILP (Integer Linear Program)

  • Symulowane wyżarzanie (simulated annealing)

  • Algorytmy genetyczne

  • SAT solver

  • ???

Dana jest funkcja f:0,1n0,1 zapisana w postaci CNF za pomocą zmiennych x1,,xn

  1. Utwórz nowe zmienne y1,,y2n odpowiadające literałom x1,x1¯,,xn,xn¯;

  2. Dla każdej zmiennej xi, utwórzmy nierówność y2i-1+y2i1

  3. Zamień każdą klausulę ωi=li1lini na nierówność yi1++yini1;

  4. Utwórzmy układ nierówności z poprzednich punktów:

    Ayb
  5. Zagadnienie programowania liniowego liczb całkowitych (ILP) jest definiowane jako problem szukania

    mini=1nyi przy ograniczeniu:  Ayb.

5.1.2. Systemy decyzyjne oparte o zbiory przybliżone

5.1.2.1. Reguły decyzyjne

Dla danego zbioru atrybutów A definiujemy język deskryptorów jako trójkę

L(A)=(D,{,,¬},F)

gdzie

  • D jest zbiorem deskryptorów

    D={(a=v):aA and vVala};
  • {,,¬} jest zbiorem standardowych operatorów logicznych;

  • F jest zbiorem formuł logicznych zbudowanych na deskryptorach z D.

  • Dla każdego zbioru atrybutów BA oznaczamy:

    D|B={(a=v):aB and vVala}, czyli zbiór deskryptorów obciętych do B.

    FB zbiór formuł zbudowanych na DB.

 

Semantyka:

Niech S=U,A będzie tablicą informacyjną. Każda formuła ϕF, jest (semantycznie) skojarzona ze zbiorem ϕS zawierającym obiekty spełniające ϕ.

Formalnie możemy indukcyjnie definiować semantykę jak następująco:

[[(a=v)]]S=xU:ax=v (5.1)
ϕ1ϕ2S=ϕ1Sϕ2S (5.2)
ϕ1ϕ2S=ϕ1Sϕ2S (5.3)
¬ϕS=UϕS (5.4)

 

Każda formuła ϕ może być charakteryzowana przez:

  • lengthϕ= liczba deskryptorów w ϕ;

  • supportϕ=ϕS= liczba obiektów spełniających formułę

\definition

Definicja reguł decyzyjnych Niech S=U,Adec będzie tablicą decyzyjną. Regułą decyzyjną dla S nazywamy formuły postaci:

ϕδ

gdzie ϕFA i δFdec.

Formułę ϕ nazywamy poprzednikiem (lub założeniem) reguły r, a δ nazywamy następnikiem (lub tezą) reguły r.

Oznaczamy poprzednik i następnik reguły r przez prevr oraz consr.

\definition

Reguły atomowa: Są to reguły postaci:

r(ai1=v1)(aim=vm)(dec=k) (5.5)

Każda reguła decyzyjna r postaci (5.5) może być charakteryzowana następującymi cechami:

lengthr = liczba deskryptorów występujących w założeniu reguły r
r = nośnik reguły r, czyli zbiór obiektów z U spełniających założenie reguły r
supportr = liczba obiektów z U spełniających założenie regułyr: supportr=cardr
confidencer = wiarygodność reguły r: confidencer=rDECkr

Mówimy, że reguła r jest niesprzeczna z A jeśli

confidencer=1
\definition

Minimalne niesprzeczne reguły: Niech S=U,Adec będzie daną tablicą decyzyjną. Niesprzeczną regułę

(ai1=v1)(aim=vm)(dec=k)

nazywamy minimalną niesprzeczną regułą decyzyjną jeśli usunięcie któregokolwiek z deskryptorów spowoduje, że reguła przestaje być niesprzezcna z S.

5.1.2.2. Regułowe systemy decyzyjne

Klasyfikatory regułowe dzialają w trzech fazach:

  1. Faza treningu: Generuje pewien zbiór reguł RULESA z danej tablicy decyzyjnej A.

  2. Faza selekcji reguł: Szuka w RULESA tych reguł, które są wspierane przez obiekt x. Oznaczamy zbiór tych reguł przez MatchRulesA,x.

  3. Faza klasyfikacji: wyznacza klasędecyzyjną dla x za pomocą reguł z MatchRulesA,x według następującego schematu:

    1. Jeśli MatchRulesA,x jest pusty: odpowiedź dla x jest ``NIEWIEM′′, tzn. nie mamy podstaw, aby klasyfikować obiekt x do którejkolwiek z klas;

    2. Jeśli MatchRulesA,x zawiera tylko obiekty z k-tej klasy: wówczas decx=k;

    3. Jeśli MatchRulesA,x zawiera reguły dla różnych klas decyzyjnych: wówczas decyzja dla x określimy za pomocą pewnego, ustalonego schematu głosowania między regułami z MatchRulesA,x.

5.1.2.3. Szukanie minimalnych reguł decyzyjnych

  • Każda reguła powstaje poprzez skracanie opisu jakiegoś obiektu.

  • Redukty lokalne

  • Te same heurystyki dla reduktów decyzyjnych.

Hurt. Jakość obsługi Jakość towaru Obok autostrady? Centrum? decyzja
ID a1 a2 a3 a4 dec
1 dobra dobra nie nie strata
2 dobra dobra nie tak strata
3 bdb dobra nie nie zysk
4 slaba super nie nie zysk
5 slaba niska tak nie zysk
6 slaba niska tak tak strata
7 bdb niska tak tak zysk
8 dobra super nie nie strata
9 dobra niska tak nie zysk
10 slaba super tak nie zysk
11 dobra super tak tak zysk
12 bdb super nie tak zysk
13 bdb dobra tak nie ?
14 slaba super nie tak ?
M 1 2 6 8
3 a1 a1,a4 a1,a2,a3,a4 a1,a2
4 a1,a2 a1,a2,a4 a2,a3,a4 a1
5 a1,a2,a3 a1,a2,a3,a4 a4 a1,a2,a3
7 a1,a2,a3,a4 a1,a2,a3 a1 a1,a2,a3,a4
9 a2,a3 a2,a3,a4 a1,a4 a2,a3
10 a1,a2,a3 a1,a2,a3,a4 a2,a4 a1,a3
11 a2,a3,a4 a2,a3 a1,a2 a3,a4
12 a1,a2,a4 a1,a2 a1,a2,a3 a1,a4
fu3=α1α1α4α1α2α3α4α1α2=α1

Reguły:

(a1=bdb)dec=zysk
M 1 2 6 8
3 a1 a1,a4 a1,a2,a3,a4 a1,a2
4 a1,a2 a1,a2,a4 a2,a3,a4 a1
5 a1,a2,a3 a1,a2,a3,a4 a4 a1,a2,a3
7 a1,a2,a3,a4 a1,a2,a3 a1 a1,a2,a3,a4
9 a2,a3 a2,a3,a4 a1,a4 a2,a3
10 a1,a2,a3 a1,a2,a3,a4 a2,a4 a1,a3
11 a2,a3,a4 a2,a3 a1,a2 a3,a4
12 a1,a2,a4 a1,a2 a1,a2,a3 a1,a4
fu8=α1α2α1α1α2α3α1α2α3α4α2α3
α1α3α3α4α1α4
=α1α2α3α3α4=α1α3α1α2α4

Reguły:

  • (a1=dobra)(a3=nie)dec=strata

  • (a1=dobra)(a2=super)(a4=nie)dec=strata

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.