Który algorytm klasyfikacji statystycznej może przewidzieć wartość prawda / fałsz dla sekwencji danych wejściowych?

15

Biorąc pod uwagę sekwencję danych wejściowych, muszę ustalić, czy sekwencja ta ma pewną pożądaną właściwość. Właściwość może być tylko prawdą lub fałszem, tzn. Istnieją tylko dwie możliwe klasy, do których może należeć sekwencja.

Dokładny związek między sekwencją a właściwością jest niejasny, ale uważam, że jest bardzo spójny i powinien podlegać klasyfikacji statystycznej. Mam wiele przypadków trenowania klasyfikatora, chociaż może to być nieco głośne, w tym sensie, że istnieje niewielkie prawdopodobieństwo, że sekwencja zostanie przypisana niewłaściwej klasie w tym zestawie treningowym.

Przykładowe dane treningowe:

Sequence 1: (7 5 21 3 3) -> true
Sequence 2: (21 7 5 1) -> true
Sequence 3: (12 21 7 5 11 1) -> false
Sequence 4: (21 5 7 1) -> false
...

Z grubsza, właściwość jest określona przez zestaw wartości w sekwencji (np. Obecność „11” oznacza, że ​​właściwość prawie na pewno będzie fałszywa), a także kolejność wartości (np. „21 7 5 „znacznie zwiększa szansę, że właściwość jest prawdziwa).

Po treningu powinienem być w stanie nadać klasyfikatorowi wcześniej niewidoczną sekwencję, na przykład (1 21 7 5 3), i powinien dać pewność, że właściwość jest prawdziwa. Czy istnieje dobrze znany algorytm szkolenia klasyfikatora z tego rodzaju wejściami / wyjściami?

Rozważyłem naiwny klasyfikator bayesowski (który tak naprawdę nie da się dostosować do faktu, że kolejność ma znaczenie, przynajmniej nie bez poważnego złamania założenia, że ​​dane wejściowe są niezależne). Zbadałem również podejście ukrytego modelu Markowa, które wydaje się nie mieć zastosowania, ponieważ dostępne jest tylko jedno wyjście, zamiast jednego wyjścia na wejście. Co mnie ominęło?

