WSTĘP

Odkąd Zadeh przedstawił podstawy logiki rozmytej w swoim słynnym artykule "Zestawy rozmyte" (Zadeh, 1965), coraz więcej dziedzin badawczych wykorzystuje jego technikę do rozwiązywania i modelowania problemów oraz stosuje ją, głównie w systemach sterowania. Ten rozkwit wynika w dużej mierze z dobrych wyników w klasyfikowaniu niejednoznacznych informacji, typowych dla systemów złożonych. Sukces w tej dziedzinie był tak przytłaczający, że można go znaleźć w wielu osiągnięciach przemysłowych ostatniej dekady: sterowanie pociągiem Sendai , sterowanie systemami klimatyzacji, pralkami, autofokusem w aparatach, robotami przemysłowymi itp. Logika rozmyta została również zastosowana do komputerowej analizy obrazu ze względu na jej szczególne zalety: wysoką niewrażliwość na szum i zdolność do łatwego radzenia sobie z informacjami wielowymiarowymi , cechy, które są obecne w większości analiz obrazów cyfrowych. W logice rozmytej techniki, które były najczęściej stosowane do analizy obrazu, to algorytmy klasteryzacji rozmytej, odkąd Bezdek zaproponował je w latach siedemdziesiątych . Technika ta ewoluowała nieustannie w kierunku korygowania problemów początkowych algorytmów i uzyskiwania lepszej klasyfikacji: technik lepszej inicjalizacji tych algorytmów oraz algorytmów, które umożliwiałyby ocenę rozwiązania za pomocą funkcji ważności. Ulepszono również mechanizm klasyfikacji poprzez modyfikację funkcji przynależności algorytmu, umożliwiając mu prezentowanie zachowań adaptacyjnych; ostatnio do obliczania przynależności zastosowano funkcje jądra . Obecnie zastosowania logiki rozmytej znajdują zastosowanie w niemal wszystkich dziedzinach informatyki, stanowiąc jedną z najbardziej obiecujących gałęzi sztucznej inteligencji, zarówno z teoretycznego, jak i komercyjnego punktu widzenia. Dowodem tej ewolucji jest rozwój inteligentnych systemów opartych na logice rozmytej. W niniejszym artykule przedstawiono kilka algorytmów klasteryzacji rozmytej zastosowanych do analizy obrazów medycznych. Zamieszczono również wyniki badania wykorzystującego obrazy biomedyczne do zilustrowania wspomnianych koncepcji i technik.

TŁO

Logika rozmyta jest rozszerzeniem tradycyjnej logiki binarnej, która pozwala nam osiągnąć logikę wielowartościową poprzez znacznie bardziej szczegółowy opis domen i lepszą klasyfikację poprzez przeszukiwanie większego obszaru. Logika rozmyta umożliwia efektywniejsze modelowanie świata rzeczywistego: na przykład, podczas gdy logika binarna pozwala nam jedynie stwierdzić, że kawa jest gorąca lub zimna, logika rozmyta pozwala nam rozróżnić wszystkie możliwe wahania temperatury: bardzo gorąca, letnia, zimna, bardzo zimna itd. Techniki oparte na logice rozmytej okazały się bardzo przydatne w radzeniu sobie z niejednoznacznością i niejasnością, które zwykle towarzyszą analizie obrazów cyfrowych. Na jakim poziomie szarości ustalamy progowanie? Gdzie lokalizujemy krawędź w rozmytych obiektach? Kiedy poziom szarości jest wysoki, niski lub średni? Rozmyte przetwarzanie obrazów cyfrowych można uznać za zupełnie inny obszar zainteresowania w porównaniu z tradycyjnymi technikami komputerowego przetwarzania obrazu. Nie została ona opracowana w celu rozwiązania konkretnego problemu, lecz opisuje nową klasę technik przetwarzania obrazu i nową metodologię ich opracowywania: rozmyte detektory krawędzi, rozmyte operatory geometryczne, rozmyte operatory morfologiczne itd. Te cechy sprawiają, że logika rozmyta jest szczególnie użyteczna w opracowywaniu algorytmów usprawniających analizę obrazów medycznych, ponieważ zapewnia ramy do reprezentacji wiedzy, z których można korzystać na dowolnym etapie analizy.

ALGORYTMY KLASTEROWANIA ROZMYTEGO ZASTOSOWANE W ANALIZIE OBRAZÓW BIOMEDYCZNYCH

Systemy obrazowania medycznego wykorzystują szereg czujników, które wykrywają cechy tkanek i strukturę narządów, co pozwala nam, w zależności od zastosowanej techniki, uzyskać dużą ilość informacji i obrazów danego obszaru pod różnymi kątami. Te zalety sprawiły, że stały się one jedną z najpopularniejszych technik wspomagających diagnostykę i przyczyniły się do obecnego rozpowszechnienia i różnorodności technik obrazowania medycznego (zdjęcia rentgenowskie, PET…) oraz do rozwoju nowych technik (fMRI). Złożoność segmentacji obrazów biomedycznych wynika wyłącznie z jej cech: dużej ilości danych, które należy przeanalizować, utraty informacji związanej z przejściem z obrazu 3D do reprezentacji 2D, dużej zmienności i złożoności kształtów, które należy analizować… Jednym z najczęściej stosowanych celów segmentacji obrazów medycznych jest wykorzystanie technik rozpoznawania wzorców, ponieważ zazwyczaj celem analizy cyfrowego obrazu medycznego jest wykrycie określonego elementu lub obiektu: guzów, narządów itp. Spośród wszystkich tych technik techniki klastrowania rozmytego okazały się jednymi z najpotężniejszych, ponieważ pozwalają nam wykorzystać kilka cech zbioru danych, z których każda ma własną wymiarowość, i podzielić te dane; ponadto działają automatycznie i zazwyczaj mają niskie wymagania obliczeniowe. Zatem, jeśli problem segmentacji zdefiniujemy jako podział obrazu na obszary o wspólnej cesze, algorytmy klasteryzacji rozmytej przeprowadzają ten podział z wykorzystaniem zbioru przykładowych elementów, zwanych centroidami, i uzyskują macierz o rozmiarze oryginalnego obrazu i o wymiarze równym liczbie klastrów, na które obraz został podzielony; wskazuje to przynależność każdego piksela do każdego klastra i służy jako podstawa do detekcji każdego elementu. W następnej sekcji przedstawiamy serię algorytmów klasteryzacji rozmytej, które można uznać za odzwierciedlenie ewolucji w tej dziedzinie i jej różnych punktów widzenia. Na koniec algorytmy te zostaną wykorzystane w badaniu, które przedstawia zastosowanie i możliwości logiki rozmytej w analizie obrazów biomedycznych.

Rozmyte C-średnie (FCM)

Algorytm FCM został opracowany przez Bezdka i jest pierwszym algorytmem rozmytego klasteryzacji; początkowo wymaga on podania liczby klastrów, na które zostanie podzielony obraz, oraz próbki każdego klastra. Kroki tego algorytmu są następujące:

1. Obliczenie przynależności każdego elementu do każdego klastra:



2. Obliczanie nowych centroidów obrazu:



3. Jeśli błąd utrzymuje się poniżej określonego progu, należy przerwać. W przeciwnym razie należy powrócić do kroku 1. Parametrami zmienianymi w analizie algorytmu były dostarczone próbki oraz wartość m.

Rozmyty algorytm K-najbliższego sąsiada (FKNN)

Rozmyty algorytm K-najbliższego sąsiada jest, jak sama nazwa wskazuje, rozmytą odmianą algorytmu segmentacji twardej. Wymaga on znajomości liczby klas, na które podzielony zostanie zbiór, który ma zostać sklasyfikowany. Element, który ma zostać sklasyfikowany, jest powiązany z klasą najbliższej próbki spośród K najbardziej podobnych. Te K najbardziej podobnych próbek nazywane są "sąsiadami"; jeśli na przykład sąsiedzi są klasyfikowani od najbardziej do mniej podobnych, klasą docelową badanego elementu będzie klasa sąsiada, który jest pierwszy na liście. Używamy wyrażenia z Równania 3 do obliczenia współczynników przynależności piksela do rozpatrywanych klastrów:



gdzie u_ij reprezentuje współczynnik przynależności j-tej próbki do i-tej klasy; x_j reprezentuje jedną z K próbek najbardziej podobnych do przetwarzanego piksela; x reprezentuje sam piksel; m jest współczynnikiem wagowym odległości między pikselem a próbkami, a u_i(x) reprezentuje poziom przynależności piksela x do klasy i. Podczas analizy tego algorytmu parametrami, które się zmieniały, były próbki podane jako początkowe centroidy i rozważana liczba sąsiadów.

