Sztuczna inteligencja

Wykład

2022-10-05
Przestrzeń stanów i rozwiązywanie problemów przez jej przeszukiwanie (do sformułowania prostych problemów - sformułowania omawiać będziemy na następnych zajeciach)
- Materiały
  - Solving problems by searching
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Czym jest przestrzeń stanów.
  - Co oznacza, że środowisko jest obserwowalne, dyskretne, znane, deterministyczne (ang. observable, discrete, known, deterministic)
  - Co rozumiemy pod pojęciem formulate--state--execute design pattern.
  - Jakie elementy definiują problem.
  - Czym jest rozwiązanie problemu.
  - Wyjaśnij rolę i znaczenie pojęć usefulness oraz abstraction.
2022-10-12
Omawiamy sformułowania prostych problemów.
- Materiały
  - Solving problems by searching
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Umieć opisać proste problemy (toy problems) w kategoriach stanu, stanu początkowego, działań, modelu przejścia, testu celu, kosztu ścieżki.
2022-10-19
Elementarne i nieelementarne metody przeszukiwania przestrzeni stanów. Drzewo przeszukiwań, przeszukiwania wszerz, w głąb, uniform-cost search.
- Materiały
  - Solving problems by searching
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Co to jest drzewo przeszukiwania.
  - Zdefiniuj i wyjaśnij ogólny algorytm przeszukiwania drzew.
  - Zdefiniuj i wyjaśnij ogólny algorytm przeszukiwania grafów.
  - Opisz algorytm przeszukiwania wszerz.
  - Opisz algorytm uniform-cost search.
  - Opisz algorytm przeszukiwanie w głąb.
  - Wyjaśnij różnice między strategiami przeszukiwania typu informed oraz uninformed.
2022-10-26
Elementarne i nieelementarne metody przeszukiwania przestrzeni stanów. Best first search i A*.
- Materiały
  - Solving problems by searching
  - Rysunek ideowy - przykładowa przestrzeń preszukiwania do testowania algorytmów
  - Introduction to A* (bardzo dobre)
  - Introduction to A* (nowa wersja poprzedniego z animacjami)
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Wyjaśnij różnice między strategiami przeszukiwania typu informed oraz uninformed.
  - Jak możemy mierzyć wydajność rozwiązywania problemów.
  - Wyjaśnij ideę heurystycznych (informed) strategii przeszukiwania;
  - Co to jest funkcja heurystyczna;
  - Zdefiniuj i wyjaśnij algorytm przeszukiwania best first search (w wariancie zachłannym i A*).
2022-11-09
Inne niż "klasyczne" metody przeszukiwania
- Materiały
  - Beyond classical search (do algorytmu genetycznego, ale już bez niego)
  - Rozdział 8: "Means-Ends Analysis", strona 81
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Podać przykłady problemów z nieistotną ścieżką (irrelevant path).
  - Wyjaśnić, co to jest state-space landscape.
  - Wyjaśnić, co to jest funkcja celu (objective function).
  - Opisać działanie algorytmu hill-climbing.
  - Podać możliwe modyfikacje algorytmu hill-climbing.
  - Opisać działanie algorytmu symulowanego wyżarzania (simulated annealing).
  - Opisać działanie algorytmu Means-Ends-Analysis.
2022-11-16
Algorytm genetyczny
- Materiały
  - Rozdział 39: "Algorytmy genetyczne", strona 295
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Opisać poszczególne etapy algorytmu genetycznego.
  - Opisać operację krzyżowania i mutacji.
  - Opisać podstawową metodę selekcji osobników, tzw. metodę ruletki.
2022-11-23
Algorytm genetyczny - przykładowe zadania
- Materiały
  - ...
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Umieć zastosować algorytm genetyczny dla wybranych, prostych problemów.
2022-11-29
Beyond classical search (ciąg dalszy - searching in continuous space)
- Materiały
  - Beyond classical search
  - Metoda gradientowa
    - Metoda gradientowa - idea
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Wiedzieć, co to jest gradient.
  - Umieć wykorzystać gradient w celu znalezienia ekstremum funkcji.
