Lukasz Stafiniak pages | SI / SI

en pl

Ciekawe nowości na stronie:

Pracownie i zadania:

Pracownia z sieci bayesowskich: Dependence modeling trails (kurs online z Helsinek)
- Wykład: Wnioskowanie na probabilistycznych sieciach przekonań
- A Tutorial on Learning With Bayesian Networks (David Heckerman, Mar. 1995)
- Learning Causal Relations in Multivariate Time Series Data (Pu Chen and Hsiao Chihying)
- A Short Course on Graphical Models (Mark A. Paskin)
Pracownia z sieci bayesowskich 2:
- JavaBayes (kopia lokalna na stronie wykładowcy)
  - JavaBayes Home (dokumentacja)
- pebl: Python Environment For Bayesian Learning
- Open Bayes for Python (częściowy klon BNT, tylko zmienne dyskretne)
  - svn download
- Bayes Net Toolbox for Matlab
  - How to use BNT
  - LinkStrength Package for BNT
- Bayesian Network tools in Java (BNJ) (problematyczny, nieaktywny)
- Norsys Software Corp. Netica (brak automatycznego wykrywania struktury, tylko uczenie parametrów)
  - Bayes Net Library
  - Basic Decision Making with Bayes Nets
Warunki oceny małych projektów
1. Za wersję podstawową można dostać maksymalnie 15 punktów (za ładny raport z dołączonymi — tzn. wysłanymi mailem lub wskazanymi url-em — źródłami w postaci wykorzystanych programów / skryptów dla przeprowadzonych eksperymentów / danych).
2. Wystarczy jedno rozszerzenie, aby uzyskać maksimum: 20 punktów (ale nie dostaje się ich automatycznie za samo zrealizowanie wersji rozszerzonej). Niektóre rozszerzenia mogą się okazać bardzo mało czasochłonne w realizacji, nie ma konieczności ograniczać się do jednego ;-)
3. Jeśli wkręcisz się w realizowanie rozszerzeń, dodatkowe rozszerzenia mogą stanowić treść dużego projektu (końcowego). Wkład pracy w duży projekt powinien być przynajmniej około trzykrotnie większy niż w pojedyńczy mały projekt.
4. Wiele rozszerzeń ma dwa warianty: poglądowy “teoretyczny” (zaproponuj) i rzeczywisty (zaprogramuj). Na mały projekt często wystarczy wariant poglądowy, na duży projekt wskazany jest wariant rzeczywisty.
5. Warto przeczytać treść wszystkich wariantów projektów.
6. Patrząc na kryteria oceniania:
  - Trzeba zrobić dwa rozszerzone zadania i bez mankamentów (20+20=40pkt), lub trzy podstawowe zadania (średnio 40/3=13pkt za zadanie — wystarczy wersja podstawowa) żeby mieć szansę na piątkę. (40pkt za małe projekty)
  - Trzeba zrobić dwa podstawowe zadania bez mankamentów (15+15=30pkt) lub trzy podstawowe niedopieszczone zadania (średnio 10pkt za zadanie) żeby mieć szansę na cztery z plusem (30pkt za małe projekty).
  - Trzeba zrobić dwa podstawowe niedopieszczone zadania (10+10=20pkt) lub jedno rozszerzone zadanie bez mankamentów zeby mieć szansę na czwórkę.
7. Proszę nie czekać na ostatnią chwilę, bo pokazując wcześniej można ze mną negocjować co znaczy “bez mankamentów”.
8. Można też wynegocjować uznanie wyników częściowych z dużego projektu jako zadanie, jeśli będą zgłoszone w odpowiednim terminie (ale wtedy punktacja za duży projekt będzie mierzyć późniejszy wkład pracy).
9. Jeśli zadanie ma kilka wariantów wersji podstawowej, to są one jednocześnie rozszerzeniami (tzn. realizując dwie wersje podstawowe robimy zadanie rozszerzone).
Projekt z sieci przekonań: warianty
1. Data Mining. Znajdź strukturę sieci z danych wykorzystując jedno z poznanych narzędzi.
  1. Wersja podstawowa: odnajdź w internecie zbiór danych dla interesującego i/lub zrozumiałego dla Ciebie zagadnienia. Zinterpretuj zależności w powstałej sieci (m.in. popatrz na ich siłę; popatrz czy zależność przyczynowa jest oczywista). Opisz kilka wyników zapytań do sieci (tzn. rozkładów prawdopodobieństw dla pewnych zmiennych przy ustalonych wartościach pewnych spośród pozostałych zmiennych): czy są intuicyjne, czy zachodzi np. “explaining away” etc.
  2. Rozszerzenie 1: samodzielnie zgromadź dane. Możesz np. podpiąć się do jakiejś aplikacji i przeprowadzić logowanie jej zmiennych. Możesz skonstruować model deterministyczny jakiegoś zjawiska (tylko zmienne wejściowe będą losowane), ale część zmiennych wejściowych pozostawić ukrytych przed modelowaniem statystycznym (co spowoduje, że część z pozostałych zależności nabierze charakteru losowego).
  3. Rozszerzenie 2: wyraź posiadaną wiedzę o zagadnieniu w postaci więzów (twardych, a może również miękkich), lub w postaci początkowej sieci przekonań. Porównaj sieć znalezioną z uwzględnieniem twojej wiedzy, z siecią którą (to samo lub inne) narzędzie odnalazło przy braku wiedzy startowej (z w pewnym sensie “jednostajnym” rozkładem a priori na struktury sieci).
  4. Rozszerzenie 3: urozmaić strukturę sieci: węzły innego typu niż dyskretne ze stabulowanymi prawdopodobieństwami warunkowymi (np. dla zmiennych ciągłych); zmienne ukryte (nie obserwowane, wogóle albo zazwyczaj, w danych uczących).
