Ściana Północna

Sieci bayesowskie to struktury graficzne służące do reprezentowania relacji probabilistycznych między dużą liczbą zmiennych i przeprowadzania wnioskowania probabilistycznego na tych zmiennych. W latach osiemdziesiątych przeprowadzono wiele powiązanych badań dotyczących rozwoju sieci bayesowskich (sieci przekonań, sieci przyczynowych, diagramów wpływu), algorytmów przeprowadzania z nimi wnioskowania oraz aplikacji, które z nich korzystały. Jednak praca została rozproszona po artykułach naukowych. W latach 90. pojawiły się doskonałe algorytmy uczenia sieci bayesowskich z danych. Jednak do 2000 r. nadal wydawało się, że nie ma dostępnego źródła "uczenia się sieci bayesowskich". Celem tego tekstu jest zapewnienie takiego źródła. Aby uczynić ten tekst kompletnym wprowadzeniem do sieci bayesowskich, omówię metody wnioskowania w sieciach bayesowskich i diagramy wpływu. Jednak nie staram się być wyczerpujący w tej dyskusji. Na przykład podaję szczegóły tylko dwóch algorytmów do dokładnego wnioskowania ze zmiennymi dyskretnymi, a mianowicie algorytmu przekazywania wiadomości Pearla oraz symbolicznego algorytmu wnioskowania probabilistycznego D'Ambrosio i Li. Może wydawać się dziwne, że przedstawiam algorytm Pearl, ponieważ jest jednym z najstarszych. Mam ku temu dwa powody: 1) algorytm Pearla odpowiada modelowi ludzkiego rozumowania przyczynowego, oraz 2) Algorytm Pearla z łatwością rozciąga się na algorytm wnioskowania ze zmiennymi ciągłymi.

Część 1 zawiera wprowadzenie do sieci bayesowskich.

Część 2 omawia dalsze relacje między DAG a rozkładami prawdopodobieństwa, takimi jak rozdzielenie d, warunek wierności i warunek minimalności.

Część 3 omawia algorytm przekazywania wiadomości Pearl, symboliczne wnioskowanie probabilistyczne D'Ambrosio i Li oraz związek algorytmu Pearl z ludzkim rozumowaniem przyczynowym.

Część 4 przedstawia algorytm wnioskowania ze zmienną ciągłą, algorytm wnioskowania przybliżonego i wreszcie algorytm wnioskowania abdukcyjnego (znajdowanie najbardziej prawdopodobnego wyjaśnienia)

Część 5 omawia diagramy wpływów, które są sieciami bayesowskimi, uzupełnione o węzły decyzyjne i węzeł wartości oraz dynamiczne sieci bayesowskie i diagramy wpływów.

Częśćy 6 wprowadza algorytmy omawiając zmienne binarne

Część 7 uogólnia to na zmienne wielomianowe . Ponadto w rozdziale 7 omawiam parametry uczenia się, gdy zmienne są ciągłe.

Część 8 przedstawia metodę bayesowską dla struktury uczenia się zarówno w przypadku zmiennych dyskretnych, jak i ciągłych.

Część 9 omawia metodę opartą na ograniczeniach dla struktury uczenia się.

Część 10 porównuje metody bayesowskie i metody oparte na ograniczeniach, a także przedstawia kilka przykładów uczenia się sieci bayesowskich w świecie rzeczywistym.

Część 11 kończy się odniesieniem do zastosowań sieci bayesowskich

To jest tekst dotyczący uczenia się sieci bayesowskich; nie jest to tekst o sztucznej inteligencji, systemach eksperckichh czy analizie decyzji. Jednak ponieważ są to dziedziny, w których sieci bayesowskie znajdują zastosowanie, pojawiają się one często w całym tekście.

Ściana Zachodnia

Przedstawiamy nowe podejście do widzenia komputerowego. Cały proces widzenia, od tworzenia obrazu do pomiaru, rozpoznawania lub reagowania, jest uważany za proces integralny. Widzenie komputerowe jest rozumiane jako zbiór technik pozyskiwania, przetwarzania, analizowania i rozumienia złożonych, wielowymiarowych danych z naszego środowiska na potrzeby badań naukowych i technicznych. W tym sensie bierzemy pod uwagę interdyscyplinarny charakter widzenia komputerowego z jego powiązaniami z praktycznie wszystkimi naukami przyrodniczymi i próbuje wypełnić dwie ważne luki. Pierwsza dotyczy współczesnych nauk fizycznych i wielu nowatorskich technik pozyskiwania obrazów. Druga dotyczy podstawowych badań i zastosowań.