Zmodyfikowany algorytm rozmytych średnich C

Ten algorytm opiera się na pracach Younga Wona Lima i Sang Uk Lee , którzy opisali algorytm segmentacji obrazów kolorowych poprzez badanie histogramów każdego pasma kolorów. Algorytm ten opiera się również na algorytmie klasyfikacji rozmytych średnich C. Algorytm MFCM składa się z dwóch części:

1. Części trudnej, która bada histogramy obrazu w celu uzyskania liczby klas i przeprowadza pierwszą globalną klasyfikację obrazu; oraz

2. Części rozmytej, która klasyfikuje piksele, które mają większe trudności z określeniem klasy, do której należą. Piksele tego obszaru nazywane są "strefą rozmytą".

Po uzyskaniu początkowych klastrów wraz z ich centroidami, algorytm wykorzystuje funkcję przynależności FCM (równanie 2) do klasyfikacji pikseli. Punkty rozmyte to piksele znajdujące się pomiędzy początkowymi klastrami oraz piksele klastrów zbyt małych, aby algorytm mógł je uwzględnić. Ponieważ nie dysponujemy oznaczonymi obiektami prostymi każdej klasy, do obliczenia współczynników przynależności piksela wykorzystujemy centra grawitacji klastrów. Podczas analizy tego algorytmu zmienialiśmy wartość sigma używanej do wygładzenia histogramu, obszar, którego początkowe klastry potrzebują do przetrwania, oraz obszary bezpieczeństwa wokół klastrów.

Kernelized Fuzzy C-Means (KFCM)

Algorytm ten został zaproponowany przez Wu Zhong-Donga i opiera się na metodzie FCM, zintegrowanej z funkcją jądra, która umożliwia przeniesienie danych do przestrzeni o większej wymiarowości, co ułatwia separację klastrów. Najczęściej używanymi funkcjami jądra są funkcje wielomianowe (równanie 4) i radialne funkcje bazowe (równanie 5).



Algorytm składa się z następujących kroków:

1. Obliczenie funkcji przynależności:



gdzie



2. Obliczenie nowej macierzy jądra i



gdzie



3. Zaktualizuj członkostwa u_jk do û_jk za pomocą równania 6.

4. Jeśli błąd utrzymuje się poniżej określonego progu, przerwij. W przeciwnym razie wróć do kroku 1. Różnymi parametrami do analizy tego algorytmu były próbki początkowe.

Obrazy wykorzystane w badaniu

Do wyboru obrazów wykorzystanych w badaniu zastosowaliśmy tradycyjne techniki przetwarzania obrazu, a histogram był podstawowym narzędziem.



Zaobserwowaliśmy, że obrazy charakteryzowały się wysokim poziomem zmienności, ponieważ nie było możliwe ujednolicenie różnych elementów, które mają na nie decydujący wpływ: pozycji pacjenta, jasności itp. Wybraliśmy zdjęcia na podstawie charakterystycznej cechy (złe oświetlenie, obecność nietypowych obiektów itp.) lub ich "normalności" (prawidłowe oświetlenie, dobry kontrast itp.). Obrazy zostały zdigitalizowane do rozmiaru 500x500 pikseli i 24 bitów koloru na piksel, przy użyciu przeciętnego skanera. Histogramy na rysunku pokazują niektóre cechy obecne w większości fotografii. Paski o większej liczbie pikseli to pasma kolorów czerwonego i zielonego, ze względu na kolor skóry i fakt, że kolor zielony jest zwykle używany w chusteczkach higienicznych. Histogram jest ciągły i przedstawia wartości na większości poziomów, co pozwala przypuszczać, że wartość większości punktów jest określana przez kombinację trzech pasm, a nie tylko jednego, jak można było się spodziewać. To komplikuje analizę obrazu za pomocą algorytmów.algorytmu były próbki początkowe.

Wyniki

Obrazy testowe podzielono na 3 klastry: tło, tkankę zdrową i tkankę oparzoną. Obszary te są wyraźnie rozróżniane przez specjalistę, co pozwala nam na tworzenie lepszych masek do oceny skuteczności detekcji pikseli w przypadku oparzeń. Skuteczność algorytmów klastrowania rozmytego została po raz pierwszy zmierzona za pomocą metody RUMA (Relative Ultimate Measurement Accuracy) Zhanga (Zhang, 1996). Celem metody RUMA jest ocena jakości segmentacji pod względem podobieństwa pomiarów przeprowadzonych na obrazie segmentowanym i na obrazie rzeczywistym (równanie 8).



W naszym badaniu zmierzyliśmy wskaźnik sukcesu, porównując liczbę pikseli wypalonego obszaru na obrazie wynikowym, które pokrywały się z pikselami wypalonego obszaru na masce. Zdecydowaliśmy się również na zastosowanie drugiego pomiaru wskaźnika sukcesu, ponieważ chociaż RUMA dostarcza wartość dla obszaru zainteresowania, może nie wykryć pewnych błędów klasyfikacji, które mogą wpłynąć na wynikowy obraz. Używamy miary opracowanej przez nasz zespół badawczy, która mierzy wydajność algorytmu klasteryzacji w klasyfikowaniu wszystkich pikseli obrazu (równanie 9). Podczas opracowywania miary zakładaliśmy, że błąd będzie mniejszy, jeśli błąd klasyfikacji każdego klastra będzie mniejszy, więc zmierzyliśmy błąd klasyfikacji pikseli każdego klastra i porównaliśmy go z liczbą pikseli w tym klastrze.



F_ij to liczba klastrów należących do klastra j i przypisanych do klastra i, MASC,sub>j to całkowita liczba pikseli należących do klasy j, a n to liczba klastrów, na które podzielono obraz. Wartość tego pomiaru mieści się w przedziale od 0 do n; w celu uproszczenia interpretacji została znormalizowana w przedziale od 0 do 1. Grafikę uproszczono poprzez odwrócenie wartości rozbieżności: im wyższa wartość, tym lepszy wynik.



Rysunek (a) przedstawia najlepsze wyniki algorytmu FKNN, zmieniającego liczbę próbek i sąsiadów od 1 próbki na klaster do 8 próbek, dla obu pomiarów. Rysunek (b) przedstawia wyniki algorytmu MFCM, zmieniającego próg wymagany dla każdego obszaru histogramu i sigmy, dla obu pomiarów. Algorytmy FCM i FKCM nie są szczegółowe, ponieważ zmienianymi parametrami były wartość dostarczonych próbek i próg zatrzymania, z dość stabilnym wynikiem dla obu pomiarów. Na rysunku 3 możemy zobaczyć jeden z wyników uzyskanych dla algorytmu FCM i obrazu oznaczonego jako Q1.





Rysunek (a) przedstawia wyniki dla różnych obrazów zestawu testowego dla RUMA zastosowanego do wszystkich algorytmów, a rysunek (b) przedstawia wyniki z wykorzystaniem pomiaru globalnego. Testy ujawniają duże zróżnicowanie wartości dostarczanych dla różnych algorytmów przez każdy pomiar; wynika to z braku jednorodnych warunków w akwizycji obrazów i wynikających z tego różnic w jakości fotografii. Możemy również zauważyć, że wyniki uzyskane za pomocą FKCM są znacznie lepsze niż wyniki z FCM, ponieważ ten pierwszy używa lepszej funkcji do obliczenia przynależności pikseli. Niemniej jednak, dla większości obrazów dobre wyniki z FKCM są prześcignięte przez algorytmy FKNN i MFCM. W przypadku FKNN wynika to z jego możliwości użycia kilku próbek dla każdego klastra, co pozwala na dokładniejsze obliczenie przynależności i mniejsze prawdopodobieństwo błędu. Z drugiej strony, algorytm MFCM przeprowadza wcześniejszą analizę histogramu, co w większości przypadków pozwala na znalezienie prawidłowych centroidów i dokonanie trafnych klasyfikacji. Chociaż algorytm FKNN uzyskuje lepsze wyniki, w większości przypadków wymaga on dużej liczby próbek (ponad 4), co może utrudniać pracę eksperta medycznego i komplikować implantację w rzeczywistych warunkach klinicznych. Problem ten nie dotyczy algorytmu MFCM, który sam oblicza próbki; jednak jego skuteczność jest bardzo zróżnicowana i w przypadku wielu obrazów musieliśmy precyzyjnie dostroić parametry, aby uzyskać dobre wyniki.

PRZYSZŁE TRENDY