2. Akwizycja i reprezentacja wiedzy. Samodzielnie skonstruuj sieć przekonań (jej strukturę i parametry).
  1. Wersja podstawowa: skonstruuj prostszą sieć (wariant (a)) lub wprowadź/zaimportuj trudniejszą sieć odnalezioną w internecie (wariant (b)). Opisz zależności w sieci oraz kilka wyników zapytań do sieci (jak w wariancie Data Mining).
  2. Rozszerzenie 1: skonstruuj sieć przeprowadzając wywiad z osobą, która zna się na analizowanym zagadnieniu (wariant ©). Osoba ta nie może być kolegą (koleżanką) z naszego przedmiotu; dobrze, jeśli wogóle nie jest studentem bądź absolwentem informatyki lub matematyki. (Częścią zadania jest namówienie kogoś, by nam pomógł.) W raporcie zamieść transkrypcję fragmentu wywiadu.
  3. Rozszerzenie 2: zaplanuj (i może też zaprogramuj) mechanizm gromadzenia danych w trakcie użytkowania modelu, oraz okresową automatyczną aktualizację parametrów modelu (a być może również struktury modelu, choć to mniej bezpieczne); możesz potrzebować narzędzia dopuszczającego nieobserwowanie niektórych zmiennych w danych uczących. Rozważ “trade-off” pomiędzy konserwatywnym zachowaniem posiadanego modelu a nadążaniem z modelem za gromadzonymi danymi. Niektóre narzędzia pozwolą ci wyrazić stary model bezpośrednio, np. jako parametry “a priori” dla rozkładu Dirichleta. Jeśli twoje narzędzie tego nie potrafi, będziesz musiał wygenerować odpowiednią porcję danych ze starego modelu, żeby zrównoważyć wpływ wiedzy względem wpływu napłyniętych obserwacji. Przykłady gromadzenia danych:
    - Jeśli model służy do predykcji, to użytkownik może powiedzieć później, co stało się naprawdę.
    - Jeśli model wspiera podejmowanie decyzji, to użytkownik może później ocenić podjętą decyzję.
    - Jeśli dane (ang. “evidence”) w zapytaniach użytkownika nie mają charakteru hipotetycznego ale są zaobserwowane, np. są to objawy obserwowane u pacjenta, to zarejestruj je; dobry model pomiędzy objawami może zaoszczędzić na badaniach diagnostycznych. Gromadząc dane spływające z całego regionu wydobywamy wiedzę o charakterze epidemiologicznym itd.
  4. Rozszerzenie 3: urozmaić strukturę sieci (jak w rozrzerzeniu 3 wariantu Data Mining): węzły innego typu niż dyskretne, zmienne ukryte itd.