Pierwsza część, Czujniki i obrazowanie, : dotyczy tworzenia i akwizycji obrazu.

Druga część, Przetwarzanie sygnału i rozpoznawanie wzorców, : koncentruje się na przetwarzaniu sygnałów przestrzennych i czasowo-przestrzennych odbieranych przez czujniki obrazowania.

Trzecia część składa się z Galerii aplikacji, : która w zwięzłym przeglądzie przedstawia szeroką gamę przykładów zastosowań zarówno z przemysłu, jak i nauki. Ta część ilustruje, jak wizja komputerowa jest zintegrowana z różnymi systemami i aplikacjami

•  Wprowadzenie

I Czujniki i obrazowanie

•  Promieniowanie i oświetlenie
•  Optyka obrazowania
•  Radiometria obrazowania
•  Wykrywanie obrazu w stanie stałym
•  Kalibracja geometryczna systemów obrazowania cyfrowego
•  Techniki obrazowania trójwymiarowego

II Przetwarzanie sygnału i rozpoznawanie wzorców

•  Reprezentacja sygnałów wielowymiarowych
•  Operatory Sąsiedzkie

•  Ruch
•  Algorytmy trójwymiarowego obrazowania
•  Projektowanie nieliniowych filtrów dyfuzyjnych
•  Wariacyjne wygładzanie adaptacyjne i segmentacja
•  Operatory morfologiczne
•  Modelowanie probabilistyczne w wizji komputerowej
•  Przetwarzanie rozmytego obrazu
•  Obliczenia w sieciach neuronowych do przetwarzania obrazu

III Galeria aplikacji

Ściana Południowa

Dziedzina ta rozpoczęła się w późnych latach pięćdziesiątych i wczesnych sześćdziesiątych XX wieku, kiedy dostępność cyfrowych komputerów umożliwiła naukowcom i inżynierom tworzenie i eksperymentowanie z różnymi modelami procesów ewolucyjnych. Ta wczesna praca zaowocowała wieloma ważnymi paradygmatami WE, w tym programowaniem ewolucyjnym (EP), strategiami ewolucji (ES) i algorytmami genetycznymi (GA), które posłużyły za podstawę większości prac wykonanych w latach siedemdziesiątych XX wieku, okresie intensywnej badanie i udoskonalanie tych pomysłów. Rezultatem był szereg solidnych algorytmów o znacznym potencjale rozwiązywania trudnych problemów naukowych i inżynieryjnych. Pod koniec lat 80. i na początku lat 90. poziom aktywności wzrósł do tego stopnia, że każda z podgrup związanych z podstawowymi paradygmatami WE (GA, ES i EP) była zaangażowana w planowanie i organizowanie własnych, regularnie planowanych konferencji. Jednak w tej dziedzinie narastało poczucie potrzeby większej interakcji i spójności między różnymi podgrupami. Aby dziedzina jako całość dojrzała, potrzebowała nazwy, musiała mieć wyartykułowaną, spójną strukturę, potrzebowała rezerwuaru dla literatury archiwalnej. Lata 90. odzwierciedlają to dojrzewanie, wybierając obliczenia ewolucyjne jako nazwę dziedziny, tworząc dwa czasopisma dla tej dziedziny oraz zobowiązując się do stworzenia tego podręcznika jako pierwszego jasnego i spójnego opisu tej dziedziny.

Ściana Wschodnia

Część I Wprowadzenie

Część II Narzędzia matematyczne

Sekcje 1 : Rozmyte zbiory
A. Definicje
B. Operacje mnogościowe
C. a-Cięcia
D. Kardynalność zbioru rozmytego
E. Włączenia i równości zbiorów rozmytych
F. Wypukłe zbiory rozmyte i rozmyte zbiory strukturalne
G. Zestawy rozmyte L
H. Miary rozmycia

Sekcja 2 : Zasada rozszerzenia, rozszerzone operacje i rozszerzone zbiory rozmyte

