Các kỹ thuật để trích xuất các biểu thức chính quy ra khỏi tập dữ liệu có nhãn

Question

Giả sử tôi có tập dữ liệu gồm vài trăm nghìn chuỗi (đây là câu tự nhiên, nếu nó quan trọng) được gắn nhãn với một "nhãn" nhất định. Mỗi câu được gắn thẻ chính xác một nhãn và có khoảng 10 nhãn, mỗi nhãn có khoảng 10% tập dữ liệu thuộc về chúng. Có một mức độ tương tự cao với cấu trúc của các câu trong một nhãn.

Tôi biết các âm thanh trên như một ví dụ cổ điển về vấn đề học máy, nhưng tôi muốn đặt một câu hỏi hơi khác. Có bất kỳ kỹ thuật nào đã biết để tạo ra một bộ các cụm từ thông dụng có lập trình cho mỗi nhãn, có thể phân loại thành công dữ liệu đào tạo trong khi vẫn tổng quát hóa dữ liệu thử nghiệm trong tương lai không?

Tôi sẽ rất hài lòng với các tham chiếu đến văn học; Tôi nhận ra rằng đây sẽ không phải là một thuật toán đơn giản :)

PS: Tôi biết rằng cách phân loại thông thường là với các kỹ thuật học máy như SVM hoặc như vậy. Tuy nhiên, tôi đang tìm cách tạo một biểu thức chính quy . (Tôi sẽ hài lòng với với các kỹ thuật máy học để tạo ra các biểu thức thông thường, chỉ cần không phải với kỹ thuật máy học để thực hiện việc phân loại chính nó!)

Answer 1

Cho đến khi tôi biết, đây là chủ đề của nghiên cứu hiện tại trong tính toán tiến hóa.

Dưới đây là một số ví dụ:

Xem trượt 40-44 tại

https://cs.byu.edu/sites/default/files/Ken_De_Jong_slides.pdf (slide tồn tại như của việc đăng câu trả lời này).

Ngoài ra, xem

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

cho một bài đánh giá chi tiết hơn về một hệ thống được trình bày tại GECCO 2012.

Answer 2

Lưu ý:Có thể điều này sẽ giúp cách nọ cách kia. Hàm bên dưới này tạo mẫu RegEx cho một giá trị đã cho là a và b. Trong đó a và b cả hai đều là chuỗi alpha. Và chức năng sẽ tạo ra một mẫu RegEx hợp lý để phù hợp với phạm vi giữa a và b. Hàm sẽ chỉ lấy ba ký tự đầu tiên để tạo mẫu và tạo ra một result có thể giống như chức năng starts-with() ở một số ngôn ngữ với gợi ý về lợi ích chung của RegEx.

Một ví dụ đơn giản 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 

Và nó được gọi như

?GetRangePattern("ABC","DEF") 

sản xuất này

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

Answer 3

Vấn đề này thường được đóng khung như thế nào để tạo ra automata hữu hạn từ bộ chuỗi, thay vì biểu thức thông thường, mặc dù bạn rõ ràng có thể tạo ra REs từ FA vì chúng là equivalent.

Nếu bạn tìm kiếm xung quanh cảm ứng tự động, bạn sẽ có thể tìm thấy khá nhiều tài liệu về chủ đề này, bao gồm cả phương pháp GA.