WSTĘP

Dane wielowymiarowe stają się coraz powszechniejsze w analizie danych. Dotyczy to zwłaszcza dziedzin związanych z danymi spektrometrycznymi, takich jak chemometria. Dzięki rozwojowi dokładniejszych spektrometrów możliwe jest uzyskanie widm obejmujących tysiące punktów danych. Dane wielowymiarowe są problematyczne w uczeniu maszynowym ze względu na zwiększony czas obliczeniowy i problem z wymiarowością . Dlatego wskazane jest zmniejszenie wymiarowości danych. W przypadku chemometrii widma są zazwyczaj dość gładkie i mało zaszumione, dlatego dopasowanie funkcji jest wygodnym narzędziem redukcji wymiarowości. Dopasowanie uzyskuje się poprzez ustalenie zbioru funkcji bazowych i obliczenie wag dopasowania zgodnie z kryterium najmniejszych kwadratów błędu. W niniejszym artykule opisano nienadzorowaną metodę znajdowania dobrej bazy funkcji, która jest specjalnie zaprojektowana do danego zbioru danych. Podstawę stanowi zestaw funkcji Gaussa zoptymalizowanych pod kątem dokładnego dopasowania. Uzyskane wagi są dodatkowo skalowane za pomocą testu delty (DT) w celu poprawy wydajności predykcji. Do estymacji wykorzystano model maszyny wektorów nośnych najmniejszych kwadratów (LS-SVM).

TŁO

Podejście, w którym dane wielowymiarowe traktowane są jako funkcje, a nie tradycyjne wektory dyskretne, nazywa się Funkcjonalną Analizą Danych (FDA) .Kluczowym elementem FDA jest wybór funkcji bazowych, które umożliwiają reprezentację funkcyjną. Powszechnie stosowanymi bazami są krzywe B-sklejane ,szeregi Fouriera lub falki . Jednakże atrakcyjne jest zbudowanie bazy specyficznej dla danego problemu, która wykorzystuje właściwości statystyczne dostępnych danych. W literaturze istnieją przykłady znajdowania optymalnego zestawu funkcji bazowych, które minimalizują błąd dopasowania, takie jak Funkcjonalna Analiza Głównych Składowych . Funkcje bazowe uzyskane metodą Funkcjonalnej Analizy Głównych Składowych (PCA) zazwyczaj mają wsparcie globalne (tj. są niezerowe w całym przedziale danych). Dlatego funkcje te nie nadają się do kodowania informacji przestrzennych danych. Informacje przestrzenne mogą jednak odgrywać istotną rolę w wielu dziedzinach, takich jak spektroskopia. Na przykład, często zmierzone widma zawierają piki przy określonych długościach fal, które odpowiadają określonym substancjom w próbce. Dlatego obszary te są z pewnością istotne dla oszacowania ilości tych substancji. Proponujemy, aby do kodowania tego rodzaju informacji przestrzennych można było użyć funkcji obsługiwanych lokalnie, takich jak funkcje Gaussa. Ponadto, selekcja zmiennych może służyć do wyboru odpowiednich funkcji spośród funkcji nieistotnych. Wybór istotnych zmiennych bezpośrednio na podstawie danych surowych jest często trudny ze względu na ich dużą wymiarowość; koszt obliczeniowy metod selekcji zmiennych, takich jak selekcja w przód i w tył , rośnie wykładniczo wraz z liczbą zmiennych. Dlatego też, mądrze rozmieszczone funkcje Gaussa są proponowane jako narzędzie do kodowania informacji przestrzennej przy jednoczesnym zmniejszeniu wymiarowości danych, tak aby możliwe stało się wykorzystanie innych, bardziej wydajnych narzędzi przetwarzania informacji. Sugeruje się skalowanie zmiennych oparte na teście delty (DT) w celu poprawy wydajności predykcji. Typowy problem w chemometrii dotyczy przewidywania pewnej ilości chemicznej bezpośrednio na podstawie mierzonego widma. Ze względu na addytywność widm absorpcyjnych, zakłada się, że problem jest liniowy, a zatem modele liniowe, takie jak metody cząstkowych najmniejszych kwadratów , są szeroko stosowane w zadaniu predykcyjnym. Wykazano jednak, że założenie o addytywności nie zawsze jest prawdziwe, a warunki środowiskowe mogą dodatkowo wprowadzać większą nieliniowość do danych . Dlatego też proponujemy, aby w celu rozwiązania ogólnego problemu predykcji zastosować metodę nieliniową. LS-SVM to stosunkowo szybki i niezawodny model nieliniowy, który zastosowano również w chemometrii .

WYKORZYSTANIE BAZY GAUSSA Z DANYMI SPEKTOMETRYCZNYMI

Rozważmy problem, w którym celem jest oszacowanie pewnej wielkości p ∈ ℛ ze zmierzonego widma absorpcyjnego X na podstawie zbioru N przykładów treningowych (X_j ,p_j)^N<_j=1 . W praktyce dane spektrometryczne X_j to zbiór dyskretyzowanych pomiarów (x^j_i y^j_i)^m_i=1, gdzie x^j_i ∈ [ a,b] ⊂ ℛ , oznaczają długość fali obserwacji, a y^j_i ∈ ℛ jest odpowiedzią. Przyjmując ramy FDA ,naszym celem jest zbudowanie modelu predykcyjnego F tak, aby . Tutaj argumentem X jest widmo rzeczywiste, tj. funkcja ciągła, która odwzorowuje długości fal na odpowiedzi. Bez dużej utraty ogólności można założyć, że X należy do L₂([a, b]), przestrzeni kwadratów funkcje całkowalne na przedziale [a, b]. Jednak ponieważ widmo X jest nieznane i nieskończenie wymiarowe, w praktyce niemożliwe jest zbudowanie modelu F(X). Dlatego X musi zostać aproksymowane reprezentacją q-wymiarową ω =P(X),P:L₂ -> ℛ^q , a nasz model predykcyjny przyjmuje postać . Oczywiście, aby uzyskać redukcję wymiarowości, wymagamy, aby q było mniejsze niż liczba punktów w widmach. Rysunek 1 przedstawia wykres ogólnej metody predykcji



Do aproksymacji X użyto dopasowania Gaussa. Uzyskane wektory ω są dodatkowo skalowane za pomocą macierzy diagonalnej A przed ostatecznym modelowaniem LS-SVM. Poniższe sekcje wyjaśniają te kroki bardziej szczegółowo.