A. Zasada rozszerzenia
B. Rozszerzone operacje rzeczywiste
C. Rozszerzone zestawy rozmyte

Sekcja 3 Rozmyte relacje

A. N-Ary Rozmyte relacje
B. Binarne rozmyte relacje
C. Relacje podobieństwa i powiązane tematy
D. Rozmyte zamówienia
E. Równania relacji rozmytych
F. Uogólnione rozmyte relacje

Sekcja 4 : Funkcje rozmyte

A. Różne rodzaje funkcji rozmytych
B. Fuzzy Extremum
C. Całkowanie funkcji rozmytych w (nie) rozmytych przedziałach
D. Różnicowanie
E. Łamigłówka
F. Kategorie zbiorów rozmytych

Sekcja 5 : Miary rozmyte, prawdopodobieństwa / możliwości

A. Miary rozmyte i całki Sugeno
B. Możliwość i prawdopodobieństwo
C. Zdarzeń rozmytych
D. Rozkłady rozmyte

Część III Rozmyte modele i struktury formalne

Sekcja 6 : Logika wielowartościowa i rozmyta
A. Fuzzy Switching Logic
B.Logiki wielowartościowe
C .Fuzzy Modal Logic
D. Logika o wartościach rozmytych
E. Przybliżone rozumowanie

Sekcja 7: Dynamiczne systemy rozmyte

A. Złożoność i niejasność w teorii systemu
B. Systemy rozmyte z czasem dyskretnym
C. Fuzzy Automata
D. Systemy deterministyczne w rozmytym środowisku
E.Liniowe systemy rozmyte
F.Inne zagadnienia związane z nieostrożnością i systemami

Sekcja 8 : Język rozmyty - algorytmy rozmyte

A. Języki rozmyte i gramatyki rozmyte
B. Fuzzy Algorytmy

Sekcja 9 : Rozmyte modele badań operacyjnych
A. Optymalizacja w rozmytym środowisku
B. Grafy rozmyte

Część IV Rozmyte tematy zorientowane na systemy

Sekcja 10 L Skąd się biorą "oni"?
A. Nieformalna dyskusja wstępna
B. Praktyczne oszacowanie funkcji członkostwa
C. Identyfikacja operatorów zbiorów rozmytych
D. Analiza tolerancji z wykorzystaniem zbiorów rozmytych

Sekcja 11 : Od języków programowania do języków naturalnych

A. Rozmyte języki programowania
B. Modelowanie języków naturalnych
C. Dedukcyjne słowne systemy dynamiczne

Sekcja 12 : Rozmyte zbiory w podejmowaniu decyzji

A. Rozmyty porządek rang
B. Podejmowanie decyzji pod kątem wielu kryteriów
C. Agregacja opinii w grupie społecznej. Konsensus
D. Podejmowanie decyzji w warunkach losowości i rozmywania

Sekcja 13 : Fuzzy Control

A. Rozmyta optymalna kontrola
B. Synteza kontrolerów językowych

Sekcja 14: Zbiory rozmyte w systemach uczących się

A. Nauka za pomocą automatów lub rozmytych miar warunkowych
B. Samodoskonalenie rozmytych kontrolerów językowych

Sekcja 15 : Klasyfikacja wzorców za pomocą zbiorów rozmytych

A. Rozpoznawanie wzorców
B. Algorytmy klastrowania
C. Zbieranie informacji

Sekcja 16 : Rozmyta diagnoza

A. Rozróżnianie stanów rozmytych w środowisku probabilistycznym
B. Przedstawienie przyczynowości przez relacje rozmyte

Sekcja 16 : Zbiory rozmyte w identyfikacji struktur

A. Rozmyte modelowanie strukturalne
B. Heurystyczna Synteza Struktury
C. Rozmyte wnioskowanie gramatyczne

Sekcja 17 : Rozmyte gry

Sekcja 18 : Rozmyte zbiory i katastrofy

Część V Przegląd potencjalnych zastosowań

A. Sztuczna inteligencja i robotyka
B. Przetwarzanie obrazu i rozpoznawanie mowy
C. Nauki biologiczne i medyczne
D. Kontrola
E. Stosowane badania operacyjne
F. Ekonomia i geografia
G. Socjologia
H. Psychologia
I. Językoznawstwo
J. Semiotyka
K. Inne tematy