Dziedzina logiki rozmytej to dziedzina, która stale się rozwija i jest coraz częściej stosowana w produktach przemysłowych. Dziedzina analizy obrazów medycznych należy do najaktywniejszych w dziedzinie wizji komputerowej i stanowi istotne wyzwanie dla badaczy poszukujących nowych rozwojów technologicznych. Algorytmy klastrowania rozmytego stanowią jedną z najbardziej użytecznych i interesujących gałęzi logiki rozmytej. Oczekuje się, że ich zastosowanie będzie rosło, a nowe algorytmy będą się pojawiać, zapewniając coraz lepsze wyniki. Algorytmy te będą coraz częściej stosowane w dziedzinie obrazowania medycznego, gdzie pozwalają nam obsługiwać nowe, wielowymiarowe modalności i udoskonalenia.

WNIOSKI

W niniejszym artykule przedstawiono wyniki uzyskane za pomocą różnych algorytmów klastrowania rozmytego w analizie zbioru zdjęć ran oparzeniowych. Badane techniki zapewniają wysoki poziom detekcji w obszarze oparzenia, co dowodzi ich przydatności w analizie tego typu obrazów medycznych. Testy ujawniają jednak wysoki stopień zmienności wartości dostarczanych przez każdy algorytm, ze względu na brak jednorodnych warunków podczas akwizycji obrazu i wynikające z tego różnice w jakości obrazów. Niniejsze badanie pokazuje, jak algorytm FKCM zapewnia najlepsze rezultaty przy najmniejszej liczbie parametrów. Jednak gdybyśmy mogli kontrolować kontekst, w jakim wykonywane są zdjęcia, najlepszym algorytmem byłby MFCM, który zapewnia lepsze rezultaty i działa automatycznie. Ponadto, dokonujemy przeglądu aktualnego stanu wiedzy w dziedzinie logiki rozmytej i algorytmów klasteryzacji, aby pokazać charakterystykę tych technik i ich możliwości.

WSTĘP

W ostatnich latach obserwuje się wzrost zainteresowania zastosowaniami logik modalnych do specyfikacji i walidacji systemów złożonych. Dotyczy to w szczególności łączonych logik wiedzy, czasu i działań w rozumowaniu o systemach wieloagentowych . W następnym akapicie wyjaśniamy, czym są logiki wiedzy, czasu i działań z punktu widzenia matematyków i filozofów. Zapewnia nam historyczną perspektywę i naukowy kontekst dla tych logik. Dla matematyków i filozofów logika działań, czasu i wiedzy może być przedstawiona w kilku zdaniach. Logika działań (np. Elementarna Logika Zdaniowo-Dynamiczna) jest polimodalną odmianą podstawowej logiki modalnej K do interpretacji w dowolnych modelach Kripkego. Logika czasu (np. Liniowa Logika Temporalna ) to logika modalna z wieloma modalnościami, które odpowiadają "następnym razem", "zawsze", "czasami" i "aż do", które można interpretować w modelach Kripkego w porządkach częściowych (w szczególności dyskretnych porządkach liniowych dla LTL). Wreszcie logika wiedzy lub logika epistemiczna (np. Propositional Logic of Knowledge ) jest polimodalną odmianą innej podstawowej logiki modalnej S5 (Bull & Segerberg, 2001) przeznaczonej do interpretacji w modelach Kripkego, w których wszystkie relacje binarne są równoważnościami.

TŁO: LOGIKI MODALNE

Wszystkie logiki modalne to języki charakteryzujące się składnią i semantyką. Zdefiniujmy poniżej bardzo prostą logikę modalną w ten sposób. Logika ta nazywa się Elementarną Dynamiczną Logiką Zdań (EPDL). Niech prawda, fałsz będą stałymi boolowskimi, a Prp i Rel rozłącznymi zbiorami zmiennych zdaniowych i relacyjnych. Składnia klasycznej logiki zdań składa się z formuł, które są konstruowane ze zmiennych zdaniowych i spójników boolowskich "¬" (negacja), "&" (koniunkcja), "∨" (dysjunkcja), "->" (implikacja) i "<->" (równoważność) zgodnie ze standardowymi zasadami. EPDL ma dodatkowe konstruktory formuł, modalności, które są powiązane ze zmiennymi relacyjnymi: jeśli r jest zmienną relacyjną, a j jest formułą EPDL, to

o ([r]φ) to formuła, którą odczytuje się jako "prostokąt r-φ" lub "po r zawsze φ";
o (r?φ) to formuła, którą odczytuje się jako "romb r-φ" lub "po r czasami φ".

Semantyka EPDL jest definiowana w modelach, które informatycy nazywają systemami przejść oznaczonymi, a matematycy i filozofowie modelami Kripkego1. Model M to para (D , I), gdzie dziedzina (lub wszechświat) D ≠ Ø jest zbiorem, podczas gdy interpretacja I jest parą odwzorowań (P , R). Elementy dziedziny D nazywane są stanami przez informatyków, a światami przez matematyków i filozofów. Interpretacja odwzorowuje zmienne zdaniowe na zbiory stanów P: Prp -> 2^D, a zmienne relacyjne na relacje binarne w stanach R: Rel -> 2^{D × D}. Piszemy I(p) i I(r) zamiast P(p) i R(r), gdy implicite jest powiedziane, że p i r są odpowiednio zmiennymi zdaniowymi i relacyjnymi. Każdy model M = (D , I) można postrzegać jako graf skierowany z węzłami i krawędziami oznaczonymi odpowiednio zmiennymi zdaniowymi i zmiennymi akcji. Jego węzły są stanami D. Węzeł s ∈ D jest oznaczony zmienną zdaniową p ∈ Prp wtedy i tylko wtedy, gdy s ∈ I(p). Para węzłów (s₁,s₂) ∈ D×D jest krawędzią grafu wtedy i tylko wtedy, gdy (s₁,s₂) ∈ I(r) dla pewnej zmiennej relacyjnej r ∈ Rel; w tym przypadku krawędź (s₁,s₂) jest oznaczona przez tę zmienną relacyjną r. Odwrotnie, graf z węzłami i krawędziami oznaczonymi odpowiednio przez zmienne zdaniowe i relacyjne można traktować jako model. Dla każdego modelu M = (D,I) relacja wynikania (ważności, spełnialności) |=_M między stanami i formułami może być zdefiniowana przez indukcję po strukturze formuły:

o dla każdego stanu s |=_M prawdziwego i nie s|=_M fałszywego;
o dla dowolnego stanu s i zmiennej zdaniowej p, s _M p wtedy i tylko wtedy, gdy s∈ I(p);
o dla dowolnego stanu s i formuły φ, s |=_M (¬φ) wtedy i tylko wtedy, gdy nie zachodzi s|=_Mφ o dla dowolnego stanu s i formuł φ i Ψ s |=_MMφ i s|=_MΨ ; s|=_M (φ ∨ Ψ) wtedy i tylko wtedy, gdy s|=_Mφ lub s|=_MΨ; o dla dowolnego stanu s, zmiennej relacyjnej r i wzoru φ, s|=_M ([r]φ) wtedy i tylko wtedy, gdy (s,s′) ∈ I(r) oraz s′ |=_Mφ dla każdego stanu s′ ; s |=_M (φ) wtedy i tylko wtedy, gdy (s,s′) ∈ I(r) oraz s′|=_Mφ j dla pewnego stanu s′ . Semantyka powyższego rodzaju nazywana jest semantyką możliwych światów. Wyjaśnijmy pragmatykę EPDL na poniższym przykładzie łamigłówki. Alicja i Bob grają w Grę Liczbową. Pozycje w grze to liczby całkowite z zakresu [1..109]. Pozycją początkową jest liczba losowa. Alicja i Bob wykonują naprzemienne ruchy: Alicja, Bob, Alicja, Bob itd. Dostępne ruchy są takie same dla obu: jeśli bieżąca pozycja to n?[1..99], to (n+1) i (n+10) to możliwe kolejne pozycje. Gracz wygrywa grę, jeśli przeciwnik jako pierwszy wejdzie do [100..109]. Problem: Znajdź wszystkie pozycje początkowe, w których Alicja ma strategię wygrywającą. Model Kripkego dla tej gry jest dość oczywisty:

o Stany odpowiadają pozycjom w grze, tj. liczbom całkowitym z zakresu [1..109].
o Zmienna zdaniowa fail jest interpretowana przez [100..109].v o Zmienna relacyjna "ruch" jest interpretowana przez możliwe ruchy.

Formuła ¬"fail & < move >(¬fail & [move]fail) jest prawidłowa w stanach, w których gra nie jest przegrana, istnieje ruch, po którym gra nie jest przegrana, a następnie wszystkie możliwe ruchy zawsze prowadzą do przegranej. Zatem ta formuła EPDL jest prawidłowa w stanach, w których Alicja ma strategię wygrywającą z Bobem w jednej rundzie.

ŁĄCZENIE WIEDZY, DZIAŁAŃ I CZASU

Logika wiedzy