2022-12-07
Beyond classical search (ciąg dalszy - and-or drzewa)
Adversarial search (mini-max, mini-max z cięciami)
- Materiały
  - Beyond classical search
  - And-Or drzewa
    - Tabela przejść
    - Pełne drzewo zbudowane w oparciu o tabelę przejść
    - Rozwiązanie
    - Uproszczona wersja powyższego drzewa
  - Adversarial search (mini-max, mini-max z cięciami)
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Co to jest contingency plan (strategy) i kiedy musimy go użyć.
  - Czym są and-or drzewa.
  - Wyjaśnij ideę działania algorytmu przeszukiwania and-or drzew.
  - Dlaczego gry są tak interesujące dla sztucznej inteligencji (wskazówka: gry wymagają zdolności do podejmowania decyzji, nawet jeśli obliczenie optymalnej decyzji jest niewykonalne, a każda nieefektywność jest surowo karana).
  - Jak zdefiniować grę jako problem wyszukiwania (zdefiniować pojęcia: stan początkowy, model przejścia, warunek końca, funkcja wypłaty oraz funkcje określające gracza i jego akcje).
  - Co jest optymalnym rozwiązaniem w grach.
  - Zdefiniować i wyjaśnić algorytm mini-max.
2022-12-14
Adversarial search (mini-max, mini-max z cięciami) - ciąg dalszy (analizujemy przykłady dla algorytmu mini-max, analizujemy przypadki gdy można zrezygnować z analizy pewnego poddrzewa - można je odciąć)
- Materiały
  - Adversarial search (mini-max, mini-max z cięciami)
  - Przykład pokazując, iż wybór optymalnego ruchu zależy od głębokości analizy (dla głębokości 1 był to ruch A3, dla głębokości 2 - ruch A1 a dla głębokości 3 - ruch A2)
  - Przykład (Wikipedia) - dwa obrazki: statyczny pokazujący ideę oraz dynamiczny pokazujący co się dzieje
  - Intuicja pokazująca możliwość pominięcia niektórych gałązi
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zdefiniować i wyjaśnić algorytm mini-max.
  - Wyjaśnij, jak działa odcięcie alfa-beta.
2022-12-21
Drzewa decyzyjne
- Materiały
  - Learning from examples (drzewa decyzyjne)
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Co rozumiemy pod pojęciem nauki i dlaczego chcemy, aby agent się uczył.
  - Zdefiniować/wyjaśnić trzy główne rodzaje uczenia się.
  - Co to jest drzewo decyzyjne i jak działa.
  - Zdefiniować i wyjaśnić algorytm uczenia/tworzenia drzewa decyzyjnego.
2023-01-11
Drzewa decyzyjne - ciąg dalszy (przykłady)
- Materiały
  - Learning from examples (drzewa decyzyjne)
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Co rozumiemy pod pojęciem nauki i dlaczego chcemy, aby agent się uczył.
  - Zdefiniować/wyjaśnić trzy główne rodzaje uczenia się.
  - Co to jest drzewo decyzyjne i jak działa.
  - Zdefiniować i wyjaśnić algorytm uczenia/tworzenia drzewa decyzyjnego.
2023-01-18
Sztuczne sieci neuronowe
- Materiały
  - Artificial neural networks. In the search of the brain
  - Dla osób bardziej zainteresowanych tematem: Rozdział 15-23
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Model sztucznego neuronu.
  - Typowe architektury sztucznych sieci neuronowch.
  - Metody nauki.
2023-01-25
Podsumowanie materiału, dyskusje na wybrane tematy
- Materiały
  - ...
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - ...
2023-02-01
Podsumowanie materiału, dyskusje na wybrane tematy
- Materiały
  - ...
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - ...

Ćwiczenia

2022-10-05 (projekt do oddania do 2022-10-11, 23:59) Budujemy prosty system klasyfikujący obrazy
- Materiały
  - problem_01_001.dat
  - problem_01_001_test.dat
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować prosty system klasyfikujący.
2022-10-12 Omawiamy prosty system klasyfikujący obrazy
- Materiały
  - problem_01_001.dat
  - problem_01_001_test.dat
  - task_01_basic_solution.py - jeszcze nie gotowy system, ale najważniejsza jego część funkcjonalna
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować prosty system klasyfikujący.
2022-10-19 (projekt do oddania do 2022-11-06, 23:59) FSM (finite state machine) - konstrukcja chatbot-a przy wykorzystaniu automatu
- Materiały
  - Rysunek ideowy
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zasada działania automatu.
  - Jak wykorzystać automat do budowy prostego chatbot-a.