Pisanie funkcji R za pomocą fix()

a) Upewnij się, że domyślnym edytorem tekstu jest Notatnik lub Notatnik ++ (lub dowolny inny wybrany przez Ciebie edytor tekstu). Można to zrobić, korzystając z następujących instrukcji z wiersza polecenia R:
> options (editor="notepad")br> lub podając pełną ścieżkę do preferowanego edytora tekstu, np. coś podobnego do
> options (editor="C:\\Program files\\Notepad++\\Notepad++")br> b) Wpisz fix (my.func3) po znaku zachęty R. Otworzy się edytor tekstu.Wpisz instrukcje, jak pokazano w oknie edytora.



Zamknij okno. Sprawdź, co się dzieje w konsoli R.
c) Co się stanie, jeśli podczas używania poprawki zostanie popełniony błąd składniowy? Aby zobaczyć: Najpierw skopiuj my.func3 do my.func4. Następnie w wierszu polecenia R wpisz poprawkę (my.func4). Zrób celowy błąd składniowy, np. usuń ostatni nawias zamykający. Zamknij okno edytora tekstu. Co dzieje się w konsoli? Co należy zrobić, aby naprawić błąd?
d) Uważnie przestudiuj komunikat w konsoli R, gdy wystąpił błąd składniowy w funkcji utworzonej przez fix ():

> Error in edit(name, file, title, editor) :
unexpected 'yyy' occurred on line xx
use a command like
x <- edit()
to recover
e) Wyjaśnij, dlaczego podany poniżej sposób jest prawidłową odpowiedzią na powyższą wiadomość od oceniającego R:

> my.func4 <- edit () ENTER

OSTRZEŻENIE

Przed napisaniem funkcji rozwiązywania dowolnego problemu: upewnij się, że problem jest dokładnie zrozumiany; upewnij się w 100%, że odpowiednia teoria statystyczna jest poprawnie zrozumiana. Niezastosowanie się do tego jest nieostrożne i niebezpieczne!

Przydział gniazd

W tej sekcji kilkakrotnie omawialiśmy temat przypisywania slotów, ale nie przyjrzeliśmy się algorytmowi. Przypisanie slotów musi zdarzać się stosunkowo rzadko w grze. Przez większość czasu grupa postaci po prostu podąża za swoimi slotami. Przydział zwykle ma miejsce, gdy do formacji zostaje przydzielona grupa wcześniej zdezorganizowanych postaci. Zobaczymy, że dzieje się to również wtedy, gdy postacie spontanicznie zmieniają sloty w ruchu taktycznym. W przypadku dużej liczby postaci i slotów przydział można wykonać na wiele różnych sposobów, po prostu sprawdzając każde możliwe przypisanie i wykorzystując to, które ma najniższy koszt. Niestety liczba zleceń do sprawdzenia bardzo szybko staje się ogromna. Liczba możliwych przypisań k znaków do n gniazd jest określone wzorem permutacji:

_nP_k ≡ n! /(n ?k)!

W przypadku formacji składającej się z 20 miejsc i 20 znaków daje to prawie 2500 bilionów różnych możliwych przydziałów. Oczywiście, bez względu na to, jak rzadko musimy to robić, nie możemy sprawdzić każdego możliwego zadania. A wysoce wydajny algorytm nam tutaj nie pomoże. Problem przypisania jest przykładem problemu niepełnego czasu nie wielomianowego (NP-zupełnego); żaden algorytm nie może go poprawnie rozwiązać w rozsądnym czasie. Zamiast tego upraszczamy problem, stosując metodę heurystyczną. Nie gwarantujemy uzyskania najlepszych wyników zleceniae, ale zwykle bardzo szybko otrzymujemy przyzwoite zadanie. Heurystyka zakłada, że postać znajdzie się w miejscu, które najlepiej do niej pasuje, dlatego możemy spojrzeć na każdą postać po kolei i przypisać ją do slotu o najniższym koszcie. Ryzykujemy, że zostawimy postać na koniec i nie mamy nigdzie sensownego jej umieszczenia. Możemy poprawić wydajność, biorąc pod uwagę bardzo ograniczone postacie jako pierwsze, a elastyczne jako ostatnie. Postacie mają łatwość przypisania wartości, która odzwierciedla, jak trudno jest znaleźć dla nich miejsca. Łatwość przypisania wartości wynika z:



gdzie c_i to koszt zajmowania slotu i, n to liczba możliwych slotów, a k to limit kosztu slotu, powyżej którego slot jest uważany za zbyt kosztowny, aby można go było uznać za zajęty. Postacie, które mogą zajmować tylko kilka miejsc, będą miały dużo wysokich kosztów, a zatem niską łatwość. Zwróć uwagę, że nie sumujemy kosztów dla każdej roli, ale dla każdego faktycznego miejsca. Nasz krasnolud może być w stanie zajmować tylko sloty do walki w zwarciu, ale jeśli jest ich dwa razy więcej niż inne typy, nadal będzie stosunkowo elastyczny. Podobnie, mag, który może pełnić zarówno rolę magiczną, jak i pociskową, będzie nieelastyczny, jeśli będzie tylko jeden z nich w formacji dziesięciu slotów. Lista znaków jest sortowana według łatwości przypisywania wartości, a najbardziej niewygodne znaki są przypisywane jako pierwsze. To podejście działa w zdecydowanej większości przypadków i jest standardowym podejściem do przydziału formacji.

Ogólne koszty slotów

Koszty slotu niekoniecznie muszą zależeć tylko od postaci i ról w automacie. Można je uogólnić tak, aby obejmowały wszelkie trudności, jakie postać może mieć w zajmowaniu miejsca. Na przykład, jeśli formacja jest rozłożona, postać może wybrać miejsce, które jest blisko, na bardziej odległym polu. Podobnie lekka piechota może chcieć posunąć się dalej, aby zająć pozycję niż czołg ciężki. Nie jest to poważny problem, gdy formacje będą używane do ruchu, ale może mieć znaczenie w formacjach obronnych. To jest powód, dla którego użyliśmy kosztu automatu zamiast wyniku (tj. Wysoki jest zły, a niski dobry, a nie odwrotnie). Odległość może być bezpośrednio wykorzystana jako koszt slotu. Mogą istnieć inne kompromisy w przyjmowaniu pozycji w formacji. W punktach osłon w całym pomieszczeniu może znajdować się wiele szczelin obronnych. Postacie powinny zajmować pozycje w kolejności zapewnianej przez osłonę. Częściowe pokrycie powinno być zajęte tylko wtedy, gdy nie ma lepszego miejsca. Niezależnie od źródła wahań w kosztach slotów, algorytm przypisania będzie nadal działał normalnie. W naszej implementacji uogólnimy mechanizm kosztu slotu na wywołanie metody; Biblioteka pytamy postać, jak kosztowne będzie zajęcie określonego miejsca. Kod źródłowy na stronie zawiera implementację tego interfejsu, który obsługuje podstawowy mechanizm ról slotów.

Realizacja

Możemy teraz zaimplementować algorytm przypisania przy użyciu uogólnionych kosztów szczelin. Metoda obliczania przypisania jest częścią klasy menedżera formacji, tak jak poprzednio.
1 class FormationManager
2
3 # … other content as before …
4
5 def updateSlotAssignments():
6
7 # Holds a slot and its corresponding cost.
8 struct CostAndSlot:
9 cost
10 slot
11
12 # Holds a character's ease of assignment and its
13 # list of slots.
14 struct CharacterAndSlots:
15 character
16 assignmentEase
17 costAndSlots
18
19 # Holds a list of character and slot data for
20 # each character.
21 characterData
22
23 # Compile the character data
24 for assignment in slotAssignments:
25
26 # Create a new character datum, and fill it
27 datum = new CharacterAndSlots()
28 datum.character = assignment.character
29
30 # Add each valid slot to it
31 for slot in 0..pattern.numberOfSlots:
32
33 # Get the cost of the slot
34 cost = pattern.getSlotCost(assignment.character)
35
36 # Make sure the slot is valid
37 if cost >= LIMIT: continue
38
39 # Store the slot information
40 slotDatum = new CostAndSlot()
41 slotDatum.slot = slot
42 slotDatum.cost = cost
43 datum.costAndSlots.append(slotDatum)
44
45 # Add it to the character's ease of assignment
46 datum.assignmentEase += 1 / (1+cost)
47
48 # Keep track of which slots we have filled
49 # Filled slots is an array of booleans of size:
50 # numberOfSlots. Initially all should be false
51 filledSlots = new Boolean[pattern.numberOfSlots]
52
53 # Clear the set of assignments, in order to keep track
54 # of new assignments
55 assignments = []
56
57 # Arrange characters in order of ease of assignment, with
58 # the least easy first.
3.7 Coordinated Movement 165
59 characterData.sortByAssignmentEase()
60 for characterDatum in characterData:
61
62 # Choose the first slot in the list that is still
63 # open
64 characterDatum.costAndSlots.sortByCost()
65 for slot in characterDatum.costAndSlots:
66
67 # Check if this slot is valid
68 if not filledSlots[slot]:
69
70 # Create an assignment
71 assignment = new SlotAssignment()
72 assignment.character = characterDatum.character
73 assignment.slotNumber = slot
74 assignments.append(assignment)
75
76 # Reserve the slot
77 filledSlots[slot] = true
78
79 # Go to the next character
80 break continue
81
82 # If we reach here, it is because a character has no
83 # valid assignment. Some sensible action should be
84 # taken, such as reporting to the player.
85 error
86
87 # We have a complete set of slot assignments now,
88 # so store them
89 slotAssignments = assignments