Logiki wiedzy są również znane jako logiki epistemiczne. Jedną z najprostszych logik epistemicznych jest zdaniowa logika wiedzy dla n>0 agentów (PLK_n). W tym kontekście stosuje się specjalnąterminologię, notację i modele Kripkego. Zbiór symboli relacyjnych Rel w PLK_n składa się z liczb naturalnych [1..n] reprezentujących nazwy agentów. Notacja dla modalności jest następująca: jeśli i∈ [1..n] a φ jest formułą, to zamiast ([i]φ) i (iφ) używa się (Kiφj) i (Siφ). Formuły te odczytuje się jako "(agent) i zna φ" i "(agent) i może przypuszczać φ". Dla każdego agenta i ∈ [1..n] w każdym modelu M = (D, I), interpretacja I(i) jest "relacją nierozróżnialności", tj. relacją równoważności między stanami, których agent i nie może rozróżnić. Każdy model M, w którym wszyscy agenci są interpretowani w ten sposób, oznaczamy jako (D, ∿₁, … ∿_n, I) z wyraźnym I(1) = ∿₁, … I(n) = ~_n zamiast krótkiej standardowej notacji (D,I). Agent zna pewien "fakt" φ w stanie s modelu M, jeśli fakt ten jest ważny w każdym stanie s′ tego modelu, że agent nie może odróżnić od s: o s =_M (K_i φ) wtedy i tylko wtedy, gdy s′|=?_M φ dla każdego stanu s′ ∿_i s. Podobnie agent może założyć "fakt" φ|=_M w stanie s modelu M, jeśli fakt ten jest ważny w pewnym stanie s′ tego modelu, którego agent nie potrafi odróżnić od s: o s|=_M (S_iφ) wtedy i tylko wtedy, gdy s′|=_Mφ dla pewnego stanu s′∿_i s.Powyższa semantyka możliwych światów wiedzy jest wynikiem pionierskich badań .

Logika temporalna z akcjami

Inną polimodalną logiką zdaniową jest Logika Drzew Obliczeniowych z akcjami (Act-CTL). Act-CTL jest wariantem podstawowej logiki temporalnej z rozgałęzionym czasem zdaniowym - Logiki Drzew Obliczeniowych (CTL). W Act-CTL zbiór symboli relacyjnych składa się z symboli akcji Act. Każdy symbol akcji można zinterpretować jako "akcję natychmiastową", która jest wykonywana w jednym niepodzielnym momencie czasu. Notacja Act-CTL dla podstawowych modalności jest następująca: jeśli b∈ Act a φ jest formułą, to zamiast ([b]φ) i (< b >φ) stosuje się (A_bXφ) i (E_bXφ). Jednak składnia Act-CTL zawiera również inne specjalne konstrukcje związane z symbolami akcji: jeśli b∈ Act oraz φ i ψ są formułami, to (A_bGφ), (A_bFφ), (E_bGφ), (E_bFφj), A_b(φ Uψ) i E_b(φ U ψ) są również formułami Act-CTL. W formułach Act-CTL prefiks "A" czyta się jako "dla każdej przyszłości", "E" - "dla pewnej przyszłości", sufiks "X" - "następny stan", "G" - "zawsze" lub "globalnie", "F" - "czasami" lub "przyszłość", infiks "U" - "aż do", a podindeks "b" czyta się jako "w b-run(ach)". Wyjaśniliśmy już semantykę (A_bXφ) i (E_bXφ) odwołując się do ([b] φ) i (?b?φ). Konstrukcje "A_bG ", "A_bF ", "E_bG " i "E_bF " można wyrazić za pomocą "A_b(…U …)" i "E_b(…U…)", na przykład: (E_bFφ) <-> E_b(true U φ). Zdefiniujmy zatem poniżej semantykę tylko "A_b(…U…)i "E_b(…U…))". Niech M = (D, I) będzie modelem. Jeśli b∈ Act jest symbolem akcji, to częściowy b-przebieg jest sekwencją stanów s₀,… s_k,s_(k+1), … ∈ D (być może nieskończoną) taką, że (s_k,s_(k+1)) ∈ I(b) dla każdej kolejnej pary stanów w tej sekwencji. Jeśli b ∈ Act jest symbolem akcji, to b-przebieg jest nieskończonym częściowym b-przebiegiem lub skończonym b-przebiegiem, który nie może być kontynuowany. Wówczas semantykę konstrukcji "A_b(…U…)" i "E_b(…U…)" można zdefiniować następująco:

o s |=_M A_b(φ U ψ) wtedy i tylko wtedy, gdy dla każdego b-przebiegu s₀,… ,s_k, …, który zaczyna się w s (tj. s₀=s) istnieje pewne n≥ 0, dla którego s_n|=_Mψ i s_k|=_Mφ dla każdego k ∈[0..(n-1)];

o s |=_M E_b(φ U ψ) wtedy i tylko wtedy, gdy dla pewnego b-układu s₀, …,s_k, …, który zaczyna się w s (tj. s₀=s) istnieje pewne n ≥ 0, dla którego s_n|=_Mψ i s_k |=_Mφ dla każdego k∈ [0..(n-1)].

Standardową rozgałęzioną logikę temporalną CTL można traktować jako Act-CTL z jednym niejawnym symbolem akcji.

Połączona logika wiedzy, akcji i czasu

Istnieje wiele połączonych logik polimodalnych do rozumowania o systemach wieloagentowych. Być może najbardziej zaawansowaną jest logika przekonania-pragnienia-intencji (BDI) . Przekonania agenta odpowiadają informacjom, jakie agent posiada o świecie. (Informacje te mogą być niekompletne lub nieprawidłowe. Wiedza agenta w BDI to jedynie prawdziwe przekonanie). Pragnienia agenta odpowiadają przydzielonym zadaniom. Intencje agenta reprezentują pragnienia, które zobowiązał się on osiągnąć. Dopuszczalne działania to działania poszczególnych agentów; mogą być one konstruowane z działań pierwotnych za pomocą kompozycji, wyboru niedeterministycznego, iteracji i równoległego wykonywania. Jednak semantyka BDI i rozumowanie w BDI są dość skomplikowane jak na krótki artykuł encyklopedyczny. Dla porównania, omówmy poniżej prosty przykład połączonej logiki wiedzy, działań i czasu - mianowicie Logikę Zdaniową Wiedzy i Czasu Rozgałęzienia dla n > 0 agentów Act-CTL-K_n . Najpierw podajemy formalną definicję Act-CTL-K_n, następnie omawiamy pewne zagadnienia pragmatyczne, a następnie - w następnej sekcji - wprowadzamy sprawdzanie modeli jako mechanizm wnioskowania. Niech [1..n] będzie zbiorem agentów (n > 0), a Act będzie skończonym alfabetem symboli akcji. Składnia Act-CTL-K_n dopuszcza modalności epistemiczne K_i i S_i dla każdego i ∈?[1..n] oraz konstrukcje rozgałęzień A_bX, E_bX, A_bG, E_bG, A_bF, E_bF, A_b(…U…) i E_b(…U…) dla każdego b ∈ Act. Semantyka jest definiowana w kategoriach implikacji w środowiskach. (Epistemiczne) środowisko to krotka E = (D, ∿₁, … ∿_n , I) taka, że (D, ∿₁, … ∿_n) jest modelem dla PLK_n, a (D, I) jest modelem dla Act-CTL. Relacja wynikania |= jest definiowana przez indukcję zgodnie ze standardową definicją spójników zdaniowych oraz powyższymi definicjami modalności epistemicznych i konstrukcji czasu rozgałęzienia. Jesteśmy zainteresowani głównie środowiskami synchronicznymi z idealnym przywołaniem opartymi na śladach, generowanymi ze skończonych środowisk tła. "Wygenerowane" oznacza, że możliwe "światy" są przebiegami maszyn skończonych. Istnieje kilka możliwości zdefiniowania semantyki logiki łączonej w przebiegach. W szczególności istnieją dwa skrajne przypadki: zapominające systemy asynchroniczne (FAS) i systemy synchroniczne z idealnym przywołaniem (PRS). "Doskonałe przywołanie" oznacza, że każdy agent ma plik dziennika ze wszystkimi swoimi obserwacjami wzdłuż przebiegu, podczas gdy "zapominający" oznacza, że informacje tego rodzaju nie są dostępne. "Synchroniczny" oznacza, że każdy agent może rozróżniać przebiegi o różnej długości, podczas gdy "asynchroniczny" oznacza, że niektóre przebiegi o różnej długości mogą być nierozróżnialne. Jest całkiem naturalne, że w przypadku FAS połączona logika Act-CTL-K_n może wyrazić tyle samo, ile może wyrazić w skończonym systemie tła. Natomiast w przypadku PRS Act-CTL-K_n staje się znacznie bardziej ekspresywny niż w skończonym środowisku tła. Znaczenie połączonych logik w ramach semantyki opartej na śladach z synchronicznym doskonałym odwołaniem polega na ich charakterystyce jako logik uczenia się agenta lub nabywania wiedzy. Chcielibyśmy uzasadnić tę charakterystykę za pomocą następującej łamigłówki FCP(N,M) z pojedynczym agentem Fake Coin Puzzle. Zbiór składa się z (N+1) wyliczonych monet. Ostatnia moneta jest prawidłowa. Pojedyncza moneta z numerem w [1..N] jest fałszywa, ale inne monety z numerami w [1…N+1)] są prawidłowe. Wszystkie prawidłowe monety mają taką samą wagę, która różni się od wagi fałszerstwa. Czy możliwe jest zidentyfikowanie fałszerstwa poprzez równoważenie monet maksymalnie M razy? W FCP(N,M) agent (czyli osoba, która musi rozwiązać zagadkę) nie zna ani numeru fałszywej monety, ani tego, czy jest ona lżejsza, czy cięższa od prawidłowych monet. Niemniej jednak liczba ta należy do [1..N], a fałszywa moneta jest albo lżejsza (l), albo cięższa (h). Agent może wykonywać zapytania równoważące i odczytywać wyniki równoważenia po każdym zapytaniu. Każde zapytanie równoważące jest akcją b(L,R), która polega na równoważeniu dwóch rozłącznych zestawów monet: z liczbami L⊆[1..N+1] na lewej szalce i z liczbami R⊆[1..N+1] na prawej szalce, |L| = |R|. Istnieją trzy możliwe wyniki równoważenia: "<", ">" i "=", co oznacza, że lewa szalka jest odpowiednio lżejsza, cięższa lub równa prawej szalce. Oczywiście istnieją stany początkowe (oznaczone przez ini), które reprezentują sytuację, gdy nie wykonano żadnego zapytania. Podsumujmy. Agent działa w środowisku wygenerowanym ze skończonej przestrzeni [1..N]×{l,h}×{<,>, =, ini}. Jego/jej dopuszczalne działania to równoważenie zapytania b(L,R) dla rozłącznego L, R⊆ [1..N+1] z |L| = |R|. Jedyną dostępną dla agenta informacją (tj. dającą mu/jej możliwość rozróżnienia stanów) jest wynik równoważenia. Agent powinien nauczyć się fake_coin_number z sekwencji, która może zaczynać się od dowolnego stanu początkowego, a następnie składać się z M zapytań i odpowiadających im wyników. Stąd logika pojedynczego agenta Act-CTL-K1 wydaje się być bardzo naturalnym frameworkiem do wyrażania FCP(N,M) w następujący sposób: w celu sprawdzenia lub obalenia, czy



