1 Case-Based Reasoning Autor: Robert Papis

2 Plan prezentacji Wprowadzenie Przykład Precedens Cykl CBR CBR na świecie Podsumowanie

3 Korzenie Human experts are not systems of rules, they are libraries of experiences. Riesbeck and Schank 1989

4 Korzenie Case-based reasoning is [...] reasoning by remembering. Leake, 1996 A case-based reasoner solves new problems by adapting solutions that were used to solve old problems. Riesbeck & Schank, 1989 Case-based reasoning is both [...] the ways people use cases to solve problems and the ways we can make machines use them. Kolodner, 1993

5 Przykład warsztat samochodowy Problem Opis przypadku marka samochodu, rocznik Zaobserwowane symptomy coś zgrzyta przy zmianie biegów Wyniki dodatkowych pomiarów napięcie na akumulatorze 6,3 V Zadanie Znaleźć przyczynę usterki Zaproponować sposób naprawy

6 Przypadek X Opis problemu... Proponowane rozwiązanie... Cecha1: Cecha2:... Wartość1 Wartość2.... Przykład – opis przypadku Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Diagnoza : Zaleczenia: Przypadek 32 Przednie światło nie działa VW Golf II, 1.6L 1993 13,6V OK. OK Uszkodzony bezpiecznik Wymienić bezpiecznik

7 Przykład – baza przypadków Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Diagnoza : Zalecenia: Przypadek 1 Przednie światło nie działa VW Golf II, 1.6L 1993 13,6V OK OK Uszkodzony bezpiecznik Wymienić bezpiecznik Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Diagnoza : Zalecenia: Przypadek 2 Przednie światło nie działa Audi A6 1995 12,9V zmiażdżone w wypadku OK Uszkodzona żarówka Wymienić przednie światła Każdy przypadek opisuje jedną sytuację Przypadki są od siebie niezależne Przypadki nie są regułami

8 Przykład – nowy problem Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK Próbujemy opisać nowy przypadek Wartości niektórych cech mogą być nieznane Nowy problem jest przypadkiem bez rozwiązania

9 Przykład – wyszukanie podobnych Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Diagnoza : Zaleczenia: Przypadek X Porównaj nowy przypadek z każdym przypadkiem przechowywanym w bazie przypadków Problem: Samochód: Rocznik: Akumulator: Stan świateł: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK Podobne ? Wybierz najbardziej podobny Podobieństwo jest jedną z najważniejszych idei CBR

10 Przykład – podobieństwo Podobieństwo jest obliczane dla każdej z cech Podobieństwo zależy od wartości cech Cechy mogą posiadać różne znaczenie (wagę) Podobne ? Cecha: Problem Cecha: Akumulator Przednie światło nie działa Tylne światło nie działa Wycieraczki nie działają 0,8 0,5 12,6 V 13,6 V 6,7 V 0,9 0,2

11 Przykład – porównanie z przypadkiem 1 Miara podobieństwa (uwzględniając wagi) Problem: Samochód: Rocznik: Akumulator: Stan świateł: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK Przypadek 1 Diagnoza : Zaleczenia: Przednie światło nie działa VW Golf II, 1.6L 1993 13,6V OK OK Uszkodzony bezpiecznik Wymienić bezpiecznik 0,9 0,6 0,4 0,8 1,0 sim(np, p1) = 1/20*[6*0,8+1*0,4+1*0,6+6*0,9+6*1,0]=0,86

12 Przypadek 2 Diagnoza : Zaleczenia: Przednie światło nie działa Audi A6 1995 12,9V zmiażdżone w wypadku OK Uszkodzona żarówka Wymienić przednie światła Przykład – porównanie z przypadkiem 2 Miara podobieństwa (uwzględniając wagi) Problem: Samochód: Rocznik: Akumulator: Stan świateł: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK 0,95 0,4 0,8 0 sim(np, p2) = 1/20*[6*0,8+1*0,8+1*0,4+6*0,95+6*0]=0,585

13 Przykład – wykorzystanie rozwiązania 1 Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK Uszkodzony bezpiecznik Wymienić bezpiecznik Jeżeli diagnoza jest poprawna, zapamiętujemy nowy przypadek Przypadek 1 Diagnoza : Zaleczenia: Przednie światło nie działa VW Golf II, 1.6L 1993 13,6V OK OK Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: 0,86 Uszkodzony bezpiecznik Wymienić bezpiecznik