Instrukcja break continue wskazuje, że najbardziej wewnętrzna pętla powinna zostać pozostawiona, a otaczająca pętla powinna zostać ponownie uruchomiona z następnym elementem. W niektórych językach nie jest to łatwe do osiągnięcia. W C / C ++ można to zrobić, oznaczając najbardziej zewnętrzną pętlę i używając nazwanej instrukcji continue (która będzie kontynuować nazwaną pętlę, automatycznie przerywając wszelkie otaczające pętle). Zobacz informacje referencyjne dla swojego języka, aby zobaczyć, jak osiągnąć ten sam efekt.

Struktury danych i interfejsy

W tym kodzie ukryliśmy dużą złożoność struktur danych. Istnieją dwie listy, characterData i costAndSlots, w strukturze CharacterAndSlots, które są sortowane. W pierwszym przypadku dane postaci są sortowane według oceny łatwości przypisania, przy użyciu rozszerzenia sortByAssignmentEase. Można to zaimplementować jako dowolny rodzaj lub alternatywnie metodę można przepisać w celu sortowania na bieżąco, co może być szybsze, jeśli lista danych znaków jest zaimplementowana jako lista połączona, do której można bardzo szybko wstawić dane. Jeśli lista jest zaimplementowana jako tablica (co zwykle jest szybsze), lepiej zostawić sortowanie na ostatnie i użyć szybkiego algorytmu sortowania lokalnego, takiego jak quicksort. W drugim przypadku dane znakowe są sortowane według kosztu slotu przy użyciu metody sortByCost. Ponownie, można to zaimplementować w celu sortowania podczas kompilowania listy, jeśli podstawowa struktura danych obsługuje szybkie wstawianie elementów.

Wydajność

Wydajność algorytmu wynosi O (kn) w pamięci, gdzie k to liczba znaków, a n to liczba slotów. Jest to O (ka log a) w czasie, gdzie a jest średnią liczbą slotów, które może zająć dana postać. Jest to zwykle niższa wartość niż całkowita liczba gniazd, ale rośnie wraz ze wzrostem liczby gniazd. Jeśli tak nie jest, jeśli liczba ważnych gniazd dla znaku nie jest proporcjonalna do liczby gniazd, to wydajność algorytmu również wynosi O (kn) w czasie. W obu przypadkach jest to znacznie szybsze niż proces O (nPk). Często problem z tym algorytmem dotyczy raczej pamięci niż szybkości. Istnieją sposoby na uzyskanie tego samego efektu algorytmicznego przy mniejszej ilości pamięci, jeśli to konieczne, ale przy odpowiednim wydłużeniu czasu wykonywania. Niezależnie od implementacji algorytm ten często nie jest wystarczająco szybki, aby mógł być używany regularnie. Ponieważ przypisanie zdarza się rzadko (na przykład gdy użytkownik wybierze nowy wzorzec lub dodaje jednostkę do formacji), można je podzielić na kilka klatek. Gracz raczej nie zauważy opóźnienia o kilka klatek, zanim postacie zaczną składać się w formację.

•  Wprowadzenie
• AI Gry