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

95

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.

Daniel Rikowski
źródło
4
Jestem zaskoczony, że nikt nie wspomniał o Regex :: PreSuf
tripleee

Odpowiedzi:

44

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ć.

Yuval F.
źródło
44

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.

Fabiano Tarlao
źródło
5
To powinna być najlepsza odpowiedź. Jest to możliwe i to pokazuje. Źródło jest dostępne tutaj: github.com/MaLeLabTs/RegexGenerator
rjurney
Twój przykład kodów produktów pokazuje, dlaczego wspomniany człowiek powinien sprawdzić specyfikację kodów produktów i napisać wyrażenie regularne w oparciu o specyfikację, zamiast próbować wywnioskować wyrażenie regularne z ograniczonego zestawu przykładowych kodów produktów (niezależnie od tego, czy jest to osoba, czy program próbuje wywnioskować wyrażenie regularne).
Jan Goyvaerts
2
To jest właściwy sposób robienia rzeczy. Mój przykład to tylko sposób na koncepcyjne wyjaśnienie problemu. Czasami nie ma specyfikacji lub facet po prostu nie jest w stanie samodzielnie napisać wyrażenia regularnego (brak wiedzy).
Fabiano Tarlao,
Mówiąc bardziej precyzyjnie i jednoznacznie :-), „To jest właściwy sposób robienia rzeczy” -> „Masz rację, to jest najlepszy sposób robienia rzeczy, zawsze powinieneś zaczynać od specyfikacji, kiedy to możliwe”
Fabiano Tarlao
2
Artykuł „Wnioskowanie o wyrażeniach regularnych do wyodrębniania tekstu z przykładów” zawiera szczegółowe wyjaśnienie algorytmu machinelearning.inginf.units.it/publications/ ...
mimmuz
36

Ż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.

Jan Goyvaerts
źródło
Masz rację, wiele algorytmów uczenia się, które znalazłem po wysłaniu mojego pytania, wymaga informacji pozytywnych i negatywnych. O ile rozumiem, jednoznaczny „opis wyższego poziomu” nie jest konieczny, ponieważ użytkownik podaje go, odpowiadając na pytania.
Daniel Rikowski
Jeśli narzędzie zadaje pytania, to kombinacja pytań i udzielonych odpowiedzi tworzy opis wyższego poziomu. Jakość takich narzędzi w dużej mierze zależy od zadawanych przez nie pytań.
Jan Goyvaerts
To głupie, ponieważ jeśli podałeś inny przykład, możesz wyeliminować niektóre z tych możliwości. Kolejny przykład usuwa więcej.
Cris
2
@Cris: Zasada pozostaje bez względu na to, ile próbek dostarczysz. Po prostu zmienia możliwości. Na przykład dodanie 123456 zmian nr 2 do (\ d) \ 1 {5} | 123456 i nr 3 do [19] {6} | 123456. Lub może zmienić # 3 na [1-69] {6}. Może się nawet zdarzyć, że żądany wzorzec będzie pasował do 6 identycznych cyfr lub 6 cyfr, z których każda jest o jeden większa od poprzedniej cyfry. Nawet jeśli dostarczysz 10000 próbek liczb 6-cyfrowych, program nie będzie mógł rozróżnić numerów 1, 4, 5 lub 6 bez dodatkowych instrukcji od użytkownika.
Jan Goyvaerts
Wydaje mi się, że ten problem można łatwo rozwiązać w następujący sposób: program stara się być jak najbardziej ogólny (w granicach rozsądku), a następnie podaje przykłady innych rzeczy, które według niego pasowałyby. Po prostu mówiąc „tak” i „nie” proponowanym dopasowaniom, możesz pomóc mu zrozumieć granice tego, co faktycznie próbujesz uchwycić. Chciałbym zobaczyć narzędzie w edytorze tekstu, które wykorzystywało tę koncepcję i proponowane dopasowania z aktualnie otwartego pliku.
Jon McClung,
9

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”.

Daniel LeCheminant
źródło
3
Zaczyna robić się interesująco, gdy użytkownik wprowadzi próbki pozytywne i negatywne . Wyrażenie regularne musiałoby pasować do próbek dodatnich, a nie pasować do próbek ujemnych.
user55400
@blixtor - Właściwie to całkiem proste. Po prostu nie umieszczaj żadnego z negatywnych przykładów w skonstruowanym wyrażeniu regularnym, a zostaną odrzucone. Pamiętaj, że ten, który buduje kod, pasuje tylko do pozytywnego przykładu; negatywne przykłady (i wszystko inne) są z definicji wykluczone!
Daniel LeCheminant
Daniel ma rację. Bez opisu wyższego poziomu lista alternatyw jest wszystkim, co można konsekwentnie i dokładnie wywnioskować z listy przykładów.
Jan Goyvaerts
6

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).

Jay Kominek
źródło
Tak, właśnie to chcę zrobić, interaktywnie zapytać użytkownika.
Daniel Rikowski
Wydaje się, że odniesienia Yuvala F. są tym, co miałem na myśli, sugerowałbym przyjrzenie się im.
Jay Kominek,
5

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

Chad Birch
źródło
4

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.

patros
źródło
2

@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 ...

Brian Postow
źródło
2

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

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.

Daniel Rikowski
źródło
0

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.

cjk
źródło
1
Nieprawda, powinieneś szukać problemów, które są nierozstrzygalne na maszynach Turinga.
Stephen Curial
Aby być uczciwym, powiedziałem, że jeśli ktoś może nauczyć się REGEX, to maszyna może. Generalnie nie miałem tego na myśli.
cjk
@scurial Nie sądzę, że są problemy, które ludzie mogą rozwiązać, ale są nierozstrzygalne na maszynach Turinga, prawda?
Sunny88,