3. Teoriodecyzyjne heurystyki w przeszukiwaniu i grach. Skonstruuj sieć przekonań z węzłem/węzłami decyzyjnymi oraz węzłem wartości/nagrody/użyteczności/kosztu; patrz Basic Decision Making with Bayes Nets. Dziedziną modelu ma być problem przeszukiwania (gra jedno-osobowa) lub gra dwuosobowa.
  1. Wersja podstawowa: Zmiennymi “środowiskowymi” są parametry stanu przeszukiwania / stanu gry. Zmienna / zmienne decyzyjne dostarczają parametrów operatorowi przejścia do kolejnego stanu. Stan gry może decydować, które zmienne są obserwowane w trakcie używania modelu (np. kolejne decyzje nasze/przeciwnika w grze o niewielkiej ilości ruchów, np. pokerze czy “oczku”). Niektóre zmienne mogą wogóle nie być obserwowalne w trakcie używania struktury, ale być łatwo dostępne dla uczenia struktury (np. kolejny ruch przeciwnika).
  2. Rozszerzenie 1: zamiast konstruować model “z palca” albo “z internetu”, zaprogramuj generator danych a następnie znajdź model z wygenerowanych danych. W generowanych danych za wartość zmiennej “heurystyka” podstaw estymowaną odległość od rozwiązania (poprzez najkrótszą z rzeczywiście znalezionych ścieżek do rozwiązania) lub wypróbkowane prawdopodobieństwo wygranej (jaka część spośród rozgrywek przechodzących przez dany stan zakończyła się wygraną). W generatorze wykorzystaj najlepsze dostępne ci heurystyki żeby przyspieszyć generowanie i poprawić jakość danych.
  3. Rozszerzenie 2: zaproponuj / zaprogramuj mechanizm uaktualniania modelu w czasie rozgrywki lub po kilku rozgrywkach.
  4. Rozszerzenie 3: zaproponuj / zaprogramuj strategię przeszukiwania / strategię rozgrywki, która nie kieruje się chęcią maksymalizacji nagrody, ale chęcią jak najsprawniejszego poprawienia jakości modelu.
    1. Rozszerzenie 4: zaproponuj, wykorzystując teorię bayesowskiego uczenia ze wzmocnieniem, mechanizm optymalnego wyboru ruchu, uwzględniający, że poprawienie jakości modelu poprawi skuteczność maksymalizacji nagrody.
Pracownia z przeszukiwania w przestrzeni stanów
Pracownia z więzów i z gier
- generic constraint development environment — Gecode
  - Modeling with Gecode
  - Constraint Propagation — Models, Techniques, Implementation (Guido Tack)
- aplet z warcabami
- Mini Gosix (autor: Tautrimas Pajarskas) (gra planszowa Gosix stworzona przez: Pierre Canuel)
Projekt z przeszukiwania heurystycznego i gier: warianty
1. Znajdowanie ścieżki w dynamicznym środowisku: zaprogramuj agenta przechodzącego z punktu startowego do punktu docelowego w sytuacji, gdy mapa którą dysponuje nie odpowiada dokładnie rzeczywistości, albo rzeczywistość jest zmienna.
  1. Wersja podstawowa: mamy sytuację podobną do rozpatrywanej na pracowni: szukamy ścieżki na dwuwymiarowej arenie. Jednak mamy do dyspozycji dwie mapy: mapę, która jest w pełni dostępna algorytmowi, oraz arenę, którą będziemy udostępniać algorytmowi tylko dla komórek sąsiadujących z zajmowaną przez agenta (możesz udostępnić bezpośrednio sąsiadujące bądź sąsiadujące w ustalonym promieniu); algorytm oczywiście powinien zapamiętywać potrzebną informację. Załóżmy wstępnie, że mapa nie ma fałszywych przeszkód. Zaprowadź agenta do celu minimalizując, w kolejności istotności: ilość rzeczywiście podjętych przez agenta kroków, złożoność obliczeń wykonywanych podczas ruchu agenta, złożoność obliczeń wstępnych. Sugerowane algorytmy: “Adaptive A*”, “Real-Time Adaptive A*”, “Prioritorized Learning Real-Time A*”.
    - Alternatywnie, agent dysponuje pełną informacją o arenie, ale na arenie pojawiają się nowe przeszkody w przypadkowych miejscach i momentach.
  2. Rozszerzenie 1: jeśli w wersji podstawowej udostępniałeś algorytmowi jedynie komórki areny bezpośrednio sąsiadujące z agentem, to teraz rozszerz “pole widzenia” do większego promienia. Wariant (1a): wprowadź “zawodność obserwacji”: specjalne komórki, które z sąsiedztwa wyglądają na osiągalne, ale akcja wkroczenia na nie okazuje się niewykonalna. Wariant (1b): wprowadź zmienny cel: na arenie cel może okazać się w innym miejscu, niż był na mapie (agent musi zaobserwować komórkę fałszywego celu, żeby się przekonać) — jednak zwykle niedaleko od celu z mapy.
    1. Rozszerzenie 2: wolno przemieszczający się cel: po zbliżeniu się agenta do celu, ten zaczyna uciekać.
  3. Rozszerzenie 3: uwzględnij możliwość występowania na arenie “okazji”: komórek osiągalnych, które nie były osiągalne na mapie. Sugerowane algorytmy: “Lifelong Planning A*”, “D* Lite”.
    - Alternatywnie, agent dysponuje pełną informacją o arenie, ale arena może się w każdej chwili “nieznacznie” zmienić.