Dopasowanie Gaussa: Aproksymacja funkcji widmowej X

Ponieważ przestrzeń L₂([a, b]) jest przestrzenią funkcji o nieskończonym wymiarze, konieczne jest rozważenie pewnej skończonej podprzestrzeni V ⊂ L₂([a, b]) w celu uzyskania dopuszczalnego przybliżenia funkcji. Definiujemy V za pomocą zbioru funkcji Gaussa.



gdzie t_k to środek, a σ_k to parametr szerokości. Zbiór φ_k(x) rozpina q-wymiarową unormowaną przestrzeń wektorową i możemy zapisać V = span{φ_k(x)}. Naturalnym wyborem normy jest norma L₂:



Teraz X można przybliżyć, korzystając z reprezentacji bazowej , gdzie



Wagi ω dobiera się tak, aby zminimalizować błąd kwadratowy:



Innymi słowy, po prostu dopasowujemy funkcję do punktów (x_i y_i)^m_i=1 używając funkcji bazowych φ_k(x). Teraz dowolny jest jednoznacznie określony przez wektor wagowy ω. Sugeruje to, że równoważne jest analizowanie dyskretnych wektorów wagowych ? zamiast funkcji ciągłych .

Ortonormalizacja

Modele radialno-symetryczne (takie jak LS-SVM) zależą tylko od metryki odległości d(ˇ,ˇ) w przestrzeni wejściowej. Zatem wymagamy, aby odwzorowanie z V na ℛ^q było izometryczne, tj. dla dowolnych funkcji . Pierwsza odległość jest obliczana w przestrzeni funkcji, a druga w ℛ^q. W przestrzeń V, odległości są zdefiniowane przez normę . Teraz proste obliczenie daje



gdzie



Oznacza to, że jeśli baza jest ortonormalna, macierz Φ staje się macierzą jednostkową i odległości stają się równe, tj.



Niestety, w przypadku bazy Gaussa tak nie jest i konieczne jest zastosowanie transformacji liniowej . W tym przypadku macierz U jest rozkładem Choleskiego Φ=U^TU. W rzeczywistości przekształcone wagi ? są powiązane z zestawem nowych funkcji bazowych , które są zoptymalizowane pod kątem dopasowania do danych i ortonormalne

Znalezienie optymalnej bazy Gaussa

Gdy funkcje bazowe są ustalone, wagi ω można łatwo uzyskać, rozwiązując problem (2). Rozwiązaniem jest pseudoodwrotność ω = (G^TG)^-1G^Ty , gdzie y = [y₁, y₂,…, y_m]^T to wartości do dopasowania, a [G]_i,j = φ_j(x_i). Ponieważ funkcje Gaussa są różniczkowalne, położenia i szerokości można zoptymalizować w celu lepszego dopasowania. Średni błąd dopasowania wszystkich funkcji uzyskuje się poprzez uśrednienie równania (2) dla wszystkich danych wejściowych próbki j = 1, . . .,N. Używając powyższej notacji macierzowej, można ją sformułować jako



które można różniczkować względem t_k i σ_k . Znając pochodne cząstkowe, położenia i szerokości można zoptymalizować za pomocą nieograniczonej optymalizacji nieliniowej. W niniejszym artykule zaproponowano metodę quasi-Newtona Broydena-Fletchera-Goldfarba-Shanno (BFGS) z przeszukiwaniem liniowym. Sformułowanie algorytmu BFGS można znaleźć w pracach Bazaraa, Sherali i Shetty (1993). Przykład danych widmowych i zoptymalizowanych funkcji bazowych przedstawiono na rysunku 2.



To zastosowanie dotyczy przewidywania zawartości tłuszczu w próbkach mięsa za pomocą widm absorpcyjnych w bliskiej podczerwieni . Widać, że baza dostosowała się do danych: w centrum, gdzie dane charakteryzują się większą wariancją, występują wąskie funkcje.

Skalowanie zmiennych

Skalowanie zmiennych można postrzegać jako uogólnienie selekcji zmiennych; w selekcji zmiennych zmienne są albo uwzględniane w zbiorze treningowym (odpowiadając mnożeniu przez 1), albo wykluczane z niego (odpowiadając mnożeniu przez 0), podczas gdy w skalowaniu zmiennych dopuszczalny jest cały zakres [0,1] skalarów. W niniejszym artykule przedstawiamy metodę wyboru skalowania za pomocą testu delta (DT). Skalary są generowane za pomocą iteracyjnego wyboru w przód i w tył (FBS). FBS jest zwykle używany do selekcji zmiennych, ale można go również rozszerzyć na skalowanie; Zamiast obracania skalarów z 0 na 1 lub odwrotnie, dozwolone są wzrosty o 1/h (w przypadku selekcji w przód) lub zmniejszenia o 1/h (w przypadku selekcji w tył). Liczba całkowita h jest stałym parametrem siatki. Zaczynając od początkowego skalowania, algorytm FBS zmienia każdy ze skalarów o ±1/h i akceptuje zmianę, która spowodowała największą poprawę. Proces jest powtarzany, aż do znalezienia braku poprawy. Proces jest inicjowany kilkoma zestawami losowych skalarów. DT to metoda szacowania wariancji szumu w zbiorze danych. Mając zbiór ogólnych par wejście-wyjście (x_i,y_i)^N_i=1 ∈ ℛ,sup>m x ℛ ii oznaczając najbliższego sąsiada x_i jako x_NN(i), estymacja wariancji DT wynosi



gdzie y_NN(i) jest wynikiem x_NN(i). Zatem δ jest równoważne reszcie (tj. błędowi predykcji) modelu pierwszego najbliższego sąsiada. DT jest przydatne w ocenie zależności zmiennych losowych i dlatego może być używane do skalowania: Wybierany jest zbiór skalarów, które dają najmniejsze δ.

LS-SVm

LS-SVM to modyfikacja najmniejszych kwadratów maszyny wektorów nośnych (SVM) . Problem optymalizacji kwadratowej SVM jest uproszczony, co pozwala na jego redukcję do liniowego układu równań. Co więcej, regresyjna SVM zazwyczaj obejmuje trzy nieznane parametry, podczas gdy LS-SVM ma tylko dwa: parametr regularyzacji γ i parametr szerokości θ.Biorąc pod uwagę zbiór N przykładów treningowych (x_i,y_i)^N_i=1 ∈ ℛ,sup>m x ℛ model LS-SVM to , gdzie Ψ : ℛ ^m-> ℛⁿ jest odwzorowaniem z przestrzeni wejściowej na przestrzeń ukrytą o wyższym wymiarze, w ∈ ℛⁿ jest wektorem wagowym, a b jest wyrazem odchylenia. Problem optymalizacji sformułowano jako