Roman Starkov
źródło
Czy masz sposób na zmierzenie odległości między parą sekwencji? Czy znana jest minimalna i / lub maksymalna długość sekwencji?
Craig Wright,
@CraigWright Nie mogę znaleźć odpowiedniego miernika odległości. Można założyć maksymalną długość rzędu 12 i minimum około 4. Ponadto istnieje około 30 różnych wartości (nie są one nieograniczonymi naturami; po prostu dość mały zestaw możliwości)
Roman Starkov
Jakie są twoje zmienne wielokrotnych odpowiedzi, o których wspominasz? Czytałem twój problem, ponieważ jest to wyjście binarne i być może możesz po prostu utworzyć zmienne zastępcze Var1.1, Var1.12, ..., Var12.12
B_Miner
@B_Miner Być może nie rozumiem, jak działa HMM, ale wydaje się, że działa on w następujący sposób: karmię go moją sekwencją wejściową (abcde) i wyświetla ona sekwencję ukrytą najlepiej pasującą do tego, a mianowicie (a 'b' c 'd' e ' ). Nie sądzę, żeby zmienne fikcyjne rozwiązały to; Potrzebuję prawdziwej / fałszywej klasyfikacji dla całej sekwencji.
Roman Starkov,
@romkyns, nie tak działa HMM. HMM jest procesem probabilistycznym. Biorąc pod uwagę sekwencję HMM M , możesz obliczyć prawdopodobieństwo, że M wyprowadzi s (używając programowania dynamicznego; algorytm przekazywania). Ponadto, biorąc pod uwagę zestaw sekwencji treningowych, możesz znaleźć HMM M, który ma maksymalne prawdopodobieństwo wytworzenia tych sekwencji treningowych (przy użyciu algorytmu Baum-Welch). Więc HMM może być czymś, co można wypróbować tutaj. Będzie jednak kilka szczegółów do uzupełnienia. sMMsM
DW

Odpowiedzi:

10

Można wypróbować podejście probabilistyczne podobne do naiwnego klasyfikatora Bayesa, ale przy słabszych założeniach. Na przykład zamiast silnego założenia niezależności, należy przyjąć założenie Markowa:

p(xc)=p(x0c)tp(xtxt1,c)

to etykieta twojej klasy, x to twoja sekwencja. Musisz oszacować dwa rozkłady warunkowe, jeden dla c = 1 i jeden dla c = 0 .cxc=1c=0

Zgodnie z regułą Bayesa:

p(c=1x)=p(xc=1)p(c=1)p(xc=1)p(c=1)+p(xc=0)p(c=0).

Które rozkłady wybrać dla p(xtxt1,c) zależy od innych założeń dotyczących sekwencji i ilości dostępnych danych.

Na przykład możesz użyć:

p(xtxt1,c)=π(xt,xt1,c)iπ(xi,xt1,c)

Przy takich rozkładach, jeśli w twoich sekwencjach występuje 21 różnych liczb, musisz oszacować parametry π ( x t , x t , c ) plus 21 2 = 42 parametry dla p ( x 0c ) plus 2 parametry dla p ( c ) .21212=882π(xt,xt,c)212=42p(x0c)2p(c)

Jeśli założenia modelu nie są spełnione, może pomóc w precyzyjnym dostrojeniu parametrów bezpośrednio w odniesieniu do wydajności klasyfikacji, na przykład poprzez zminimalizowanie średniej utraty logarytmu

1#D(x,c)Dlogp(cx)

za pomocą opadania gradientu.

Lucas
źródło
(+1) Podoba mi się ten. Jednak może być potrzebna straszna ilość danych, aby uzyskać wiarygodne szacunki dla wszystkich p(xt|xt1,c)
steffen
Jeśli możesz przyjąć więcej założeń dotyczących zaangażowanych dystrybucji, możesz uniknąć znacznie mniejszych parametrów. Jeśli na przykład wiedziałeś, że jest dwumianowy, a E [ x tx t - 1 , c ] = x t - 1 , musisz oszacować tylko dwa parametry, jeden dla każdej wartości c . Oczywiście, jeśli nie możesz poczynić żadnych założeń i nie masz wystarczającej ilości danych, niewiele możesz zrobić. Nie ma darmowego lunchu.p(xtxt1,c)E[xtxt1,c]=xt1c
Lucas
6

Sugeruję zdefiniowanie niektórych funkcji, a następnie wybranie algorytmu uczenia maszynowego w celu zastosowania do tych funkcji.

Cechy: Zasadniczo każda cecha powinna być czymś, co można obliczyć z określonej sekwencji, i które Twoim zdaniem może mieć znaczenie dla tego, czy sekwencja ma właściwość, czy nie. Na podstawie opisu możesz rozważyć takie funkcje, jak:

  • „Worek liczb”. Możesz policzyć, ile razy każda możliwa liczba pojawia się w sekwencji. Załóżmy na przykład, że każda sekwencja składa się tylko z liczb 1-30. Następnie możesz wygenerować 30 funkcji; z TH funkcja liczy, ile razy liczba i pojawia się w sekwencji. Na przykład sekwencjaii(7 5 21 3 3) generuje wektor cech (0,0,2,0,1,0,1,0, ..., 0,1,0, ..., 0).

  • (7 5 21 3 3)7 55 2121 33 3302302

  • „Worek trygramów”. Można również rozważyć trygramy, które są podsekwencją trzech kolejnych liczb z oryginalnej sekwencji. Możesz zrobić to samo co powyżej.

d=30+302+303d wymiarowy wektor cech , który jest zbiorem cech. Gdy to zrobisz, możesz wyrzucić oryginalne sekwencje. Na przykład zestaw treningowy staje się wiązką par danych wejściowych / wyjściowych, gdzie wejściowy jest wektorem cech (odpowiadającym pewnej sekwencji z zestawu treningowego), a wyjściowy jest wartością logiczną (wskazującą, czy ta sekwencja ma właściwość, czy nie) .

ii

d

DW
źródło
Pierwszą próbą, którą faktycznie wdrożyłem, był „worek trygramów” z naiwną klasyfikacją bayesowską. Wyniki są zachęcające, ale nie świetne. Pomyślałem, że może to mieć związek z faktem, że trygramy wcale nie są niezależne: jeśli mam „1 2 3”, to bardzo prawdopodobne, że mam trygram „2 3 *”. Być może powinienem jeszcze trochę poeksperymentować z dokładnymi funkcjami.
Roman Starkov,
Więcej eksperymentów, zarówno z różnymi zestawami funkcji, jak iz różnymi algorytmami uczenia się, jest dobrym pomysłem. Ponadto, w oparciu o opis problemu, możesz chcieć dodać funkcje wyglądu każdego numeru (worek słów, a nie tylko worek trygramów): jeśli używasz tylko trygramów, utrudniasz algorytmowi uczenia maszynowego fakty takie jak „sekwencje zawierające 11 prawie na pewno nie mają właściwości”.
DW
2

To, co skutecznie robisz, to testowanie hipotez na szeregach czasowych. HMM będą dla Ciebie działać, ale będziesz musiał dostosować je do konkretnego przypadku.

Szczerze mówiąc, jeśli nie możesz zapisać jakiegoś matematycznego opisu tego, co próbujesz wykryć, nie zajdziesz daleko. Być może możesz nam powiedzieć o tym, jakiej funkcji oczekujesz?

użytkownik873
źródło
1
Uczenie maszynowe pokazało nam, że możemy dojść bardzo daleko, nie mając pojęcia, czego szukać.
bayerj
1

Biorąc pod uwagę maksymalną długość 12 w sekwencji, sieć neuronowa z 12 wejściami i jednym wyjściem może działać, ale będziesz musiał uzupełnić koniec każdej sekwencji zerami lub pewną obojętną wartością.

Craig Wright
źródło
1

Czy próbowałeś korzystać z sieci bayesowskich? To pierwsza rzecz, o której myślę, kiedy muszę połączyć wiele danych (przychodzących pojedynczo), aby dojść do prawdopodobieństwa zmiennej losowej.

Sieci bayesowskie nie opierają się na założeniu niezależności, jakie robi naiwny Bayes.

BTW, ukryte modele Markowa są szczególnym przypadkiem sieci bayesowskich.

DojoGojira
źródło