Techniki wyodrębniania wyrażeń regularnych z zestawu danych z etykietami

Question

Załóżmy, że mam zestaw danych o kilkuset tysiącach ciągów (które zdarzą się naturalnymi zdaniami językowymi, jeśli to ma znaczenie), z których każdy jest oznaczony określoną "etykietą". Każde zdanie jest oznakowane dokładnie jedną etykietą i jest około 10 etykiet, z których każda zawiera około 10% należących do nich zestawów danych. Istnieje wysoki stopień podobieństwa do struktury zdań w obrębie etykiety.

Wiem, że powyższe brzmi jak klasyczny przykład problemu z uczeniem maszynowym, ale chcę zadać nieco inne pytanie. Czy są jakieś znane techniki programowego generowania zestawu wyrażeń regularnych dla każdej etykiety, które mogą z powodzeniem zaklasyfikować dane treningowe, nadal generalizując przyszłe dane testowe?

Byłbym bardzo szczęśliwy z odniesieniami do literatury; Zdaję sobie sprawę, że nie będzie to prosty algorytm :)

PS: Wiem, że normalnym sposobem klasyfikacji jest technika uczenia maszynowego, taka jak SVM lub podobna. Jednak wyraźnie szukam sposobu generowania wyrażeń regularnych. (Byłbym zadowolony z technik uczenia maszynowego do generowania wyrażeń regularnych, nie tylko z technik uczenia maszynowego do prowadzenia samej klasyfikacji!)

Answer 1

O ile mi wiadomo, jest to przedmiotem bieżących badań w zakresie obliczeń ewolucyjnych.

Oto kilka przykładów:

Zobacz slajdy 40-44 w

https://cs.byu.edu/sites/default/files/Ken_De_Jong_slides.pdf (slajdy istnieć jako delegowania tej odpowiedzi).

również zobaczyć

http://www.citeulike.org/user/bartolialberto/article/10710768

do bardziej szczegółowego przeglądu systemu przedstawionego na GECCO 2012.

Answer 2

Uwaga:Może to jakoś pomoże. Ta funkcja poniżej generuje wzór RegEx dla danej wartości a i b. Gdzie a i b oba są ciągami alfa. Funkcja wygenerowałaby piękny wzór, który byłby zgodny z zakresem a i b. Ta funkcja wymagałaby utworzenia pierwszych trzech znaków w celu wygenerowania wzorca i wygenerowania funkcji result, która może być w pewnym języku podobna do funkcji z podpisem o ogólnej wartości RegEx.

Prosty przykład VB.NET