dla każdego stanu początkowego s, gdzie E jest środowiskiem PRS wygenerowanym z przestrzeni skończonej [1..N]×{l,h}×{<, >, =, ini}, a B jest zapytaniem równoważącym ∪_{L,R ⊆[1..N+1]}b_(L,R)

PRZYSZŁE TRENDY: SPRAWDZANIE MODELU DLA LOGIK POŁĄCZONYCH

Problemem sprawdzenia modelu dla logiki połączonej (w szczególności Act-CTL-K_n) i klasy środowisk epistemicznych (np. środowisk PRS lub FAS) jest walidacja lub obalenie s |=_Eφ, gdzie E jest skończenie generowanym środowiskiem w klasie, s jest "stanem początkowym" środowiska E, a φ jest formułą logiki. Powyższa reformułacja FCP(N,M) jest szczególnym przykładem problemu sprawdzenia modelu dla formuły Act-CTL-K_n i pewnego skończenie generowanego środowiska idealnego odwołania. Prace (Meyden i Shilov, 1999) i (Garanina, Kalinina i Shilov, 2004) wykazały, że jeśliliczba agentów n> 1, to problem sprawdzenia modelu w synchronicznych systemach idealnego odwołania jest bardzo trudny, a nawet nierozstrzygalny. W szczególności ma nieelementarne górne i dolne granice czasowe dla Act-CTL-K_n. W pracach (Meyden i Shilov, 1999) oraz (Shilov, Garanina i Choe, 2006) zaproponowano drzewiaste struktury danych, aby umożliwić "wykonalne" sprawdzanie modeli kombinacji logiki temporalnej i działania z logiką zdań wiedzy PLKn. Alternatywnie, zaproponowano uproszczenie języka logiki, która ma być łączona, lub rozważenie agentów z "ograniczonym" wywoływaniem.

WNIOSKI

Połączenie logik temporalnych i logik działań z logikami wiedzy staje się aktualnym tematem badań ze względu na znaczenie badania interakcji między wiedzą a działaniami w wnioskowaniu dotyczącym systemów wieloagentowych w czasie rzeczywistym. Kompleksowy przegląd logik, technik i wyników wykraczał poza zakres artykułu. Głównym celem niniejszego artykułu było wprowadzenie w półformalny temat połączonych logik modalnych i omówienie ich użyteczności w wnioskowaniu dotyczącym systemów wieloagentowych. Nacisk położono na weryfikację modelową specyfikacji wiedzy i czasu opartych na śladach w systemach synchronicznych z idealnym przywołaniem.

WSTĘP

Łączenie ekspertów to klasyczna strategia, szeroko stosowana w różnych zadaniach rozwiązywania problemów. Zespół osób o zróżnicowanych i uzupełniających się umiejętnościach wspólnie podejmuje się zadania, tak aby osiągnąć lepsze wyniki niż pojedyncza osoba poprzez integrację mocnych stron. Począwszy od końca lat 80-tych XX wieku w literaturze poświęconej rozpoznawaniu znaków pisanych ręcznie, prowadzone są badania nad łączeniem wielu klasyfikatorów. Również od początku lat 90. XX wieku w dziedzinie sieci neuronowych i uczenia maszynowego podejmowane są badania pod nazwą uczenia zespołowego lub modelu mieszanego ekspertów nad tym, jak wspólnie uczyć się modelu mieszanego ekspertów (modeli parametrycznych) oraz nad strategią łączenia, która pozwala na ich optymalną integrację. Celem artykułu jest ogólny zarys dwóch nurtów badań, nie tylko z ponownym opracowaniem podstawowych zadań, składników i typowych reguł łączenia, ale także z ogólnymi ramami kombinacji (w szczególności z jednym zwięzłym i bardziej użytecznym przypadkiem szczególnym modulowanym jednoparametrowo, zwanym α-integracją) zaproponowanymi w celu ujednolicenia szeregu typowych reguł kombinacji klasyfikatorów i kilku modeli uczenia opartych na mieszaninie, a także reguły maksymalnej i minimalnej stosowanej w literaturze dotyczącej systemów rozmytych.

KONTEKST