gdzie e_i to błąd predykcji, a γ ≥ 0 to parametr regularyzacji. Problem dualny wyprowadzono za pomocą mnożników Lagrange′a, co prowadzi do liniowego układu KKT, który jest łatwy do rozwiązania . Korzystając z rozwiązania dualnego, oryginalny model można sformatować jako



gdzie jądro K(x,x_i =Ψ(x)^TΨ(x_i) ,jest ciągłym i symetrycznym odwzorowaniem z ℛ ^m x> ℛⁿ, a α_isą mnożnikami Lagrange′a. Powszechnie stosowanym wyborem dla K jest standardowe jądro Gaussa .Prognoza LS-SVM jest ostatnim krokiem proponowanej metody, w której dane widmowe są kompresowane przez dopasowanie Gaussa, a wagi dopasowania są normalizowane i skalowane przed prognozą.

PRZYSZŁE TRENDY

Jedynym nieznanym parametrem proponowanej metody jest liczba funkcji bazowych wybieranych w procesie walidacji. W przyszłości należy opracować inne metody określania prawidłowego rozmiaru bazy, aby przyspieszyć ten proces. Ponadto metodologię należy przetestować na różnych zbiorach danych, w tym innych niż dane spektralne. Predyktor LS-SVM można również zastąpić innym modelem. Chociaż proponowane dopasowanie Gaussa w połączeniu z modelem LS-SVM wydaje się dość solidne, należy szczegółowo zbadać związek między funkcjami bazowymi a wydajnością predykcji. Pożądana byłaby bezpośrednia optymalizacja bazy w celu uzyskania najlepszej możliwej wydajności predykcji (zamiast dobrego dopasowania danych), chociaż wydaje się to trudne ze względu na nadmierne dopasowanie i wysokie koszty obliczeniowe.

WNIOSKI

Niniejszy artykuł dotyczy problemu znalezienia dobrego zestawu funkcji bazowych do redukcji wymiarów danych spektralnych. Zaproponowaliśmy metodę opartą na funkcjach bazowych Gaussa, w której położenie i szerokości funkcji są optymalizowane w celu jak najdokładniejszego dopasowania danych. Podstawa rzeczywiście odzwierciedla charakter danych i stanowi dobre narzędzie do redukcji wymiarów. Inne metody, takie jak proponowane skalowanie DT, skorzystają z mniejszego wymiaru danych i pomogą osiągnąć jeszcze lepszą kompresję danych. Model LS-SVM to solidna i szybka metoda do wykorzystania w ostatecznej predykcji.

WSTĘP

Paradygmat agenta zyskał ostatnio na znaczeniu w badaniach i rozwoju systemów opartych na logice obliczeniowej. Jasna i poprawna specyfikacja jest tworzona poprzez programowanie logiczne (LP) i rozumowanie nienomotoniczne, które ponownie znalazły się w centrum uwagi. Również niedawne znaczące ulepszenia w zakresie wydajności implementacji LP dla rozumowania niemonotonicznego przyczyniły się do tego odrodzenia. Agenci muszą jednak stale aktualizować swoją bazę wiedzy, a zwłaszcza baza intencjonalna (reguły), dzięki której nasz agent ma zdolność reagowania na zmiany w dynamicznym środowisku, ma kluczowe znaczenie w kontekście agentów programowych. Taka cecha powinna odpowiadać przemyślanemu, racjonalnemu zachowaniu, jakiego oczekują od naszych agentów. Jakość usług oferowanych przez agenta opiera się na formie, w jakiej agent łączy racjonalność i reaktywność. Agent reaktywny może oferować dobrze ocenione rekomendacje, ale ta odpowiedź opiera się na nieaktualnych informacjach, podczas gdy zachowanie racjonalne może generować rekomendacje w oparciu o najnowsze uzyskane informacje. Dlatego jesteśmy zainteresowani rozwojem agentów świadomych środowiska. Z tego powodu bardzo ważne jest posiadanie procesu aktualizacji agentów, tj. takiego, który pozwala nam projektować agentów z ich racjonalnym komponentem. W ostatnich latach zaproponowano kilka semantyk dla aktualizacji programów logicznych . Wszystkie te semantyki są zbieżne w traktowaniu propozycji AGM jako standardowego modelu w teorii aktualizacji, ze względu na bogactwo jej właściwości. Podejście AGM, jest dominującym paradygmatem w tym obszarze, ale w kontekście logiki monotonicznej. Wszystkie te propozycje analizują i reinterpretują postulaty AGM w ramach programowania zbiorów odpowiedzi (ASP). Jednak większość zaadaptowanych postulatów AGM i aktualizacji jest naruszana przez programy aktualizacji. Z tego powodu pracowaliśmy nad znalezieniem właściwości, które spełnia nasz operator aktualizacji . Naszym celem jest zbudowanie semantyki opartej na właściwościach strukturalnych. Jest to nasz główny cel w teorii aktualizacji. Autorzy przedstawiają zbiór właściwości, które spełnia operator aktualizacji. W tym artykule kontynuujemy ten sam kierunek badań, przedstawiając nowatorską propozycję mającą na celu wzbogacenie posiadanej przez nas teorii aktualizacji . Ta nowatorska propozycja zapewnia dwie korzyści. Po pierwsze, zachowujemy wiele właściwości przedstawionych we wcześniejszych pracach , takich jak: słaba nieistotność składni (WIS). Właściwość ta jest podobna do jednego z postulatów zaproponowanych przez AGM, ale w tym przypadku dla logiki niemonotonicznej i w ramach programowania zbiorów odpowiedzi (ASP)

TŁO

W tej sekcji przedstawiamy postępy w kontekście aktualizacji. Podajemy również kilka ogólnych definicji naszej teorii. Definiujemy naszą teorię dotyczącą programów logicznych.

Postępy w aktualizacjach

Rozważamy zadanie aktualizacji programów logicznych w ramach rozumowania niemonotonicznego i z czysto logicznego punktu widzenia. Ponieważ inteligentny agent znajduje się w środowisku podlegającym zmianom, wymagane jest, aby agent dostosowywał się w czasie. W przypadku agentów wykorzystujących techniki programowania logicznego do reprezentowania swojej wiedzy, wymagane jest, aby agent był w stanie odpowiednio aktualizować programy logiczne, aby zapewnić adaptowalność. Wybraliśmy jedno z podejść, a mianowicie semantykę zbioru odpowiedzi aktualizacji . Resides, podstawowa semantyka aktualizacji, która określa, w jaki sposób nowe, potencjalnie niespójne informacje muszą zostać włączone do bazy wiedzy, agent musi mieć określoną politykę aktualizacji, tj. specyfikację sposobu reakcji na nadejście aktualizacji. Kwestia sposobu określania żądań zmian dla baz wiedzy zyskała ostatnio coraz większą uwagę i opracowano odpowiednie języki specyfikacji dla programów logiki niemonotonicznej . W (Zacarías, 2005) wprowadziliśmy nową propozycję wzbogacenia operatora aktualizacji "⊕". Przedstawiliśmy tam udoskonalenie stabilnej semantyki modelu dla operatora aktualizacji. Przedstawiliśmy również nową właściwość, która pozwala nam stawić czoła aktualizacjom, w których nowe informacje zawierają reguły definiujące konserwatywne rozszerzenie. Tak więc podaliśmy rozszerzenie naszych właściwości udowodnionych w logice N. To podejście opiera się na pracy wykonanej przez Eitera, i inspirowane niedawnym podejściem przedstawionym przez Alferesa i innych. W niniejszej pracy udoskonalamy i wzbogacamy operator aktualizacji zaproponowany przez Eitera , dając w rezultacie nowy operator aktualizacji.

AKTUALIZACJE DLA APLIKACJI CZAS RZECZYWISTY

W tej sekcji przedstawiamy nowy mechanizm, który umożliwia szybką i łatwą aktualizację bazy wiedzy. Co więcej, ta propozycja spełnia podobne właściwości strukturalne do tych, które przedstawiliśmy w poprzednich pracach. Przedstawiamy zatem podstawowe koncepcje naszej teorii i prezentujemy nasz główny wkład oparty na wzorach ze znakiem .

Wstęp

Reguły zbudowane są z atomów zdaniowych i spójników zerowych T i ⊥, używając negacji jako błędu (¬) i spójnika (,). Reguła jest wyrażeniem postaci:

Głowa <- Ciało (1) Jeśli Ciało to T, to utożsamiamy regułę (1) z regułą Głowa. Jeśli Głowa to ⊥, to utożsamiamy regułę (1) z ograniczeniem. Program to zbiór reguł. Program logiczny P to (być może nieskończony) zbiór reguł. Dla programu P, I jest modelem P, oznaczanym jako I |= P, jeśli I |= L dla wszystkich L ∈ P. Jak pokazano , transformacja Gelfonda-Lifschitza dla programu P i modelu N ⊆ B_P (B_P oznacza zbiór atomów występujących w P) jest zdefiniowana wzorem

P^N = {rule^N : rule ∈ P}

gdzie (A <- B₁,&hellip , B_m, ¬C,sub>1, …, ¬C_n)^N jest albo:

a. A <- B₁,&hellip , B_m jeśli ∀j ≤ n: Cj ∉ N;
b. T, w przeciwnym wypadku.

Należy zauważyć, że P^N jest zawsze programem określonym. Możemy zatem obliczyć jego najmniejszy model Herbranda (oznaczony jako M_PN) i sprawdzić, czy pokrywa się on z modelem N, od którego zaczęliśmy:

Definicja 1. N jest stabilnym modelem P wtedy i tylko wtedy, gdy N jest minimalnym modelem P^N

NAPRAWA BAZ DANYCH

W niniejszym dokumencie przedstawiamy nasze nowsze podejście do aktualizacji w ramach napraw bazy danych. Sposób, w jaki podchodzimy do problemu aktualizacji, opiera się na idei naprawy niespójnej bazy danych. Zatem, biorąc pod uwagę potencjalnie niespójną bazę danych, ten mechanizm reprezentuje możliwe sposoby przywrócenia jej spójności za pomocą formuł ze znakiem. W naszym kontekście mechanizm ten służy do włączania nowych informacji, które mogą być niespójne z poprzednią bazą danych zawierającą wiedzę agenta. Podobnie , L definiuje język pierwszego rzędu, S to ustalony schemat bazy danych, a D to ustalona domena. Instancja bazy danych D składa się z atomów w języku L, gdzie D ma skończoną domenę aktywną, A(D), która jest podzbiorem D.

Definicja 2. Baza danych to para (D, IC), gdzie D jest instancją bazy danych, a IC, zbiór ograniczeń integralności, jest skończonym i klasycznie spójnym zbiorem formuł w L. Zatem baza danych to : DB = (D, IC), niech DB^A = D ∪ ICA = D ∪ {ρ(ψ) ? ψ ∈ IC, ρ : var(ψ) -> A(D)}, gdzie ρ jest podstawieniem podstawowym zmiennych do indywiduów A(D), domena aktywna D, DB to Nazywa się to rozwinięciem Herbranda DB. Ponieważ D, IC i A(D) są zbiorami skończonymi, DB^A również jest skończony, a zatem Σ^DB = {p₁, p₂, …, p_n}, zbiór formuł atomowych występujących w DB^A, jest również skończony.

AKTUALIZACJE OPARTE NA FORMUŁACH ZE ZNAKIEM

Ze względu na swoją prostotę nasz nowy proces aktualizacji nadaje się do aplikacji, które muszą udzielać odpowiedzi w czasie rzeczywistym. W pracy (Ariely, Denecker, Nuffelen i Bruynooghe, 2004) autorzy zakładają, że baza danych jest niespójna, a następnie podają ogólny opis sposobu przywracania spójności instancji baz danych, które nie spełniają danego zestawu ograniczeń integralności. W niniejszym artykule adaptujemy tę metodę do aktualizacji programów logicznych i ilustrujemy, jak można ją efektywnie wykorzystać w naszym kontekście. W niniejszym artykule rozważamy aktualizacje w kontekście programów logicznych, tj. zakładamy, że baza danych jest reprezentowana przez program logiczny. Zatem w naszym kontekście zaczynamy od faktu, że nasza baza danych jest aktualizowana nowymi informacjami, co powoduje jej niespójność. W tym momencie stosujemy tę metodę w celu zapewnienia spójności naszej bazy danych. Poniżej przedstawiamy ogólne ramy. Baza danych to para (D, IC), gdzie D jest instancją bazy danych, a IC, zbiór ograniczeń integralności, to skończony i klasycznie spójny zbiór formuł w języku. Biorąc pod uwagę potencjalnie niespójną bazę danych, naszym celem jest przywrócenie jej spójności, tj. naprawa bazy danych:

Definicja 3. Podobnie jak w (Ariely, Denecker, Nuffelen i Bruynooghe, 2004), aktualizacja bazy danych DB = (D, IC) to para {Insert, Retract}, s.t. Insert ∩ D = Φ i Retract ⊆ ? D. Para DB jest aktualizacją DB,dla której (D ∪ Insert \ Retract, IC) jest spójną bazą danych.

Intuicyjne znaczenie jest następujące: baza danych jest aktualizowana poprzez wstawianie elementów insert i usuwanie elementów Retract. Aktualizacja jest parą, gdy wynikowa baza danych jest spójna. Zauważ, że jeśli DB jest spójna, to (Φ,Φ) jest parą DB.

Poniżej podajemy kilka przykładów ilustrujących, jak ten mechanizm jest dostosowany do aktualizacji.

Przykład 1. Ten przykład ilustruje codzienną aktualizację dotyczącą wady energetycznej. Załóżmy, że masz następującą bazę danych:

DB: sen <- &no;tv-on. noc. tv-on. oglądanie-tv <- tv-on. <- awaria-zasilania, tv-on.

W tym przypadku baza danych jest spójna, jeśli zaktualizujemy ją za pomocą następującej reguły:

awaria zasilania.

Ta baza danych nie jest spójna. Zgodnie z formatem zdefiniowanym w (Ariely, Denecker, Nuffelen i Bruynooghe, 2004) ten przykład jest parą:

DB = ({sen <- &NOT; ¬tv-on., noc., tv-on., oglądanie-tv <- tv-on., awaria-zasilania.}, {<- awaria-zasilania, tv-on.})

Dlatego możemy zaadaptować metodę zaproponowaną w (Ariely, Denecker, Nuffelen i Bruynooghe, 2004) i przeprowadzić poprawną aktualizację tej bazy danych w następujący sposób:

Najpierw dodajemy do naszej początkowej konfiguracji nowe informacje (aktualizacja):

DB = ({sen <- ¬tv-on., noc., tv-on., oglądanie-tv <- tv-on., awaria-zasilania.}, {<- awaria-zasilania, tv-on, awaria zasilania.})

Po drugie, otrzymujemy wzór ze znakiem:

(¬awaria zasilania ∨ ¬tv-on) ∧ awaria zasilania.

Korzystając z formatu (Ariely, Denecker, Nuffelen i Bruynooghe, 2004), otrzymujemy:

(¬¬S_{awaria zasilania} ∨ ¬¬S_tv-on) ∧ ¬S_{awaria zasilania}. Jest to równoważne:

(S_{awaria zasilania}∨ S_{_tv-on}) ∧ ¬S_{awaria zasilania}

Po trzecie, obliczamy v^R - wartość powiązaną z R, uzyskując:

v^R(S_{awaria zasilania}) = 1
v^R(S_tv-wł) = 1
v^R(¬S_{Awaria zasilania}) = 0

Dlatego mamy: ({awaria zasilania}, {tv-wł.})

Oznacza to, że sugerowana aktualizacja to:

Wstaw -> {awaria zasilania}
Wycofaj -> {tv-wł.}

Jak widać, jest to oczekiwany rezultat. Teraz pokażemy kolejny przykład, wykorzystując metodę przedstawioną w (Eiter, Fink, Sabattini i Thompits, 2000).

Przykład 2. Ten program opisuje pewną wiedzę o niebie (Banti, Alferes i Brogi, 2003). Załóżmy, że masz następującą bazę danych:

DB: dzień <- ¬noc.
¬see-stars.
<- see-stars, dzień.

W tym przypadku baza danych jest spójna, jeśli jednak zaktualizujemy $DB$ następującą regułą:

see-stars.

Ta baza danych nie jest spójna. Zgodnie z formatem zdefiniowanym w (Ariely, Denecker, Nuffelen i Bruynooghe, 2004), ten przykład jest parą:

DB = ({dzień <- ¬noc., ¬zobacz-gwiazdy.}, {<-zobacz-gwiazdy, dzień.})

Dlatego możemy zaadaptować metodę zaproponowaną w (Ariely, Denecker, Nuffelen i Bruynooghe, 2004), uzyskując poprawną aktualizację tej bazy danych w następujący sposób:

Najpierw dodajemy naszą początkową konfigurację do nowych informacji (aktualizacja):

DB = ({dzień <- ¬noc., ¬zobacz-gwiazdy.}, {<-zobacz-gwiazdy, dzień, zobacz-gwiazdy.})

Po drugie, otrzymujemy wzór ze znakiem:

(¬zobacz-gwiazdy ∨ ¬dzień) ∧ zobacz-gwiazdy.

Korzystając z formatu (Ariely, Denecker, Nuffelen i Bruynooghe, 2004), otrzymujemy:

(¬¬S_see-gwiazdki∨ ¬¬Dzień) ∧ ¬¬S_see-gwiazdki.

Jest to równoważne:

(S_see-gwiazdki ∨ Dzień) ∧ S_see-gwiazdki.

Po trzecie, obliczamy v^R, wartość powiązaną z R, uzyskując:

v^R(S_see-gwiazdki) = 1
v^R(S_{see-gwiazdkil}) = 1
v^R(S_see-gwiazdki) = 1

Mamy zatem: ({see-stars}, {day})

Oznacza to, że sugerowana aktualizacja to:

Wstaw -> {see-stars}
Cofnij -> {day}

jest to zgodne z oczekiwaniami.

PRZYSZŁE TRENDY

Podobnie jak w (Eiter, Fink, Sabattini i Thompits, 2000), zbiega się to z tym, że ze względu na pozorny brak minimalności zmiany, rozważaliśmy udoskonalenia semantyki w kategoriach minimalnych i ściśle minimalnych zbiorów odpowiedzi. Kilka kwestii pozostaje do dalszych prac. Interesujący punkt dotyczy formułowania postulatów (zasad lub właściwości) dla operatora aktualizacji w programach logicznych i, bardziej ogólnie, w teoriach niemonotonicznych. Jak widać , kilka postulatów z obszaru zmiany teorii logicznej zawodzi w programach aktualizacji. Można to wyjaśnić dominującą rolą składni dla aktualizacji, ucieleśnioną przez przyczynowe odrzucenie reguł. Rozszerzyliśmy nasz operator na semantykę Pstable. Powinniśmy jednak kontynuować pracę w tym kierunku, ponieważ istnieją właściwości takie jak:

P ⊕ P₁ ⊕ Q ≡ P ⊕ P₂ ⊕ Q

dla każdego programu P_i i Q, które nie zawsze są spełnione, ponieważ nasza właściwość jest spełniona przez prawo. Uważamy, że przyszłe badania obracały się wokół poszukiwania właściwości spełnianych przez operator aktualizacji i że w zasadzie zostały one rozpoczęte przez niektórych autorów.

WNIOSKI

W niniejszym artykule rozważyliśmy nową propozycję zapewnienia naszym agentom procesu aktualizacji. Nasza propozycja to nowatorska i prosta metodologia, która pozwala agentowi na ciągłe aktualizowanie swojej bazy wiedzy. Dzięki temu agent zachowuje się w sposób racjonalny, podobny do zachowania człowieka. Co więcej, jest to odpowiednia propozycja dla aplikacji wymagających odpowiedzi w czasie rzeczywistym. Otwiera ona również możliwości budowania rzeczywistych aplikacji, takich jak inteligentni agenci, których komponent racjonalny jest modelowany przez bazę wiedzy, która z kolei jest utrzymywana za pomocą programów logiki aktualizacji.

WSTĘP

Funkcje rankingowe zostały wprowadzone pod nazwą porządkowych funkcji warunkowych przez Spohna . Są one reprezentacjami stanów epistemicznych i ich dynamiki. Najbardziej kompleksową i aktualną prezentacją jest praca Spohna .

TŁO

Literatura dotycząca wiedzy, przekonań i niepewności w sztucznej inteligencji dzieli się na dwie szerokie klasy. W logice epistemicznej, teorii rewizji przekonań oraz rozumowaniu niemonotonicznym podejścia jakościowe są wykorzystywane do reprezentacji stanu epistemicznego agenta. W teorii prawdopodobieństwa i teoriach alternatywnych stany epistemiczne są reprezentowane ilościowo jako stopnie przekonań, a nie przekonania typu "tak" lub "nie" . Jedną z charakterystycznych cech funkcji rankingowych jest to, że są one ilościowe, ale mimo to wywołują wrażenie przekonania typu "tak" lub "nie", które spełnia standardowe wymogi racjonalności, tj. spójność i domknięcie dedukcyjne.

FUNKCJE RANKINGOWE

Niech W będzie niepustym zbiorem możliwości lub światów, a A ciałem propozycji nad W. Oznacza to, że A jest zbiorem podzbiorów W, który obejmuje zbiór pusty Ø (Ø ∈ A) i jest domknięty ze względu na dopełnienie względem W (jeśli A ∈ A, to W∧A ∈ A) i skończone przecięcie (jeśli A ∈ A i B ∈ A, to A∩B ∈ A). Funkcja ρ z ciała A nad W do liczb naturalnych N rozszerzonych o ∞,ρ: A -> N∪{∞}, jest (skończenie minimalną) funkcją rangowania na A wtedy i tylko wtedy, gdy dla wszystkich propozycji A, B w A:

1.ρ(W) = 0
2.ρ(Ø) = ∞
3.ρ(A∪B) = min{ρ(A), ρ(B)}

Jeżeli ciało propozycji A jest domknięte ze względu na przeliczalne przecięcie (jeżeli A₁ ∈ A, …, A_n ∈ A, …, n ∈ N, to A₁∩…∩A_n∩ …∈ A), tak że A jest ciałem σ, funkcja rangowania ρ na A jest przeliczalnie minimalna wtedy i tylko wtedy, gdy spełnia się dla wszystkich propozycji A₁ ∈ A, …, A_n ∈ A…



Jeżeli ciało zdań A jest zamknięte na dowolne przecięcie (jeśli B ⊆ A, to ∩B ∈ A), tak że A jest ciałem γ, funkcja rankingu ρ na A jest całkowicie minimalna wtedy i tylko wtedy, gdy zachodzi dla wszystkich zbiorów zdań B ⊆? A:



Funkcja rankingu ρ na A jest regularna tylko wtedy, gdy ρ(A) < ∞dla każdego niepustego lub spójnego zdania A w A. Warunkowa funkcja rankingu ρ(⋅|⋅): A×A -> N∪{∞} oparta na funkcji rankingu ρ na A jest zdefiniowana tak, że dla wszystkich zdań A, B w A:



ρ(⋅|B) jest funkcją rangowania na A, dla każdego zdania B w A. Funkcja κ ze zbioru światów W do liczb naturalnych N, κ: W -> N, jest punktową funkcją rangowania na W wtedy i tylko wtedy, gdy κ(w) = 0 dla co najmniej jednego świata w w W. Każda punktowa funkcja rangowania κ na W indukuje regularną i całkowicie minimalną funkcję rangowania ρ_κ na każdym ciele zdań A nad W poprzez zdefiniowanie



Huber (2006) omawia, w jakich warunkach funkcja rankingowa w polu propozycji A wywołuje punktową funkcję rankingową w zbiorze światów W. Ranga propozycji A, ρ(A), reprezentuje stopień, w jakim agent z funkcją rankingową ρ nie wierzy w A. Jeśli ρ(A) = 0, agent nie nie wierzy w A. Nie oznacza to jednak, że wierzy w A. Może on zawiesić osąd i nie nie wierzyć ani w A, ani w jego dopełnienie lub negację W∧A (w tym przypadku ρ(A) = ρ(W∧A) = 0). Raczej wiara w tezę charakteryzuje się niewiarą w jej negację: agent z funkcją rangowania ρ: A -> N∪{∞} wierzy w A ∈ A wtedy i tylko wtedy, gdy ρ(W∧A) > 0. Zbiór przekonań Bel_ρ agenta z funkcją rangowania ρ: A -> N∪{∞} to zbiór wszystkich twierdzeń, w które wierzy: Bel_^ρ = {A ∈ A: ρ(W∧A) > 0}. Aksjomaty teorii rangowania wymagają, aby agent nie nie wierzył zarówno w tezę, jak i jej negację - tj. co najmniej jedno z A, W∧A musi mieć przypisaną rangę 0. Zatem agent z funkcją rangowania ρ: A -> N∪{∞} wierzy w A ∈ A wtedy i tylko wtedy, gdy ρ(W∧A) > ρ(A). Dla danego ρ: A -> N∪{∞} sugeruje to zdefiniowanie funkcji wiary indukowanej przez ρ, β_ρ: A -> Z∪{±∞}, tak aby dla wszystkich propozycji A w A: β_ρρ przypisuje liczby dodatnie propozycjom, w które się wierzy, liczby ujemne propozycjom, w które się nie wierzy, a 0 tym propozycjom i ich negacjom, w odniesieniu do których agent zawiesza osąd. W konsekwencji Bel_ρ = {A ∈ A:β_ρ(A) > 0} Bel_ρ jest niesprzeczny i dedukcyjnie domknięty w sensie skończonym, dla każdej funkcji rangowania ρ na A. To znaczy, ∩B ≠ Ø dla każdego skończonego B ⊆ Bel_ρ; i A ∈ Bel_ρ, jeśli istnieje skończony B ⊆ Bel_ρ taki, że ∩B ⊆ A, dla dowolnego A ∈ A. Jeśli ρ: A -> N∪{∞} jest przeliczalnie/zupełnie minimitywne, Bel_ρ jest niesprzeczny i dedukcyjnie domknięty w następującym przeliczalnym/zupełnym sensie: ∩B ≠ Ø dla każdego przeliczalnego/dowolnego B ⊆ Bel_ρ; i A ∈ Bel_ρ, jeśli istnieje przeliczalny/dowolny B ⊆ Bel_ρ taki, że ∩B ⊆ A, dla dowolnego A ∈ A. Jak zobaczymy poniżej, z diachronicznego punktu widzenia również odwrotność jest prawdziwa. Najpierw jednak musimy omówić, w jaki sposób agent epistemiczny ma aktualizować swoją funkcję rankingową, gdy dowiaduje się nowych informacji.

REGUŁY AKTUALIZACJI

Teoria stanów epistemicznych jest niekompletna, jeśli nie uwzględnia sposobu, w jaki stany epistemiczne są aktualizowane, gdy agent otrzymuje nowe informacje. Ponieważ istnieją różne formaty, w których agent może otrzymywać nowe informacje, istnieją różne reguły aktualizacji.Najprostszym i najbardziej nierealistycznym przypadkiem jest sytuacja, w której agent staje się pewien nowego twierdzenia. Przypadek ten jest omówiony w

Prostej Warunkalizacji

Jeśli stan epistemiczny agenta w czasie t jest reprezentowany przez funkcję rangowania ρ na A, i jeśli, między t a t′, agent staje się pewien twierdzenia E ∈ A i żadnego logicznie silniejszego twierdzenia E+ ⊂ E, E+ ∈ A, to stan epistemiczny agenta w czasie t′ powinien być reprezentowany przez funkcję rangowania ρ′ = ρ(⋅|E) na A. Zazwyczaj jednak nie uczymy się poprzez upewnienie się co do twierdzenia. W większości przypadków nowe informacje jedynie zmieniają siłę naszych przekonań w różnych twierdzeniach. Ilustruje to wariant przykładu podanego przez Jeffreya (1983). Niech nasza agentka interesuje się kolorem dywanu w swoim pokoju hotelowym. W chwili t, przed zameldowaniem, nie wierzy ani nie odrzuca żadnej z następujących trzech hipotez: dywan jest beżowy (beżowy), dywan jest brązowy (brązowy), dywan jest czarny (czarny). Jest jednak pewna, że dywan jest albo beżowy, albo brązowy, albo czarny. Odpowiednia część jej funkcji rangowania w chwili t wygląda zatem następująco: ρ(beżowy) = ρ(niebeżowy) = ρ(brązowy) = ρ(niebrązowy) = ρ(czarny) = ρ(nieczarny) = ρ(beżowy lub brązowy lub czarny) = 0, ρ(ani beżowy, ani brązowy, ani czarny) = ∞. W chwili t′, po zameldowaniu się i otwarciu drzwi do pokoju, agentka zdaje sobie sprawę, że dywan jest dość ciemny. W rezultacie uważa, że dywan jest albo brązowy, albo czarny. Ponieważ jednak jest późno w nocy, zasłony są zaciągnięte, a ona jeszcze nie zapaliła światła, nie może stwierdzić, czy dywan jest brązowy, czy czarny. Jej rangi dla odpowiednich zdań zmieniają się zatem na następujące wartości: ρ′(beżowy) = ρ′(nie brązowy) = ρ′(nie czarny) = 1, ρ′(nie beżowy) = ρ′(brązowy) = ρ′(czarny) = 0. Zmiana siły przekonań agentki na temat koloru dywanu wpłynie na siłę jej przekonań na temat koloru, powiedzmy, mebli w pokoju hotelowym. Na przykład, w chwili t, nasz agent jest dość pewny, że w pokoju hotelowym nie ma ciemnych mebli, jeśli dywan jest brązowy - i podobnie, jeśli dywan jest czarny. Jest również dość pewna, że w pokoju hotelowym są ciemne meble, jeśli dywan jest beżowy. Odpowiednia część jej funkcji rankingowej w czasie t wygląda następująco: ρ(ciemny|brązowy) = ρ(ciemny|czarny) = 3, ρ(ciemny|beżowy) = 0. Oznacza to, że w czasie t agent ani nie uważa, że meble są ciemne, ani że nie są ciemne, ρ(ciemny) = ρ(nieciemny) = 0. Teraz ważnym pytaniem jest, jak agent powinien zaktualizować resztę swojej funkcji rankingowej (w tym rangi dla zdań dotyczących koloru mebli), gdy jej rangi dla zdań dotyczących koloru dywanu zmieniają się, jak określono powyżej. Odpowiedź sformułowana już przez Spohna jest podana przez

Warunkowanie Spohna

Jeżeli stan epistemiczny agenta w czasie t jest reprezentowany przez funkcję rangowania ρ na A, a jeżeli pomiędzy t i t′ rangi agenta na podziale {E_i \in \begin{cal}A\ end{cal}: E_i \in I} zmieniają się na n_i \in N\cup{\infty} przy min_i{n_i}=0 (n_i=0 jeśli E_i=W i n_i=\infty jeśli E_i=\emptyset), a skończone rangi agenta nie zmieniają się przy żadnym drobniejszym podziale, wówczas stan epistemiczny agenta w czasie t′ powinien być reprezentowany przez funkcję rangowania ρ′ = min{ρ(⋅|E₁) + r₁, …, ρ(⋅|E_n) + r_n,…} na A. Zastosowane do naszego przykładu oznacza to że w chwili t′ ranga agenta dla twierdzenia, że meble są ciemne, powinna wynosić ρ′(ciemne) = min{ρ(ciemne|beżowe) + 1, ρ(ciemne|brązowe) + 0, ρ(ciemne|czarne) + 0} = 1. Oznacza to, że w chwili t′ agent wierzy, choćby bardzo słabo, że meble nie są ciemne. Warunkowanie Spohna obejmuje warunkowanie proste jako przypadek szczególny.

UZASADNIENIE

Teoria rangowania podpowiada podmiotowi epistemicznemu, jak organizować swoje przekonania i jak je aktualizować, gdy otrzymuje nowe informacje w różnych formatach. Dlaczego podmiot powinien stosować się do tych zaleceń? Odpowiedź na to pytanie wymaga odrobiny terminologii. Stopień zakorzenienia podmiotu w propozycji A to liczba źródeł informacji dostarczających informacji A, które są potrzebne, aby podmiot porzucił niewiarę w A. Jeśli podmiot od początku nie wątpi w A, jego stopień zakorzenienia w A wynosi 0. Jeśli żadna skończona liczba źródeł informacji dostarczających informacji A nie zmusi podmiotu do porzucenia niewiary w A, jego stopień zakorzenienia w A wynosi ∞. Stopnie zakorzenienia służą do pomiaru stopnia niewiary podmiotu epistemicznego. Jeśli chcesz zmierzyć mój stopień niedowierzania w tezę, że Madryt jest stolicą Hiszpanii, postaw mnie na ruchliwym placu w centrum Madrytu i policz liczbę osób przechodzących obok i mówiących mi, że Madryt jest stolicą Hiszpanii. Mój stopień utwierdzenia się w tezie, że Madryt jest stolicą Hiszpanii, wynosi n, na wypadek gdybym przestał nie wierzyć, że Madryt jest stolicą Hiszpanii po tym, jak n osób przejdzie obok i powie mi, że tak jest - pod warunkiem, że wszystkie te osoby są niezależne i równie wiarygodne, a wręcz minimalnie wiarygodne. Większość ludzi (a na pewno wszyscy ludzie w Madrycie) jest jednak bardziej niż minimalnie wiarygodna. Stopień niedowierzania agenta w A definiuje się zatem jako liczbę źródeł informacji dostarczających informacji A, które byłyby potrzebne, aby agent zrezygnował ze swojej niewiary w A, gdyby te źródła informacji były niezależne i minimalnie wiarygodne. Teraz możemy wyjaśnić, dlaczego stopnie niewiary agenta powinny podlegać rachunkowi rangowania, a zatem być rangami, i dlaczego agent powinien aktualizować swoje rangi zgodnie z warunkowością Spohna. Powinien to zrobić, ponieważ jest to konieczne i wystarczające, aby zawsze posiadał spójne i dedukcyjnie domknięte przekonania. Dokładniej, Huber dowodzi następującego.

Twierdzenie o spójności

Zbiór przekonań agenta jest i zawsze będzie spójny i dedukcyjnie domknięty w sensie skończonym/przeliczalnym/zupełnym (i ewentualnie warunkowy w zależności od pewnego twierdzenia dowodowego) wtedy i tylko wtedy, gdy funkcja stopnia niewiary tego agenta jest skończenie/przeliczalną/zupełnie minimalną funkcją rangowania, a agent aktualizuje się zgodnie z warunkowością Plaina/Spohna/Shenoya, gdy otrzymuje informacje w odpowiednim formacie. Z tego punktu widzenia aksjomaty i reguły aktualizacji teorii rangowania są niczym innym jak diachroniczną wersją spójności i domknięcia dedukcyjnego.

PRZYSZŁE TRENDY

Jednym z pytań w sztucznej inteligencji jest to, w jaki sposób agent powinien aktualizować swój stan epistemiczny, jeśli poznaje nowe informacje pojęciowe, nie ucząc się jednocześnie niczego faktycznego o świecie, w którym żyje. Istnieje kilka sposobów, w jakie taka zmiana pojęciowa może nastąpić. Agent może nauczyć się nowego pojęcia, jak wtedy, gdy enologiczny ignorant poznaje pojęcie barrique. Agent może też dowiedzieć się, że pominął możliwość ze swojego zbioru światów, jak wtedy, gdy enologiczny ignorant dowiaduje się, że oprócz win czerwonych i białych istnieją wina różowe. Wszystkie te zmiany pojęciowe wiążą się z przyjęciem nowego zbioru światów W, a w konsekwencji nowego pola propozycji A po stronie agenta. Żadna z tych zmian pojęciowych nie wydaje się być odpowiednio modelowana przez żaden z formalizmów wymienionych na początku. Teoria rankingowa jest w stanie odpowiednio modelować te zmiany pojęciowe, stosując tzw. ranking ur lub tabula rasa - tj. funkcję rankingową, która przypisuje rangę 0 każdemu stwierdzeniu. Jeśli agent dodaje nowe możliwości do swojego zbioru światów, powinien po prostu przypisać rangę 0 wszystkim tym nowym możliwościom. Podobnie jest w przypadku zastąpienia starych światów przez bogatsze.

WNIOSKI

Funkcje rangowania są niezbędnym narzędziem sztucznej inteligencji. Po pierwsze, wydają się one adekwatnie modelować większość, jeśli nie wszystkie zjawiska, którymi zajmują się zarówno jakościowe, jak i ilościowe podejścia do niepewności. Po drugie, zapewniają powiązanie między tymi dwiema klasami podejść, którego dotychczas brakowało. Po trzecie, mogą one radzić sobie ze zjawiskami, z którymi nie radzą sobie ani jakościowe, ani ilościowe podejścia.