2. Konstrukcja heurystyk: rozwiąż (napisz rozwiązywaczkę) przy pomocy algorytmu A* jedną z łamigłówek z budapesztańskich mistrzostw.
  1. Wersja podstawowa: Paweł Rychlikowski sugeruje Hiroimono lub Divide into Squares.
  2. Rozszerzenie 1: rozwiąż inną spośród łamigłówek. Porównaj opracowane przez ciebie heurystyki: jakie idee mają wspólne, a co jest w nich specyficzne dla zadania?
  3. Rozszerzenie 2: najpierw rozwiąż łamigłówkę algorytmicznie (tzn. tak jak na pracowni z Programowania) (wariant a) lub więzami (wariant b), a następnie algorytmem A*. W jaki sposób przekształciłeś algorytm rozwiązywania problemu w heurystykę?
3. Sokoban: rozwiąż (napisz rozwiązywaczkę) przy pomocy algorytmu A* grę logiczną Sokoban.
  1. Rozszerzenie 1 — strategia a taktyka: podziel rozwiązywaczkę na dwa poziomy. Na poziomie strategicznym, algorytm A* szuka rozwiązania w przestrzeni stanów taktycznie istotnych, gdzie pojedyncza akcja wymaga wielu kroków magazyniera (w szczególności, dokładne położenie magazyniera jest nieistotne, istotne są pozycje osiągalne przez magazyniera). Na poziomie taktycznym, zaprogramuj mechanizm znajdowania konfiguracji taktycznie istotnych osiągalnych z bieżącej konfiguracji. Poziom taktyczny powinien zwracać zbiór akcji-taktyk: konfiguracja wynikowa (dla poziomu strategicznego), faktyczne ruchy magazyniera do wykonania (dla systemu gry). Przykład: # to ściana, * to skrzynia, tylko krańcowe pozycje są istotne:
```
#*#    # #     # #     # #
# #    #*#     # #     # #
# #    # #     #*#     # #
# #    # #     # #     #*#
```
  2. Rozszerzenie 2: wykorzystaj programowanie więzów w implementacji pozmiomu taktycznego.
  3. Rozszerzenie 3: Nie proponuj poziomowi strategicznemu martwych konfiguracji w rodzaju zablokowanych skrzyń:
```
**      #*
###      #
```
    Wykrywaj martwe konfiguracje ogólnym mechanizmem a nie przez ręczne zakodowanie szczególnych przypadków: np. przy pomocy więzów, albo algorytmu A* odpalonego na istotnym dla danej skrzyni fragmencie konfiguracji, żeby sprawdzić czy da się ją ruszyć.
  - Trochę literatury:
    - Sokoban Solver Rolling Stone, bardzo ciekawa strona, w szczególności
      - Our Program - Rolling Stone
      - Pushing the Limits: New Developments in Single-Agent Search Andreas Junghanns, Jonathan Schaeffer (prezentacja)
    - Sokoban Wiki: Simple solver, Solver Statistics
    - Ta metoda nas nie interesuje, ale praca jest ciekawa: Evolving a compact, concept-based Sokoban solver (Tom Schaul)
4. Gry z limitem czasowym. Gry w czasie rzeczywistym.
  1. Wersja podstawowa wariant (a): zaimplementuj lub zmodyfikuj istniejący program-grę dwuosobową, tak aby pozwalał na grę dwóch różnych algorytmów przeciw sobie (może to być ten sam algorytm ale z różnymi parametrami).
  2. Wersja podstawowa wariant (b): zaprogramuj modyfikację algorytmu alfa-beta odcięć tak, aby przerywał obliczenia w momencie wyczerpania się czasu zegarowego przeznaczonego na ruch, zwracając najlepszy ruch wedle dokonanych obliczeń. Wykorzystaj np. iteracyjne pogłębianie.
  3. Rozszerzenie 2: zaproponuj / zaprogramuj (np.) modyfikację algorytmu alfa-beta odcięć tak, aby działał w ramach czasu zegarowego przeznaczonego mu na całą grę. Jeśli suma czasów zużytych na podjęcie ruchów przez gracza przekroczy ten czas, gracz przegrywa. Możesz dla uproszczenia uznać, że algorytm myśli tylko w czasie podejmowania przez siebie ruchu. Algorytm ma do dyspozycji czasy wykorzystane przez przeciwnika, grającego z tym samym limitem. Możliwie rozsądnie wyznacz ilość obliczeń/czasy na poszczególne ruchy (możesz eksperymentować).
  4. Rozszerzenie 3: zmodyfikuj wariant (a), zaprogramuj współbieżne/równoległe asynchroniczne działanie algorytmów. Tzn. każdy gracz może wykonać kilka ruchów pod rząd, jeśli drugi gracz nie zdąży wykonać ruchu w międzyczasie. Reguły twojej gry muszą dać się jakoś zinterpretować w takiej sytuacji. Gdy gracze doprowadzą do jakiegoś rodzaju stagnacji, to mogą postulować remis.
  5. Rozszerzenie 4: zaproponuj / zaprogramuj rozsądny sposób dysponowania czasem w sytuacji z rozrzerzenia 3, np. przetestuj różne strategie.