2022-10-26 (projekt do oddania do 2022-11-08, 23:59) Automat komórkowy i jego wykorzystanie do symulacji pożaru
- Materiały
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Czym jest i jak działa automat komórkowy.
  - Zaimplementować automat komórkowy zgodnie z podanymi regułami.
2022-11-09 (projekt do oddania do 2022-11-22, 23:59) Przeszukiwania wszerz, w głąb oraz uniform-cost
- Materiały
  - Opis zadania
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować wybrane algorytmy przeszukiwania przestrzeni stanów.
2022-11-16 (projekt do oddania do 2022-11-29, 23:59) Algorytm symulowanego wyżarzania
- Materiały
  - Opis zadania
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować algorytmy symulowanego wyżarzania.
2022-11-23 (projekt do oddania do 2022-12-13, 23:59) Boids - symulowanie zachowań stadnych
- Materiały
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować algorytmy symulowanego wyżarzania.
2022-11-29 (projekt do oddania do 2022-12-13, 23:59) Algorytm genetyczny
- Materiały
  - ...
- Zadania
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować algorytmy genetyczny.
2022-12-07 (projekt do oddania do 2022-12-20, 23:59) Algorytm gradientowej minimalizacji funkcji
- Materiały
  - ...
- Zadania
  - Zaimplementować algorytm gradientowej minimalizacji funkcji w formie metody najszybszego spadku z opcją minimalizacji kierunkowej dla następujących funkcji:
    - Płaszczyzna (x+y)
    - Powierzchnia (x^3+5*y^3)
    - Spłaszczony lejek (x^2+2*y^2)
    - Sinus (sin(x)+x/4)
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować algorytmy gradientowej minimalizacji funkcji.

2022-12-14 (projekt do oddania do 2023-01-10, 23:59) Algorytm mini-max

Materiały
- Rozdział 9: "Problem wyboru optymalnego ruchu", strona 91

Zadania (jedno z poniższych)

Zaimplementować grę opisaną w materiale do ćwiczeń.

Zaimplementować metodę mini-max dla drzewa (grafu) zadanego w postaci listy sąsiedztwa. Przykład:

Dla drzewa:
      1
     / \
    2   3
       / \
      /   \
     /     \
    4       5
   / \     /
  6   7   8
  
Plik wygląda tak:
8   # liczba wierzchołków
4   # Ocena wierzchołka 1
12  # Ocena wierzchołka 2
-5  # Ocena wierzchołka 3
6   # Ocena wierzchołka 4
2   # Ocena wierzchołka 5
10  # Ocena wierzchołka 6
-5  # Ocena wierzchołka 7
-7  # Ocena wierzchołka 8
1   # Numer wierzchołka będącego korzeniem drzewa
2 3 # Węzły potomne dla węzła 1
0   # Węzły potomne dla węzła 2
4 5 # Węzły potomne dla węzła 3
6 7 # Węzły potomne dla węzła 4
8   # Węzły potomne dla węzła 5
0   # Węzły potomne dla węzła 6
0   # Węzły potomne dla węzła 7
0   # Węzły potomne dla węzła 8

Co po tych zajęciach powinno się znać / wiedzieć / umieć
- Zaimplementować algorytmy mini-max.

2022-12-21 Praca nad dotychczasowymi projektami
- Materiały
  - ...
- Zadania
  - ...
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - ...
2023-01-11 (projekt do oddania do 2023-01-24, 23:59) Symulacja zachowania
- Materiały
  - Rozdział 12: "Symulacja zachowania", strona 107
- Zadania
  - Zmplementować złożone zachownania osobników i interakcje między nimi bazując m.in. na materiałach powyżej. Dodać element dziedziczenia pewnych cech.
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Implementować złożone zachownania osobników i interakcje między nimi.
2023-01-18 (projekt do oddania do 2023-01-31, 23:59) Drzewo decyzyjne
- Materiały
  - Rozdział 13: "Drzewo decyzyjne jako reprezentacja bazy reguł", strona 109
- Zadania
  - Zaimplementować drzewo decyzyjne dla problemu przedstawionego w materiałach.
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - Zaimplementować drzewo decyzyjne.
2023-01-25 Końcowe sprawdzanie projektów
- Materiały
  - ...
- Zadania
  - ...
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - ...
2023-02-01 Końcowe sprawdzanie projektów
- Materiały
  - ...
- Zadania
  - ...
- Co po tych zajęciach powinno się znać / wiedzieć / umieć
  - ...