14 Przykład – wykorzystanie rozwiązania 1 Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Nowy problem Tylne światła nie działają Audi 80 1989 12,6V OK Uszkodzony bezpiecznik Wymienić bezpiecznik Przypadek 1 Diagnoza : Zaleczenia: Przednie światło nie działa VW Golf II, 1.6L 1993 13,6V OK OK Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.: Uszkodzony bezpiecznik Wymienić bezpiecznik Przypadek 3 Diagnoza : Zaleczenia: Tylne światła nie działają Audi 80 1989 12,6V OK Uszkodzony bezpiecznik Wymienić bezpiecznik Problem: Samochód: Rocznik: Akumulator: Stan świateł: Włącznik św.:

15 Precedens precedens (łac. praecedens poprzedzający od praecedere poprzedzać) wydarzenie, które poprzedza inne tego typu; także sprawa, której sposób rozwiązania służy za przykład lub uzasadnienie analogicznych zdarzeń przyszłych, podobnych. Słownik Wyrazów Obcych, pod redakcją prof. Ireny Kamińskiej-Szmaj, 2001.

16 Przypadek Kilka cech opisujących problem oraz wynik lub rozwiązanie Przypadki mogą zawierać dane w różnych formatach: tekst, liczby, symbole, multimedia Przypadki nie są wydestylowaną wiedzą Przypadki to zapis rzeczywistych zdarzeń Świetnie nadają się do uzasadnienia decyzji

17 Cykl CBR Retrieve Reuse Revise Retain

18 Nowy problem/reprezentacja RETRIEVE REUSE REVISE RETAIN Przypadek bez części rozwiązanie Model płaski Wektor cech Zazwyczaj przechowywany w RDB Heterogeniczne Homogenicze Model obiektowy (Strukturalny CBR) Dziedziczenie klas Relacje między obiektami (całość-część) Język reprezentacji przypadków CAUSEL

19 Wyszukanie podobnych RETRIEVE REUSE REVISE RETAIN Podstawowe założenie: Podobne problemy mają podobne rozwiązania Funkcja: przypadek x przypadek ->[0,1] Lokalne i globalne podobieństwo Metoda najbliższego sąsiedztwa NN Stopień podobieństwa = użyteczność

20 Adaptacja rozwiązania RETRIEVE REUSE REVISE RETAIN Automatyczna Bez modyfikacji rozwiązania Analogia transformacyjna Analogia derywacyjna Adaptacja przez komponowanie Interaktywna Konwersacyjny CBR

21 Weryfikacja rozwiązania RETRIEVE REUSE REVISE RETAIN Faza ta często jest pomijana. Kryteria oceny: Poprawność rozwiązania Jakość rozwiązania Weryfikacja poprzez symulację komputerową Weryfikacja (ocena użytkownika) w rzeczywistym świecie

22 Zapamiętanie precedensu RETRIEVE REUSE REVISE RETAIN Uczenie poprzez zapamiętywanie. Nowe doświadczenia Poprawianie miary podobieństwa Reorganizowanie bazy przypadków Zapominanie precedensów Zdobywanie wiedzy o adaptacji rozwiązań Tworzenie drzewa decyzyjnego

23 Gdzie jest wiedza? Słownik (wykorzystywane cechy) Miara podobieństwa Transformacje rozwiązań Baza przypadków

24 Zalety CBR Redukuje koszty pozyskania wiedzy Stosunkowo niewielki kosz utrzymania Prosta nauka poprzez zapamiętywanie Wykorzystanie istniejących danych Wysoka akceptowalność przez użytkowników końcowych

25 CBR na świecie Ponad 35 uniwersytetów na świecie Kilkaset artykułów Kilkadziesiąt akademickich systemów Kilkanaście komercyjnych wdrożeń Konferencje narodowe (Niemcy od 1991) i Europejskie od 1993 I Ogólnoświatowa konferencja CBR 1995

26 Podsumowanie Podobne problemy mają podobne rozwiązania. Rozwiązanie problemu (reguła 4R :) Wyszukanie podobnych przypadków Wykorzystanie rozwiązań z precedensu (ów) Weryfikacja rozwiązania Włączenie rozwiązania do bazy Łatwość implementacji i używania Akceptacja użytkowników końcowych

27 Pytania...

28 Dziękuję za uwagę Retrieve Revise Reuse Retain