Oba nurty badawcze charakteryzują się dwoma okresami rozwoju. Pierwszy okres przypada mniej więcej na koniec lat 80. i początek lat 90. XX wieku. W literaturze poświęconej rozpoznawaniu pisma odręcznego opracowano różne klasyfikatory, wykorzystujące różne metodologie i cechy, co motywuje do badań nad łączeniem wielu klasyfikatorów w celu uzyskania lepszej wydajności. Systematyczne wysiłki na wczesnym etapie badań podjęto , próbując stworzyć ogólne ramy dla kombinacji klasyfikatorów. Zidentyfikowano nie tylko dwa podstawowe zadania i przedstawiono ramy dla trójpoziomowej kombinacji dla drugiego zadania, aby poradzić sobie z różnymi typami informacji wyjściowych klasyfikatora, ale także zbadano kilka reguł w odniesieniu do dwóch z trzech poziomów, zwłaszcza zaproponowaną regułę głosowania Bayesa, regułę iloczynu i regułę Dempstera-Shafera. Następnie, pozostała część (tj. poziom rangi) została wkrótce zbadana za pomocą liczenia Bordy. Co ciekawe i komplementarne, niemal w tym samym okresie pierwsze zadanie stało się przedmiotem badań w literaturze poświęconej uczeniu się sieci neuronowych. W obliczu problemów związanych z różnymi wyborami dla tego samego typu sieci neuronowej, wynikającymi ze zmiany jej skali (np. liczby ukrytych jednostek w sieci trójwarstwowej), różnymi lokalnymi optymalnymi wynikami dla tej samej sieci neuronowej wynikającymi z różnych inicjalizacji, przeprowadzono badania nad tym, jak trenować zespół zróżnicowanych i uzupełniających się sieci poprzez partycjonowanie walidacji krzyżowej, przycinanie redukcji korelacji, ponowne próbkowanie z kontrolą wydajności itd., tak aby powstała kombinacja dawała lepszą wydajność generalizacji . Oprócz klasyfikacji, ten strumień obsługuje również regresję funkcji poprzez całkowanie poszczególnych estymatorów za pomocą kombinacji liniowej . Co więcej, ten nurt badawczy przechodzi do wspólnego rozważenia wydajności dwóch zadań , korzystając z modeli mieszanych ekspertów (ME) , które mogą uczyć się jednego lub obu mechanizmów łączenia i poszczególnych ekspertów w ujęciu maksymalnego prawdopodobieństwa. Dwa badania nurtowe w pierwszym okresie wspólnie stworzyły krajobraz tego rozwijającego się obszaru badawczego, wraz z szeregiem typowych tematów lub kierunków. Następnie przeprowadzono dalsze badania w każdym z tych typowych kierunków. Najpierw przeprowadzono analizy teoretyczne w celu uzyskania dogłębnych spostrzeżeń i poprawy wydajności. Na przykład, przeprowadzono analizę konwergencji algorytmu EM dla uczenia się opartego na mieszance . W Tumer & Ghosh (1996) rozważane są błędy addytywne prawdopodobieństw a posteriori według klasyfikatorów lub ekspertów, a wariancje i korelacje tych błędów badane są w celu poprawy wydajności kombinacji opartej na sumie. U Kittlera (1998) dalej badany jest wpływ tych błędów na wrażliwość reguły sumy w porównaniu z regułą iloczynu, z wnioskiem, że sumowanie jest znacznie preferowane. Sugerowane są również ramy teoretyczne do traktowania kilku reguł łączących jako przypadków szczególnych (Kittler, 1998), nie zdając sobie sprawy, że te ramy są w rzeczywistości modelem mieszanki ekspertów, który został zaproponowany najpierw do łączenia regresji wielofunkcyjnych , a następnie do łączenia wielu klasyfikatorów . Ponadto przeprowadzono kolejne badanie teoretyczne dotyczące sześciu strategii łączenia klasyfikatorów . Po drugie, istnieją dalsze badania nad regułą Dempstera-Shafera i innymi metodami czesania, takimi jak metoda oparta na rangach, metoda oparta na wzmocnieniach, a także lokalne oszacowania dokładności . Po trzecie, istnieje wiele zastosowań. Ze względu na ograniczoną objętość, szczegółowe informacje znajdują się w publikacjach Ranawany i Palade (2006) oraz Sharkey i Sharkey (1999).

OGÓLNA ARCHITEKTURA, DWA ZADANIA I TRZY SKŁADNIKI

Rozważamy ogólną architekturę przedstawioną na rysunku.



Istnieje {e_j(x)}_kj=1 ekspertów, z których każdy e_j(x) jest klasyfikatorem lub estymatorem. Klasyfikator generuje jeden z trzech typów informacji, dla których mamy trzy poziomy kombinacji. Pierwsze dwa można traktować jako przypadki szczególne trzeciego, który generuje wektor pomiarów. Typowym przykładem jest , gdzie każdy wyraża prawdopodobieństwo a posteriori, że x jest sklasyfikowany do ?l-tej klasy. Ponadto p_j(l| x) = p_j (y=l|x) ? można rozszerzyć do p _j(y|x) , co opisuje rozkład dla regresji x ? y ∈ R^m . Na rysunku przedstawiono również sieć bramkową generującą sygnały {α _j(x)}^k_j=1 modulujące ekspertów za pomocą mechanizmu łączącego M(x). Na podstawie tej architektury można nadal cytować dwa istotne zadania kombinacji eksperckiej z niewielką modyfikacją w Zadaniu 1, że frazę "dla konkretnego zastosowania?" należy usunąć ze względu na wcześniej wprowadzone badania . Wnioski można uzyskać, biorąc pod uwagę trzy podstawowe składniki dwóch strumieni badań, jak pokazano na rysunku

