Czy komputer może „nauczyć się” wyrażenia regularnego na podstawie przykładów podanych przez użytkownika?

Czy komputer może „nauczyć się” wyrażenia regularnego na podstawie przykładów podanych przez użytkownika?

W celu wyjaśnienia:

• Ja nie chcę, aby dowiedzieć się wyrażeń regularnych.
• Chcę stworzyć program, który „uczy się” wyrażenia regularnego na podstawie przykładów, które są interaktywnie dostarczane przez użytkownika, być może poprzez wybranie części z tekstu lub wybranie znaczników początku lub końca.

Czy to możliwe? Czy istnieją algorytmy, słowa kluczowe itp., Dla których mogę użyć Google?

EDYCJA : Dziękuję za odpowiedzi, ale nie interesują mnie narzędzia, które zapewniają tę funkcję. Szukam informacji teoretycznych, takich jak artykuły, tutoriale, kod źródłowy, nazwy algorytmów, żeby móc stworzyć coś dla siebie.

Książka Wprowadzenie do obliczeniowej teorii uczenia się zawiera algorytm uczenia się automatu skończonego. Ponieważ każdy język regularny jest odpowiednikiem automatu skończonego, możliwe jest nauczenie się niektórych wyrażeń regularnych przez program. Kearns i Valiant pokazują przypadki, w których nie można nauczyć się automatu skończonego. Podobnym problemem jest nauczenie się ukrytych modeli Markowa , które są automatami probabilistycznymi, które mogą opisać sekwencję znaków. Zauważ, że większość współczesnych „wyrażeń regularnych” używanych w językach programowania jest w rzeczywistości silniejsza niż języki regularne, a zatem czasami trudniej jest się ich nauczyć.

Tak, jest to możliwe, możemy generować wyrażenia regularne z przykładów (tekst -> żądane wyodrębnienia). To działające narzędzie online, które wykonuje swoją pracę: http://regex.inginf.units.it/

Narzędzie online Regex Generator ++ generuje wyrażenie regularne na podstawie podanych przykładów przy użyciu algorytmu wyszukiwania GP. Algorytm GP jest oparty na wielocelowej przydatności, co prowadzi do wyższej wydajności i prostszej struktury rozwiązania (Occam's Razor). To narzędzie jest aplikacją demonstracyjną opracowaną przez Machine Lerning Lab, Trieste Univeristy (Università degli studi di Trieste). Proszę spojrzeć na samouczek wideo tutaj .

To jest projekt badawczy, więc możesz przeczytać o zastosowanych algorytmach tutaj .

Ujrzeć!:-)

Znalezienie znaczącego wyrażenia regularnego / rozwiązania na podstawie przykładów jest możliwe wtedy i tylko wtedy, gdy podane przykłady dobrze opisują problem. Rozważ te przykłady, które opisują zadanie wyodrębniania, szukamy określonych kodów pozycji; przykładami są pary tekst / wyodrębnianie:

"The product code is 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Patrząc na przykłady (człowiek) facet może powiedzieć: „kody pozycji to np. \ D ++ - 345 [AB]”

Kiedy kod przedmiotu jest bardziej liberalny, ale nie podaliśmy innych przykładów, nie mamy dowodów na dobre zrozumienie problemu. Zastosowanie rozwiązania wygenerowanego przez człowieka \ d ++ - 345 [AB] do następującego tekstu kończy się niepowodzeniem:

"On the back of the item there is a code: 966-347Z"

Musisz podać inne przykłady, aby lepiej opisać, co jest dopasowaniem, a co nie jest pożądanym: --ie:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Numer telefonu nie jest identyfikatorem produktu, może to być ważny dowód.

Żaden program komputerowy nigdy nie będzie w stanie wygenerować znaczącego wyrażenia regularnego wyłącznie na podstawie listy prawidłowych dopasowań. Pokażę ci dlaczego.

Załóżmy, że podajesz przykłady 111111 i 999999, jeśli komputer wygeneruje:

1. Wyrażenie regularne pasujące dokładnie do tych dwóch przykładów: (111111|999999)
2. Wyrażenie regularne pasujące do 6 identycznych cyfr (\d)\1{5}
3. Wyrażenie regularne odpowiadające 6 jedynkom i dziewiątkom [19]{6}
4. Wyrażenie regularne pasujące do dowolnych 6 cyfr \d{6}
5. Dowolny z trzech powyższych, z granicami słów, np \b\d{6}\b
6. Dowolny z trzech pierwszych, nie poprzedzony ani zakończony cyfrą, np (?<!\d)\d{6}(?!\d)

Jak widać, przykłady można uogólniać na wyrażenie regularne na wiele sposobów. Jedynym sposobem na zbudowanie przez komputer przewidywalnego wyrażenia regularnego jest wymóg wyszczególnienia wszystkich możliwych dopasowań. Następnie może wygenerować wzorzec wyszukiwania pasujący dokładnie do tych dopasowań.