Public Function GetRangePattern(ByVal f_surname As String, ByVal l_surname As String) As String 
     Dim f_sn, l_sn As String 
     Dim mnLength% = 0, mxLength% = 0, pdLength% = 0, charPos% = 0 
     Dim fsn_slice$ = "", lsn_slice$ = "" 
     Dim rPattern$ = "^" 
     Dim alphas As New Collection 
     Dim tmpStr1$ = "", tmpStr2$ = "", tmpStr3$ = "" 

     '///init local variables 
     f_sn = f_surname.ToUpper.Trim 
     l_sn = l_surname.ToUpper.Trim 

     '///do null check 
     If f_sn.Length = 0 Or l_sn.Length = 0 Then 
      Return "-!ERROR!-" 
     End If 

     '///return if both equal 
     If StrComp(f_sn, l_sn, CompareMethod.Text) = 0 Then 
      Return "^" & f_sn & "$" 
     End If 

     '///return if 1st_name present in 2nd_name 
     If InStr(1, l_sn, f_sn, CompareMethod.Text) > 0 Then 
      tmpStr1 = f_sn 
      tmpStr2 = l_sn.Replace(f_sn, vbNullString) 
      If Len(tmpStr2) > 1 Then 
       tmpStr3 = "[A-" & tmpStr2.Substring(1) & "]*" 
      Else 
       tmpStr3 = tmpStr2 & "*" 
      End If 
      tmpStr1 = "^" & tmpStr1 & tmpStr3 & ".*$" 
      tmpStr1 = tmpStr1.ToUpper 
      Return tmpStr1 
     End If 

     '///initialize alphabets 
     alphas.Add("A", CStr(Asc("A"))) 
     alphas.Add("B", CStr(Asc("B"))) 
     alphas.Add("C", CStr(Asc("C"))) 
     alphas.Add("D", CStr(Asc("D"))) 
     alphas.Add("E", CStr(Asc("E"))) 
     alphas.Add("F", CStr(Asc("F"))) 
     alphas.Add("G", CStr(Asc("G"))) 
     alphas.Add("H", CStr(Asc("H"))) 
     alphas.Add("I", CStr(Asc("I"))) 
     alphas.Add("J", CStr(Asc("J"))) 
     alphas.Add("K", CStr(Asc("K"))) 
     alphas.Add("L", CStr(Asc("L"))) 
     alphas.Add("M", CStr(Asc("M"))) 
     alphas.Add("N", CStr(Asc("N"))) 
     alphas.Add("O", CStr(Asc("O"))) 
     alphas.Add("P", CStr(Asc("P"))) 
     alphas.Add("Q", CStr(Asc("Q"))) 
     alphas.Add("R", CStr(Asc("R"))) 
     alphas.Add("S", CStr(Asc("S"))) 
     alphas.Add("T", CStr(Asc("T"))) 
     alphas.Add("U", CStr(Asc("U"))) 
     alphas.Add("V", CStr(Asc("V"))) 
     alphas.Add("W", CStr(Asc("W"))) 
     alphas.Add("X", CStr(Asc("X"))) 
     alphas.Add("Y", CStr(Asc("Y"))) 
     alphas.Add("Z", CStr(Asc("Z"))) 

     '///populate max-min length values 
     mxLength = f_sn.Length 
     If l_sn.Length > mxLength Then 
      mnLength = mxLength 
      mxLength = l_sn.Length 
     Else 
      mnLength = l_sn.Length 
     End If 
     '///padding values 
     pdLength = mxLength - mnLength 
     f_sn = f_sn.PadRight(mxLength, "A") 
     'f_sn = f_sn.PadRight(mxLength, "~") 
     l_sn = l_sn.PadRight(mxLength, "Z") 
     'l_sn = l_sn.PadRight(mxLength, "~") 

     '///get a range like A??-B?? 
     If f_sn.Substring(0, 1).ToUpper <> l_sn.Substring(0, 1).ToUpper Then 
      fsn_slice = f_sn.Substring(0, 3).ToUpper 
      lsn_slice = l_sn.Substring(0, 3).ToUpper 
      tmpStr1 = fsn_slice.Substring(0, 1) & fsn_slice.Substring(1, 1) & "[" & fsn_slice.Substring(2, 1) & "-Z]" 
      tmpStr2 = lsn_slice.Substring(0, 1) & lsn_slice.Substring(1, 1) & "[A-" & lsn_slice.Substring(2, 1) & "]" 
      tmpStr3 = "^(" & tmpStr1 & "|" & tmpStr2 & ").*$" 
      Return tmpStr3 
     End If 

     '///looping charwise 
     For charPos = 0 To mxLength 
      fsn_slice = f_sn.Substring(charPos, 1) 
      lsn_slice = l_sn.Substring(charPos, 1) 
      If StrComp(fsn_slice, lsn_slice, CompareMethod.Text) = 0 Then 
       rPattern = rPattern & fsn_slice 
      Else 
       'rPattern = rPattern & "(" 
       If charPos < mxLength Then 
        Try 
         If Asc(fsn_slice) < Asc(lsn_slice) Then 
          tmpStr1 = fsn_slice & "[" & f_sn.Substring(charPos + 1, 1) & "-Z" & "]|" 
          If CStr(alphas.Item(Key:=CStr(Asc(fsn_slice) + 1))) < CStr(alphas.Item(Key:=CStr(Asc(lsn_slice) - 1))) Then 
           tmpStr2 = "[" & CStr(alphas.Item(Key:=CStr(Asc(fsn_slice) + 1))) & "-" & CStr(alphas.Item(Key:=CStr(Asc(lsn_slice) - 1))) & "]|" 
          Else 
           tmpStr2 = vbNullString 
          End If 
          tmpStr3 = lsn_slice & "[A-" & l_sn.Substring(charPos + 1, 1) & "]" 
          rPattern = rPattern & "(" & tmpStr1 & tmpStr2 & tmpStr3 & ").*$" 
          'MsgBox("f_sn:= " & f_sn & " -- l_sn:= " & l_sn & vbCr & rPattern) 
          Exit For 
         Else 
          Return "-#ERROR#-" 
         End If 
        Catch ex As Exception 
         Return "-|ERROR|-" & ex.Message 
        End Try 
       End If 
      End If 
     Next charPos 
     Return rPattern 
    End Function 

I to nazywa się

?GetRangePattern("ABC","DEF") 

produkuje ten

"^(AB[C-Z]|DE[A-F]).*$" 

Answer 3

Ten problem jest zwykle określany jako generowanie automatów skończonych z zestawów łańcuchów, a nie wyrażeń regularnych, choć oczywiście można wygenerować wartości RE z FA, ponieważ są one equivalent.

Jeśli poszukujesz automatów indukcyjnych , powinieneś być w stanie znaleźć sporo literatury na ten temat, w tym podejścia GA.