5. General Game Playing. To zadanie nie jest przypisane konkretnemu zestawowi zadań, bo obejmuje szerszy zakres materiału z wykładu. Można je oddać w terminie dowolnego zestawu zadań.
  1. Wersja podstawowa wariant (a): Uruchom system GGP: serwer gier i klientów (wykorzystaj dostępnego gotowego gracza).
  2. Wersja podstawowa wariant (b): Sformalizuj być może uproszczoną wersję jednej ze swoich ulubionych gier komputerowych (!) w Game Description Language.
Pracownia z gier 2: udoskonalenia i heurystyki
- Alfa-beta: udoskonalenia
- Quiescence search
- Transposition table albo tzw. afterstates
- Null-move heuristic
- Gry losowe — expecti(mini)max
- Hierarchical Heuristic Search Techniques for Empire-Based Games (Kenrick Mock)
- Informed Search in Complex Games (by Mark Winands)
- General Game Playing Δ
- Case Based Reasoning for Game AI
Ostatnia grupa projektów: planowanie w przestrzeni planów, systemy regułowe, systemy eksperckie, agent, uczenie ze wzmocnieniem, zbiory danych ustrukturowanych: “relational learning”.
1. Uczący się system ekspercki. Być może znasz grę w 20 pytań, być może implementowałeś nawet kiedyś w BASICu program grający w nią, zgadujący słowo pomyślane przez gracza, i rozbudowujący drzewo decyzji poprzez zadawanie graczowi, po jego wygranej, pytania: jak zapytałbyś, żeby odróżnić twój przedmiot X od mojego zgadnięcia Y? Napisz system ekspercki będący udoskonaleniem tej gry. Taki system może mieć wiele zastosowań, np. w diagnostyce.
  1. Wersja podstawowa: zaprogramuj grę w 20 pytań, uczącą się jak wyżej. Wykorzystaj odpowiednie formularze z komentarzami tak, aby małym kosztem uzyskać od użytkownika poprawne językowo słowa-przedmioty do zgadywania oraz pytania o cechy rozważanego przedmiotu, z odpowiedziami “tak/nie”. Zamiast budować drzewo decyzji, dla każdego znanego przedmiotu i każdego posiadanego pytania pamiętaj odpowiedź: tak / nie / nieznana (gdy pytanie nie było jeszcze dla tego przedmiotu zadane). Zgadując przedmiot, wystartuj od zbioru wszystkich znanych przedmiotów. Wybieraj pytania tak, by szybko zawęzić aktualnie rozpatrywany zbiór przedmiotów (np. po zawężeniu do aktualnego zbioru, pytanie ma tyle samo odpowiedzi “tak” co odpowiedzi “nie”). Odrzucaj z rozpatrywanego zbioru przedmioty, dla których odpowiedź jest inna niż udzielona przez gracza (zachowuj przedmioty z odpowiedzią “nieznana”). Zapamiętuj pytania systemu i odpowiedzi użytkownika, by na końcu gdy wiadomo już, o jaki przedmiot chodziło, uaktualnić odpowiedzi pytań z “nieznana” na odpowiednio “tak” lub “nie”, a również wykryć konflikty jeśli odpowiedź się nie zgadza (to oznacza, że gracz wygrał, ale być może oszukiwał) i poinformować o tym.
  2. Rozszerzenie 1: automatycznie twórz i wykorzystuj reguły asocjacyjne. Inaczej niż w “Data Mining”, używaj jedynie niezawodnych reguł asocjacyjnych: wyrzucaj reguły, dla których chociażby jeden znany przedmiot jest kontrprzykładem. Reguła asocjacyjna mówi, że jeśli odpowiedzi na pewien zestaw (jednego, dwóch, trzech, czterech) pytań są takie-a-takie, to odpowiedź na pewne inne pytanie będzie taka-a-taka. Do tworzenia reguł zaadoptuj jeden ze znanych algorytmów (Association rule learning). W czasie zadawania pytań, gdy tylko pewna reguła “odpala” (odpowiedzi na odpowiednie pytania pokrywają się z jej przesłankami), sprawdź pytanie z jej wniosku: jeśli było już zadane, to w przypadku gdy reguła jest niepoprawna wykasuj ją, a jeśli nie było jeszcze zadane, to odłóż je na bok (tak jakby było już zadane). Powróć do pytań “rozstrzygniętych” przez reguły asocjacyjne dopiero, gdy pozostałe pytania nie rozstrzygną problemu — pamiętaj, żeby wykasować reguły, które okażą się błędne.
  3. Rozszerzenie 2: wykorzystaj również zawodne reguły asocjacyjne, uwzględnij zarówno oszacowanie prawdopodobieństwa reguły (\frac{#(!X \wedge !Y)}{#(!X \wedge ?Y)} dla reguły X \Rightarrow Y, gdzie #!X zlicza, ile razy X jest prawdziwe, a #?Y zlicza, ile razy Y jest znane) jak i jakość tego oszacowania (jak często X jest znane oraz jak często Y jest znane gdy X jest prawdziwe).
  4. Rozszerzenie 3: zbuduj odpowiednio dużą bazę wiedzy dla jakiejś praktycznej dziedziny zastosowania systemu eksperckiego, wykorzystując “human computation”: zbuduj system, w którym wielu użytkowników może grać w twoją grę (i być wykorzystywać ją do rzeczywistej diagnostyki), działając na wspólnej bazie wiedzy. Możesz np. zaprogramować serwer http i odpowiedniego klienta.
  - Akinator zgaduje słynne postacie.
2. System ekspercki w zmiennym środowisku. Zaprogramuj w Soar (lub być może w CLIPS) system ekspercki uwzględniający, że obserwacja może wpływać na badany obiekt (może być de facto interwencją), oraz że badany obiekt jest procesem — zmienia się w czasie, z czasem ujawnia dodatkowe informacje.
3. Programowanie indukcyjne. Typy algebraiczne (czyli warianty, sumy rozłączne produktów typów algebraicznych) dają bardzo wygodny sposób reprezentacji danych strukturalnych. Podejmiemy ambitne zadanie z maszynowego uczenia się: indukcję funkcji, czyli będziemy konstruować jak najoszczędniejszą funkcję, która dla zadanych danych wejściowych wygeneruje zadane dane wyjściowe. Zapoznaj się z artykułem Markusa Mottla Using Algebraic Datatypes as Uniform Representation for Structured Data, w szczególności z rozdziałem Generalizing Decision Tree Learning to Algebraic Datatypes i dokończ moją prototypową implementację funind.ml Δ.
  1. Wersja podstawowa:
    - Napisz test-zastosowanie (odpowiednik akapitu (* *** example *** *) z pliku źródłowego).
    - Wprowadź obsługę sytuacji, gdy dane nie opisują funkcji (tzn. gdy tym samym argumentom przypisane są różne wyniki — obecnie program wysypuje się wtedy).
    - Dopisz obsługę gałęzi domyślnych “ _ → “. Patrz: paragraf 3.3 artykułu.
    - Dopisz normalizację “lewej strony” (patrz paragraf 3.1.2 artykułu).
  2. Rozszerzenie 1: Rozszerz algorytm o obsługę zmiennych liczbowych (zapoznaj się z odpowiednimi mechanizmami budowy drzew decyzyjnych).
  3. Rozszerzenie 2: Możesz zmierzyć się z problemem indukcji funkcji rekurencyjnych.
4. CLIPS i Sokoban.
  - Schemat projektu: zrealizuj projekt Sokoban z drugiej listy w języku CLIPS lub Soar.
5. Agent 001. Zapoznaj się z tutorialem 2 (i być może również 3) do systemu Soar.
  1. Wersja podstawowa: zaprogramuj rozszerzenia programu “Eaters” zaproponowane na końcu tutoriala 2: punkty 1, 2, prosty mechanizm dla punktu 3.
  2. Rozszerzenie 1: zaprogramuj bardziej zaawansowany mechanizm dla punktu 3, punkt 4.
6. Agent 002. Zapoznaj się z tutorialami 2 i 3 do systemu Soar.
  1. Wersja podstawowa: zaprogramuj rozszerzenia programu “SoarTanks” zaproponowane na końcu tutoriala 3: punkty 1, 2, któryś spośród punktów 3–5.
  2. Rozszerzenie 1: zaprogramuj punkty 1–5 (czyli o dwa więcej niż w wersji podstawowej).
  3. Rozszerzenie 2: zaprogramuj dodatkowo punkty 6 i 7.
  4. Rozszerzenie 3: zaprogramuj dodatkowo punkt 8.
7. A* real-time beam search. Zaprogramuj algorytm A* z ograniczeniem na rozmiar frontu przeszukiwania (ang. “search fringe”), ale nie poprzez wyrzucanie stanów które się nie mieszczą i dalsze przeszukiwanie, a poprzez podjęcie decyzji co do kroku do podjęcia optymalnie względem posiadanej informacji (tzn. podjęcie akcji na ścieżce do najlepszego według A* stanu) i odrzucenie stanów których ocena była oparta na wybraniu innej ścieżki.
  1. Wersja podstawowa: Zaprogramuj algorytm kontrolujący agenta na bazie A* z następującą “pętlą główną”: przeszukujący aż do wypełnienia bufora “frontu przeszukiwania”, a następnie podejmujący akcje tak długo aż zwolni się miejsce we “froncie przeszukiwania”.
  2. Rozszerzenie 1: Zaprogramuj ten algorytm w systemie Soar w zgodzie z jego “filozofią”.
  3. Rozszerzenie 2: Zaprogramuj sytuację testową, w której opłaca się mniej planować wprzód przed rozpoczęciem działania i pomiędzy akcjami: np. współzawodnictwo agentów w “czasie rzeczywistym”, zmienne środowisko. Porównaj algorytm z tego zadania z algorytmem który po prostu wykonuje ustaloną ilość kroków algorytmu A* pomiędzy akcjami.
8. Reinforcement Learning oraz zastosowanie systemów reguł produkcji do programowania agentów: Soar.
  1. Wersja podstawowa: Zapoznaj się z tutorialem RL w systemie Soar. Rozszerz agenta Eaters lub SoarTanks tak, aby wykorzystywał uczenie ze wzmocnieniem.
    - Rozszerzenie: Zademonstruj, że agent rzeczywiście z czasem (dzięki uczeniu ze wzmocnieniem) zdobywa coraz więcej punktów.
9. Reinforcement Learning oraz zastosowanie systemów reguł produkcji do programowania agentów: RL-Competition i CLIPS.
  1. Wersja podstawowa: Zapoznaj się z dziedzinami Reinforcement Learning Competition 2009, zainstaluj oprogramowanie (kopia lokalna Δ). Wybierz jednego z dostępnych agentów i zapoznaj się z jego kodem źródłowym: C++ helicopter; Java mario, octopus, tetris; Python acrobot; Matlab tetris; (jest też dostępny interfejs dla Lispu ale nie ma dużego przykładowego agenta). Uruchom tego agenta i zademonstruj jego działanie.
    - Rozszerzenie 1: Zastosuj dla tego agenta uczenie ze wzmocnieniem (zaimplementuj wybrany algorytm). Zademonstruj, że agent rzeczywiście z czasem (dzięki uczeniu ze wzmocnieniem) zdobywa coraz więcej punktów.
    - Rozszerzenie 2: zanurz CLIPS i oprogramuj w nim inteligentne zachowanie twojego agenta (może nie mieć związku z uczeniem ze wzmocnieniem).
10. Planowanie w przestrzeni planów.
11. Statistical Relational Learning. System Alchemy. Modele graficzne którymi zajmowaliśmy się na pierwszej liście zadań wyrażały jedynie własności obiektów i zależności pomiędzy własnościami pojedynczego obiektu. W języku logiki byłyby to predykaty jednoargumentowe oraz formuły z jedną zmienną: da się je wyrazić w rachunku zdań. Alchemy pozwala wyrażać formuły pierwszego rzędu, relacje wiążące wiele obiektów i zależności pomiędzy tymi relacjami.
  - Schemat projektu: zrealizuj w Alchemy wybrany projekt z pierwszej listy zadań, ale z naciskiem na możliwości Alchemy których nie dają zwykłe sieci przekonań (sieci bayesowskie). Możesz np. wykorzystać skomplikowaną bazę danych z wieloma tabelami.
  - Literatura: 10-803: Markov Logic Networks (Machine Learning Department, Carnegie Mellon University)
Pracownia Soar
1. Soar Home
  - Soar Suite 9.0, Soar Suite 9.1 Beta
Pracownia CLIPS
1. CLIPS Home
Pracownia Soar 2, uczenie ze wzmocnieniem
1. Omówienie systemu Soar Δ (odp Δ)
2. AGI/RL.pdf Δ
Pracownia systemy bogate w wiedzę 1: wnioskowanie, Cyc, OpenCyc, Texai
1. Cyc 101 Tutorial
  1. all PPT slides
2. Foundations of Knowledge Representation in Cyc (Stephen Reed) OpenCycTut.pdf Δ
3. Learning to Reason Knowledge Acquisition in Cyc (świetna prezentacja!)
  - Free Semantic Content: Using OpenCyc in Semantic Web Applications (słabsza, ale więcej o Semantic Web)
4. Indukcja, abdukcja.
5. Parsowanie i generowanie języka naturalnego.
6. The Texai English Bootstrap Dialog System
Pracownia systemy bogate w wiedzę 2: RDF, SPARQL, OWL, DBpedia, Freebase
1. RDF (Primer, Concepts, Syntax, Semantics, Vocabulary, and Test Cases) i SPARQL
  - RDF dostarcza struktury danych i narzędzi do przechowywania wiedzy, ale również zrębu ontologii do jej ustrukturowania
  1. SPARQL Tutorial przy Java Semantic Web framework Jena
  2. Innym enginem Javy do pracy z RDFami jest Sesame
2. OWL2, OWL Features, OWL Guide, OWL Reference
  - Dopiero OWL dostarcza trochę semantyki dla wiedzy: zrąb ontologii zależności pomiędzy relacjami oraz narzędzia do wnioskowania.
  - OWL wprowadza ograniczenia na wyrażalność, by umożliwić szybkie wnioskowania (logiki deskryptywne). OWL 2 jest bardziej ekspresywny niż OWL-DL. OWL Full to wariant bardziej zgodny z RDF Schema, “nieznacznie” wykraczając poza logiki deskryptywne.
  - Solvery dla DL, Bossam: rule engine dla OWL
3. DBpedia, DBpedia Project website to po pierwsze: Wikipedia przerobiona automatycznie na bazę RDFową, ma m.in. wstępy do wszystkich artykułów w kilku językach w tym po polsku, kategorie oraz infoboxy; po drugie: ma ambicję agregata ontologii dla LinkedData (ontologia samej DBpedia jest płytka, “organizuje infoboxy”)
  1. Dostęp do DBpedii
    1. LinkedData pozwala dobrać się do pojęcia poprzez http, np. http://dbpedia.org/resource/Busan, http://dbpedia.org/resource/The_Lord_of_the_Rings (zwraca jako RDFy “/resource/” lub jako html dla przeglądarki “/page/”)
      - (SWEO Community Project: Linking Open Data / Data sets)
    2. końcówka SPARQL, np. People who were born in Berlin before 1900
      - SPARQL jest poszerzony o “text search”, przydatne m.in. do abstraktów (wstępów artykułów)
    3. Download
  2. Integracja z innymi źródłami: zwróć uwagę na “owl:sameAs” oraz “dbpprop:wordnet_type”, np. http://dbpedia.org/page/Air_France
    - Integracja z (Open)Cyc
    - “owl:sameAs”=“is owl:sameAs of” (równość jest symetryczna), ale DBpedia i Freebase nie przeprowadzają wnioskowania; proste wnioskowania można zakodować jako kwerendy SPARQL
  3. Publikacje, wczesne blogi:
    - Did You Blink? The Structured Web Just Arrived
    - DBpedia - niedowiarkom gwóźdź do trumny
4. Przeszukiwanie internetowych baz RDFowych: watson, Swoogle, razorbase, DBpedia URI Lookup
5. Freebase (from Metaweb)
  - Freebase jest rozszerzana przez zarejestrowanych użytkowników jak Wikipedia, ale użytkownicy nie mogą modyfikować istniejących fragmentów (żeby nie zepsuć aplikacji — kompatybilność), co pogarsza jakość i zwiększa redundancję.
  - Kiepska (nieprzemyślana) obsługa negacji i braku wiedzy.
  1. Using the Query Editor
    - Metaweb Query Language Reference Guide
    - Patrz od strony 31.
    - Metaweb używa reprezentacji grafowej podobnej do RDF (ale swojej własnej przestrzeni nazw), z tym że po prawej stronie strzałki jest węzeł i/lub wartość, zamiast węzła lub wartości tak jak w RDF (czyli mamy czwórki a nie trójki).
    - MQL pozwala nie tylko czytać, ale też wstawiać do bazy (jak SQL).
    - MQL używa JSON.
    - Pola bez wartości w zapytaniu to odpowiedniki zmiennych wzorca.
    - Mocno bazuje na metaforze obiektu (hmm… JavaScrit?), pole “id”:null przechwytuje identyfikator obiektu (“subject” czyli pierwszy element trójki/czwórki).
      - Obiekt może mieć wiele identyfikatorów.
    - Są “dzikie karty” dla atrybutów, oraz operator inwersji biorący wartość i zwracający atrybut obiektu o tej wartości.
    - Inne więzy niż równość na atrybucie: “date_of_birth<” : “2000″ (od strony 78)
    - Wiele konstrukcji, ale nie mogę znaleźć zmiennych!
  2. Query Editor
  3. Freebase RDF (Linked Data)
  4. Przykładowa aplikacja: Sets (jej kod źródłowy)
  5. Download: Freebase Data Dumps