Jeśli nie chcesz wymieniać wszystkich możliwych dopasowań, potrzebujesz opisu wyższego poziomu. Właśnie do tego służą wyrażenia regularne. Zamiast podawać długą listę 6-cyfrowych liczb, po prostu każ programowi dopasować „dowolne sześć cyfr”. W składni wyrażeń regularnych jest to \ d {6}.

Każda metoda dostarczania opisu wyższego poziomu, która jest tak elastyczna jak wyrażenia regularne, będzie również tak złożona, jak wyrażenia regularne. Wszystkie narzędzia, takie jak RegexBuddy mogą ułatwić tworzenie i testowanie opisu wysokiego poziomu. Zamiast bezpośrednio używać zwięzłej składni wyrażeń regularnych, RegexBuddy umożliwia użycie prostych angielskich bloków konstrukcyjnych. Ale nie może stworzyć dla ciebie opisu wysokiego poziomu, ponieważ nie może magicznie wiedzieć, kiedy powinien uogólniać twoje przykłady, a kiedy nie.

Z pewnością możliwe jest stworzenie narzędzia wykorzystującego przykładowy tekst wraz z dostarczonymi przez użytkownika wskazówkami do wygenerowania wyrażenia regularnego. Najtrudniejszą częścią projektowania takiego narzędzia jest to, w jaki sposób prosi użytkownika o informacje przewodnie, których potrzebuje, bez utrudniania nauki narzędzia niż same wyrażenia regularne i bez ograniczania narzędzia do typowych zadań regex lub prostych wyrażeń regularnych.

Tak, z pewnością jest to „możliwe”; Oto pseudokod:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

Problem polega na tym, że istnieje nieskończona liczba wyrażeń regularnych, które będą pasować do listy przykładów. Ten kod zapewnia najprostsze / najgłupsze wyrażenie regularne w zestawie, w zasadzie dopasowując wszystko na liście przykładów pozytywnych (i nic więcej, w tym wszystkie przykłady negatywne).

Przypuszczam, że prawdziwym wyzwaniem byłoby znalezienie najkrótszego wyrażenia regularnego, które pasuje do wszystkich przykładów, ale nawet wtedy użytkownik musiałby zapewnić bardzo dobre dane wejściowe, aby upewnić się, że wynikowe wyrażenie jest „właściwe”.

Uważam, że termin to „indukcja”. Chcesz zachęcić do regularnej gramatyki.

Myślę, że nie jest to możliwe przy ograniczonym zestawie przykładów (pozytywnych lub negatywnych). Ale jeśli dobrze pamiętam, można to zrobić, jeśli istnieje Wyrocznia, z którą można się skonsultować. (Zasadniczo musiałbyś pozwolić programowi zadawać użytkownikowi pytania tak / nie, dopóki nie będzie zadowolony).

Możesz trochę pobawić się tą stroną, jest całkiem fajna i wygląda na to, że robi coś podobnego do tego, o czym mówisz: http://txt2re.com

Istnieje język poświęcony takim problemom, oparty na prologu. Nazywa się progol .

Jak wspominali inni, podstawową ideą jest uczenie się indukcyjne, często nazywane ILP ( programowanie w logice indukcyjnej w kręgach sztucznej inteligencji w ).

Drugie łącze to artykuł wiki na temat ILP, który zawiera wiele przydatnych materiałów źródłowych, jeśli chcesz dowiedzieć się więcej na ten temat.

@Yuval jest poprawne. Patrzysz na obliczeniową teorię uczenia się lub „wnioskowanie indukcyjne”.

Pytanie jest bardziej skomplikowane niż myślisz, ponieważ definicja „uczenia się” jest nietrywialna. Jedna z powszechnych definicji mówi, że uczeń może wypluwać odpowiedzi, kiedy tylko chce, ale ostatecznie musi albo przestać wypluwać odpowiedzi, albo zawsze wypluwać tę samą odpowiedź. Zakłada to nieskończoną liczbę wejść i nie daje absolutnie żadnej gwarancji, kiedy program podejmie decyzję. Nie można również stwierdzić, kiedy podjął decyzję, ponieważ może później wypisać coś innego.

Zgodnie z tą definicją jestem prawie pewien, że zwykłych języków można się nauczyć. Według innych definicji, nie tak bardzo ...

Przeprowadziłem kilka badań w Google i CiteSeer i znalazłem następujące techniki / artykuły:

• Identyfikacja języka w limicie
• Prawdopodobnie w przybliżeniu poprawna nauka

Również „Uczenie się regularnych zestawów na podstawie zapytań i kontrprzykładów” Dany Angluin wydaje się obiecujące, ale nie mogłem znaleźć wersji PS lub PDF, tylko cytaty i artykuły seminaryjne.

Wydaje się, że jest to trudny problem nawet na poziomie teoretycznym.

Jeśli dana osoba może nauczyć się wyrażenia regularnego, to jest to zasadniczo możliwe w przypadku programu. Jednak program ten będzie musiał być poprawnie zaprogramowany, aby mógł się uczyć. Na szczęście jest to dość ograniczona przestrzeń logiki, więc nie byłoby to tak skomplikowane, jak nauczenie programu, aby móc widzieć obiekty lub coś w tym rodzaju.