. Kombinatoryczne wybory różnych składników prowadzą do różnych konkretnych modeli kombinacji eksperckiej, a różnice w rolach każdego składnika podkreślają różne skupienia dwóch strumieni. W nurcie sieci neuronowych i uczenia maszynowego, wyposażonym w strukturę dla każdego e_j(x), strukturę bramkowania i strukturę łączącą M(x), wszystkie pozostałe niewiadome są określane zgodnie z teorią uczenia się w celu minimalizacji kosztu błędu. Taka minimalizacja jest realizowana za pomocą procedury optymalizującej przez algorytm uczenia się, oparty na zbiorze treningowym {x_t, y_tt }^N_t=1 , który uczy celu y_t dla każdego odwzorowania x_t ? R^m . Natomiast w nurcie klasyfikatorów łączących, wszystkie {p_j(y|x)^k_j=1 są znane bez niewiadomych do określenia. Ponadto M jest projektowane zgodnie z pewnymi heurystykami lub zasadami, z pomocą lub bez pomocy zbioru treningowego, a badania koncentrują się głównie na opracowaniu i analizie różnych mechanizmów łączących, które omówimy szerzej później. Ostateczna wydajność łączenia jest oceniana empirycznie na podstawie wskaźnika błędnej klasyfikacji, ale nie podjęto jeszcze wysiłków w celu opracowania teorii dla jednego M, która minimalizowałaby wskaźnik błędnej klasyfikacji lub funkcję kosztu, chociaż istnieją pewne badania nad tym, jak można poprawić szacowane prawdopodobieństwa a posteriori za pomocą reguły sumy oraz nad wrażliwością szacowanych prawdopodobieństw a posteriori na błędy. Ten niedostatecznie zbadany kierunek motywuje również do dalszych badań.

f-KOMBINACJA

Średnia arytmetyczna, geometryczna i harmoniczna nieujemnej liczby b_{j t} 0, j = 1 …k,?, została dodatkowo rozszerzona o następującą postać:



gdzie f(r) jest monotoniczną funkcją skalarną, a



Możemy dalej uogólnić tę średnią f do ogólnej architektury pokazanej na rysunku 1, co daje następującą kombinację f:



gdzie



W dalszej części omówimy wykorzystanie go jako ogólnej struktury do ujednolicenia nie tylko typowych reguł łączenia klasyfikatorów, ale także uczenia się w trybie mieszanym z udziałem ekspertów i uczenia sieciowego RBF.



Obserwujemy trzy kolumny dla trzech szczególnych przypadków f(r). Pierwsza kolumna to przypadek f(r) = r, wracamy więc do modelu ME:



który został zaproponowany najpierw do łączenia regresji wielokrotnych , a następnie do łączenia klasyfikatorów . Dla różnych szczególnych przypadków a_j(x) prowadzi nas do szeregu istniejących typowych przykładów. Jak już wskazano, pierwsze trzy wiersze to cztery typowe reguły łączenia klasyfikatorów (drugi wiersz odnosi się bezpośrednio również do reguły min). Kolejne trzy wiersze to trzy typy modeli uczenia się ME. Ostatni wiersz jest nowszym rozwinięciem trzeciego wiersza. Drugi wiersz drugiej kolumny to średnia geometryczna:



która jest równa regule iloczynu , jeśli każda a priori jest równa, tj. a_j(x) = 1/m. Ogólnie rzecz biorąc, jeśli a_j(x) ≠ 1/m, istnieje różnica o współczynnik skalowania ≠aj(x)^1/k-1. Reguła iloczynu działa w sensie teorii prawdopodobieństwa pod warunkiem, że klasyfikatory są wzajemnie niezależne. U Kittlera, próbując omówić szereg reguł w ramach zunifikowanego systemu, reguła sumy jest w przybliżeniu wyprowadzona z reguły iloczynu, pod dodatkowym warunkiem, który jest zwykle trudny do spełnienia. W rzeczywistości takie narzucone powiązanie między regułą iloczynu a regułą sumy jest niepotrzebne, suma:



jest tylko marginalnym prawdopodobieństwem



co jest już w ramach teorii prawdopodobieństwa. Oznacza to, że zarówno reguła sumy, jak i reguła iloczynu współistnieją w ramach teorii prawdopodobieństwa. Z drugiej strony, można zauważyć, że suma:



jest zdominowany przez p_j(y | x)j, jeśli jest bliski 0. Oznacza to, że ta kombinacja zakłada, że każdy ekspert odda wystarczającą liczbę głosów, w przeciwnym razie łączna liczba głosów będzie nadal bardzo niska, tylko dlatego, że tylko jeden ekspert oddał bardzo niski głos. Innymi słowy, tę kombinację można uznać za zrelaksowany logiczny AND, który wykracza poza ramy teorii prawdopodobieństwa, gdy a_j(x) ≠ 1/m. Jednak pozostawanie w ramach teorii prawdopodobieństwa nie oznacza, że jest lepsze, nie tylko dlatego, że wymaga wzajemnej niezależności klasyfikatorów, ale także dlatego, że brakuje analizy teoretycznej obu reguł w sensie błędów klasyfikacji, co wymaga dalszych badań. Można zauważyć, że problem łączenia stopni poparcia zmienia się w problem łączenia stopni niezgody. Jest to interesujące. Niestety, tego rodzaju wysiłki są jak dotąd rzadko spotykane. Wyjątkowo istnieją również przykłady, których nie można uwzględnić w kombinacji f, takie jak reguła Dempstera-Shafera i reguła oparta na rangach. a-CAŁKOWANIE Po ukończeniu powyższej kombinacji f, pierwszy autor zapoznał się z pracą (Hardy, Littlewood i Polya, 1952) dzięki kolejnej publikacji (Amari, 2007), która bada znacznie bardziej zwięzły i użyteczny, jednoparametrowy przypadek modulowany, zwany a-całkowaniem. Z pomocą konkretnych podstaw matematycznych z perspektywy geometrii informacji. Narzucając dodatkowy, ale rozsądny warunek, że średnia f powinna być liniowa i bezskalowa, tj.:



dla dowolnej skali c, alternatywne wybory f(r) sprowadzają się do jednego:



Nie jest trudno to sprawdzić



PRZYSZŁE TRENDY

Oczekuje się dalszych badań w kilku następujących kierunkach:

•  Potrzebne są empiryczne i analityczne porównania wydajności dla tych nieeksplorowanych lub mniej zbadanych elementów
•  Czy istnieje najlepsza struktura dla a_j(x)? Należy przeprowadzić porównania różnych typów aj(x), zwłaszcza tych według typu MUV w ostatnim wierszu i typów ME od 4. do 7. wiersza.
•  Czy konieczne jest złagodzenie ograniczenia:



np. usunięcie wymogu nieujemności i złagodzenie rozkładu p _j(y | x) j dla innych typów funkcji?
o Jak można nauczyć się wag a_j(x) w ramach ograniczenia błędu generalizacji.
o Jak omówiono , uczenie oparte na kombinacji klasyfikatorów i uczenie oparte na mieszaninie to dwa aspekty o różnych cechach. Jak pozwolić każdej części odgrywać najlepszą rolę w zintegrowanym systemie?

WNIOSKI

Aktualizując cel , artykuł przedstawia nie tylko ogólny zarys badań nad łączeniem klasyfikatorów i modeli uczenia się opartych na mieszaninach, ale także ogólne ramy łączenia w celu ujednolicenia szeregu reguł łączenia klasyfikatorów i modeli uczenia się opartych na mieszaninach, a także szereg wskazówek dotyczących dalszych badań.

WSTĘP

Celem niniejszego artykułu jest przedstawienie typologii ścieżek kariery we Francji opracowanej za pomocą algorytmu Kohonena oraz jej rozszerzenia o metodę klastrowania analizy historii życia opartą na wykorzystaniu map samoorganizujących się (SOM). Wcześniej zaprezentowano kilka metod przekształcania informacji jakościowych w ilościowe, co umożliwia zastosowanie algorytmów klastrowania, takich jak SOM oparte na odległości euklidesowej. Nasze podejście polega na kodowaniu ilościowym danych o bliskości sytuacji na rynku pracy w czasie. Dzięki wykorzystaniu SOM, zachowanie topologii pozwala również sprawdzić, czy ta nowa metoda kodowania zachowuje specyfikę historii życia zgodnie z naszym ekonomicznym podejściem do karier. Wreszcie, to ilościowe przetwarzanie wstępne kodowania, które można łatwo zastosować do metod analizy historii życia, uzupełnia zestaw metod rozszerzających zastosowanie SOM na dane jakościowe.

TŁO

Do badania dynamicznych aspektów karier zawodowych stosuje się zazwyczaj kilka metod. Pierwsza metoda, która szacuje niektóre modele transformacji w formie zredukowanej, jest szeroko stosowana w mikroekonometrii pracy, wykorzystując modele historii zdarzeń dla danych w czasie ciągłym lub danych panelowych w czasie dyskretnym z procesami Markowa. Metody drugiego rodzaju, do których należy metoda przedstawiona w niniejszym artykule, to metody analizy sekwencji, które zajmują się złożonymi informacjami na temat historii poszczególnych rynków pracy, takimi jak różne przebyte stany, czas trwania okresów, wielokrotne przejścia między stanami itp. Ideą było empiryczne wygenerowanie statystycznej typologii sekwencji poprzez przeprowadzenie analizy skupień . Metoda ta umożliwia zatem zdefiniowanie "ścieżek klastrów" stanowiących zmienne endogeniczne i wyjaśnianych w kategoriach cech indywidualnych, takich jak płeć, poziom wykształcenia czy status społeczno-ekonomiczny rodziców. Metoda optymalnego dopasowania, która jest szeroko stosowana w naukach społecznych od czasu pionierskiej pracy Abotta, jest atrakcyjnym rozwiązaniem do analizy danych longitudinalnych tego rodzaju. Podstawową ideą leżącą u podstaw tej metody jest wzięcie pary sekwencji i obliczenie kosztu ich przekształcenia w siebie nawzajem poprzez wykonanie serii operacji elementarnych (wstawianie, usuwanie i podstawianie). Jednak ta metoda była mocno krytykowana, ponieważ może być trudno określić wartości tych operacji elementarnych. Tutaj przyjmujemy inną strategię. Po pierwsze, w celu klasyfikowania sekwencji w grupy, zdefiniowaliśmy miarę odległości między każdą trajektorią, która jest spójna z naszymi danymi i z niektórymi dobrze znanymi hipotezami teoretycznymi w dziedzinie ekonomii pracy. Następnie używamy samoorganizujących się map (algorytmu Kohonena) do klasyfikacji i celów. Samoorganizujące się mapy są znane jako potężna metoda klasteryzacji i projekcji. Ponieważ ta metoda skutecznie uwzględnia zmiany zachodzące w czasie, modele SOM dają dokładne prognozy . Historie życia można traktować jako jakościowy zapis informacji, podczas gdy modele SOM oparte są na odległości euklidesowej. Podejmowano wiele prób przekształcenia zmiennych jakościowych w ilościowe: na przykład przy użyciu opisu Burta lub przy użyciu skalowania wielowymiarowego . W naszym podejściu, ilościowe przekodowanie koncentruje się na bliskości między elementami, uwzględniając specyfikę danych (historię życia) zgodnie z naszym podejściem ekonomicznym. Podczas wstępnego przetwarzania ponownego kodowania, Self Organizing Maps okazuje się użytecznym narzędziem do klastrowania, biorąc pod uwagę przede wszystkim jego wcześniej wspomniane właściwości klastrowania i projekcji, a także ze względu na jego zdolność do zwiększania efektywności naszego nowego kodowania.

KLASTEROWANIE HISTORII ŻYCIA Z SOm

Przykład ścieżek kariery opartych na historii życia

Ekonomiści pracy generalnie zakładają, że początek kariery jest wynikiem procesu dopasowania Pracodawcy i osoby poszukujące pracy nie mają o sobie zbyt wielu informacji: pracodawcy muszą wiedzieć, jak produktywny jest ich potencjalny pracownik, a kandydaci chcą wiedzieć, czy charakterystyka stanowiska odpowiada ich oczekiwaniom. Rotacja pracowników i umowy o pracę tymczasową można zatem postrzegać jako konsekwencje tego procesu prób i błędów. Jednak pierwsza sytuacja zawodowa danej osoby może również stanowić sygnał o jej zdolności do zatrudnienia na rynku pracy. Na przykład, długi okres bezrobocia w pierwszych latach kariery zawodowej może być interpretowany przez potencjalnych pracodawców jako oznaka niskiej wydajności pracy; podczas gdy praca w agencji pracy tymczasowej może być postrzegana jako oznaka motywacji i zdolności adaptacyjnych. Jest to zgodne z następującą hipotezą zależności od ścieżki kariery: wpływ wcześniejszego doświadczenia zawodowego na późniejszą karierę zależy od "kosztu" związanego ze zmianą sytuacji zawodowej. Badania empiryczne wykazały jednak, że pracodawcy rekrutują głównie na podstawie niedawnego doświadczenia zawodowego Wpływ mniej aktualnych sytuacji zawodowych na karierę zawodową maleje zatem z czasem.

Dane

Dane wykorzystane w niniejszym badaniu opierają się na badaniu "Pokolenie 98" przeprowadzonym przez Céreq: wiosną 2001 i 2003 roku oraz jesienią 2005 roku przeprowadzono wywiady z 22 000 młodych ludzi, którzy ukończyli szkolenie wstępne w 1998 roku na wszystkich poziomach i we wszystkich specjalizacjach. Próba ta była reprezentatywna dla 750 000 młodych ludzi, którzy po raz pierwszy opuścili system edukacji w tym roku we Francji. Badanie dostarczyło użytecznych informacji na temat cech młodych ludzi (status społeczno-ekonomiczny ich rodzin, wiek, najwyższy ukończony stopień, najwyższy stopień uczęszczania, dyscyplina, wszelkie prace podejmowane w trakcie studiów, staże) oraz miesięcznej historii zatrudnienia w latach 1998-2005. Dzięki temu dysponujemy kompletnym i szczegółowym zapisem statusu na rynku pracy respondentów w okresie 88 miesięcy od lipca 1998 r. do listopada 2005 r. Okresy zatrudnienia zakodowano w następujący sposób, w zależności od rodzaju umowy o pracę: 1 = umowa o pracę na czas nieokreślony, 2 = umowa na czas określony, 3 = umowa o praktykę, 4 = umowa o pracę tymczasową w sektorze publicznym, 5 = praca tymczasowa). Pozostałe sytuacje bezrobocia zakodowano w następujący sposób: 6 = bezrobocie, 7 = bierność zawodowa, 8 = służba wojskowa, 9 = nauka w szkole.

