Técnicas para extraer expresiones regulares de un conjunto de datos etiquetados

Question

Supongamos que tengo un conjunto de datos de varios cientos de miles de cadenas (que son frases en lenguaje natural, si es que importa) que están etiquetadas con una determinada "etiqueta". Cada oración está etiquetada con exactamente una etiqueta, y hay alrededor de 10 etiquetas, cada una con aproximadamente un 10% del conjunto de datos que les pertenece. Existe un alto grado de similitud con la estructura de oraciones dentro de una etiqueta.

Sé que lo anterior suena como un ejemplo clásico de un problema de aprendizaje automático, pero quiero hacer una pregunta ligeramente diferente. ¿Existen técnicas conocidas para generar programáticamente un conjunto de expresiones regulares para cada etiqueta, que puede clasificar satisfactoriamente los datos de entrenamiento mientras se generaliza a datos de prueba futuros?

Estaría muy contento con las referencias a la literatura; Me doy cuenta de que no será un algoritmo directo :)

PS: Sé que la forma normal de clasificación es con técnicas de aprendizaje automático como SVM u otras. Sin embargo, estoy buscando explícitamente una forma de generar expresiones regulares. (Yo sería feliz con las técnicas de aprendizaje automático para la generación de las expresiones regulares, pero no con técnicas de aprendizaje automático para hacer la clasificación en sí!)

Answer 1

Hasta donde sé, este es el tema de investigación actual en computación evolutiva.

Éstos son algunos ejemplos:

Ver desliza 40-44 en

https://cs.byu.edu/sites/default/files/Ken_De_Jong_slides.pdf (existen diapositivas a partir de la publicación de esta respuesta).

Además, vea

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

para una revisión más detallada de un sistema presentado en 2012. GECCO

Answer 2

Nota:de mayo Esto ayudaría de alguna manera. Esta función siguiente genera un patrón RegEx para un valor dado de a y b. Donde a y b son cadenas alfa. Y la función generaría un patrón justo RegEx para que coincida con el rango entre a y b. La función solo tomaría los tres primeros caracteres para producir el patrón y produciría un result que podría ser algo así como la función starts-with() en algún idioma con un indicio de un favor general de RegEx.

Un ejemplo VB.NET sencilla

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 

Y se llama como

?GetRangePattern("ABC","DEF") 

produce este

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

Answer 3

Este problema generalmente se enmarca como la forma de generar autómatas finitos a partir de conjuntos de cadenas, en lugar de expresiones regulares, aunque es obvio que puede generar RE a partir de FAs ya que son equivalent.

Si busca inducción de autómatas, debería ser capaz de encontrar mucha literatura sobre este tema, incluidos los enfoques de GA.