Faza wstępnego przetwarzania: Kodowanie historii życia

Kodowanie trajektorii obejmowało dwuetapową fazę wstępnego przetwarzania: definiowanie odległości między stanami, uwzględniając dynamikę czasową, oraz wynikające z tego ilościowe kodowanie trajektorii. Te dwa etapy odnoszą się do specyfiki struktur zbiorów danych próbek historii życia: zmienne "elementy" (stany) stanowią pewne informacje jakościowe, podczas gdy zmienne "kolejność" rejestrują pewne informacje ilościowe (czas i czas trwania zdarzeń).

Odległość między sytuacjami

Praca z parami (stan, czas), zwanymi sytuacjami, pozwala uwzględnić dynamikę czasową w bliskości między stanami zawodowymi. Bliskość między dwiema sytuacjami jest mierzona na podstawie ich wspólnej przyszłości, zgodnie z naszym podejściem ekonomicznym. Sytuacja jest traktowana jako potencjał dla swojej własnej przyszłości, w zależności od jej wpływu na tę przyszłość. Podobieństwo między dwiema sytuacjami jest wyprowadzane z porównań między ich potencjałami odniesienia. Potencjalna przyszłość P^S sytuacji S pomiędzy n okresami miesięcznymi i p stanami jest definiowana jako wektor wymiarowy p×n podany w (1). Jego składniki P^S′_S są iloczynem członówΦ i β . Φ mierzy przepływ między sytuacją S a dowolną sytuacją S′ jako empiryczne prawdopodobieństwo osiągnięcia S′, zaczynając od S. Jest to również empiryczne prawdopodobieństwo, że jednostka i znajdzie się w dowolnej przyszłej sytuacji S′, pod warunkiem, że będzie w chwili obecnej w S. Współczynnik bezwładności czasowej ? waży wpływ S′ na P^S zgodnie z podejściem ekonomicznym. Jest to malejąca funkcja opóźnienia czasowego (t′-t). W zastosowaniu ścieżek kariery wybrana funkcja jest odwrotnością opóźnienia i wynosi 0 dla przeszłości. Wreszcie, α zapewnia, że potencjalne przyszłe P^S będą profilami. Naturalna odległość między sytuacjami jest zatem odległością &ch;² między ich potencjalnymi przyszłymi profilami.



gdzie



i



Kodowanie trajektorii

W niniejszym przypadku równoważenia bezwładność przestrzeni sytuacji wynika z wcześniej obliczonych odległości. Można zatem wywnioskować główne składowe bezwładności, zwane tutaj zdarzeniami głównymi. Termin "zdarzenie" odnosi się do kombinacji punktu w czasie, czasu trwania i statusu zawodowego. Proponowane tutaj ilościowe kodowanie trajektorii wynika z ich opisu w przestrzeni "zdarzeń". Zastosowany tutaj proces jest zgodny z procesem J.P. Benzécriego , który wyjaśnia, jak:

biorąc pod uwagę zbiór sytuacji {Sⁱ}, jego środek ciężkości G oraz macierz rejestrującą kwadraty odległości (d^jj′) między elementami S^j i S^j′, można wywnioskować macierz iloczynów skalarnych Δ między dowolnymi wektorami GS ze wzoru (2). W odniesieniu do sytuacji, główne składowe bezwładności (główne zdarzenia) oblicza się jako wektory głównych składowych macierzy Δ. Trajektorie można następnie opisać w przestrzeni głównych zdarzeń: wykonanie tradycyjnego kodowania binarnego (3) trajektorii Ti jest równoważne wykonaniu kodowania liniowego poprzez sytuacje (4), a następnierównież poprzez główne zdarzenia E (5).



PRZYSZŁE TRENDY

Znaczenie przedstawionej tutaj metody dotyczy obu aspektów: wstępnego przetwarzania i wyników modeli SOM. Zalety modelu SOM zależą od wybranej odległości, która musi umożliwiać powiązanemu algorytmowi zachowanie bliskości między sytuacjami. Znaczenie etapu wstępnego przetwarzania w tej metodzie zostanie zatem potwierdzone, jeśli zwiększy on niezawodność modeli SOM (Debodt, Cottrell i Verleysen, 2002 oraz Rousset, Guinot i Maillet, 2006 przedstawili odpowiednio metodę pomiaru i metodę zwiększania niezawodności). Z drugiej strony, niezawodność zależy również od wyboru przyszłej funkcji wagowej, funkcji β we wzorze (1). W konsekwencji, funkcja β może zostać tutaj określona z myślą o wiarygodności wyników modelu SOM. Niestety, ogólnie rzecz biorąc, takie podejście może być w niektórych przypadkach kontrproduktywne. Na przykład w przypadku ścieżek kariery prowadziłoby to do ważenia długoterminowej przyszłości, co zwiększyłoby odporność, ale nie byłoby odpowiednie z punktu widzenia badań ekonomicznych. Problem ten pojawia się w wielu ogólnych kontekstach, w których główny wpływ teraźniejszości na przyszłość ma charakter krótkoterminowy, podczas gdy niezawodność wzrasta w perspektywie długoterminowej. Główne kryterium wyboru funkcji β musi zatem być przedmiotem zainteresowania. Obecnie konieczne są dalsze badania w celu poprawy niezawodności tej metody: po pierwsze, funkcja β musi zostać dokładniej zdefiniowana, a po drugie, ważność metody musi zostać przetestowana po zwiększeniu niezawodności topologii SOM uzyskanej po wykonaniu etapu wstępnego przetwarzania opisanego powyżej. Warto również zbadać zastosowanie modeli Markowa w szczególności do zdefiniowania funkcji ?, a także do badania ścieżek kariery w ogóle. Metodę tę będzie trzeba w przyszłości zastosować również do innych prób.

WNIOSKI

Celem niniejszego badania była analiza wczesnej kariery absolwentów francuskich szkół z wykorzystaniem map samoorganizujących się. Ta analiza empiryczna wykazała, że ścieżki kariery są silnie segmentowane. Chociaż większość badanych "ścieżek kariery" charakteryzowała się stabilizacją narynku pracy w pewnym momencie, niektóre z nich wskazują na duże trudności napotykane przez osoby wchodzące na rynek pracy. Uzyskanie stałej umowy nie gwarantuje w rzeczywistości zatrudnienia przez całe życie. Ponadto analiza ekonometryczna przeprowadzona w drugiej części niniejszego badania pokazuje, że różnorodność ścieżek kariery można częściowo wyjaśnić poziomem wykształcenia i indywidualnymi cechami absolwentów szkół. W niniejszej metodzie analizy informacji o trajektoriach jednostek w czasie poprzez skończoną liczbę stanów, połączono dwa ważne aspekty: kodowanie danych i analizę danych przedstawionych w formie modeli SOM. Pierwszy aspekt pozwala uniknąć dobrze znanego problemu skosu, występującego w kodowaniu jakościowym, również gdy jest ono powiązane z ewolucją w czasie. Mapy samoorganizujące się są naturalnym podejściem do analizy danych, ponieważ narzędzie to łączy zalety metod klastrowania i reprezentacji. Opisana tutaj metoda okazuje się skutecznym sposobem badania zmian w czasie i bliskości między sytuacjami. Ponadto stwierdzono, że zachowanie topologii jest użyteczną właściwością, która umożliwia ocenę efektywności przekodowania. Podsumowując, przedstawiona tutaj metoda może być z łatwością wykorzystana do analizy dowolnej historii życia.