लेबल किए गए डेटा सेट से नियमित अभिव्यक्तियों को निकालने के लिए तकनीक

Question

मान लीजिए कि मेरे पास कई सौ हजार तारों का डेटा सेट है (जो प्राकृतिक भाषा वाक्यों के साथ होता है, यदि यह महत्वपूर्ण है) जिन्हें प्रत्येक एक निश्चित "लेबल" के साथ टैग किया जाता है। प्रत्येक वाक्य को बिल्कुल एक लेबल के साथ टैग किया जाता है, और लगभग 10 लेबल होते हैं, जिनमें से प्रत्येक का डेटा सेट लगभग 10% होता है। एक लेबल के भीतर वाक्यों की संरचना के लिए समानता की एक उच्च डिग्री है।

मुझे उपरोक्त ध्वनियों को मशीन सीखने की समस्या के शास्त्रीय उदाहरण की तरह पता है, लेकिन मैं थोड़ा अलग सवाल पूछना चाहता हूं। क्या प्रत्येक लेबल के लिए नियमित अभिव्यक्तियों का एक सेट प्रोग्रामेटिक रूप से उत्पन्न करने के लिए कोई ज्ञात तकनीक है, जो अभी भी भविष्य के परीक्षण डेटा को सामान्यीकृत करते समय प्रशिक्षण डेटा को सफलतापूर्वक वर्गीकृत कर सकती है?

मैं साहित्य के संदर्भों से बहुत खुश हूं; मुझे लगता है कि यह एक सरल एल्गोरिथ्म :) नहीं होगा

पुनश्च: मुझे पता है कि वर्गीकरण करने के लिए सामान्य तरीके से एक SVM या इस तरह की तरह मशीन लर्निंग तकनीक के साथ। हालांकि, मैं स्पष्ट रूप से नियमित अभिव्यक्ति उत्पन्न करने का एक तरीका ढूंढ रहा हूं। (मैं वर्गीकरण खुद करने के लिए नियमित अभिव्यक्ति पैदा करने के लिए मशीन लर्निंग तकनीक के साथ खुशी होगी, बस मशीन लर्निंग तकनीक के साथ नहीं है!)

Answer 1

जहां तक ​​मुझे पता है, यह विकासवादी गणना में वर्तमान शोध का विषय है।

यहाँ कुछ उदाहरण हैं:

देखें

https://cs.byu.edu/sites/default/files/Ken_De_Jong_slides.pdf पर 40-44 स्लाइड (स्लाइड इस उत्तर को पोस्ट करने के रूप में मौजूद हैं)।

इसके अलावा, एक प्रणाली के एक अधिक विस्तृत समीक्षा GECCO 2012 में प्रस्तुत के लिए

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

देख

Answer 2

नोट:मई यह किसी न किसी प्रकार में मदद मिलेगी। यह नीचे फ़ंक्शन a और b के दिए गए मान के लिए RegEx पैटर्न उत्पन्न करता है। जहां a और b दोनों अल्फा-स्ट्रिंग्स हैं। और समारोह a और b के बीच की सीमा से मेल खाने के लिए एक उचित RegEx पैटर्न उत्पन्न करेगा। समारोह में पैटर्न बनाने के लिए केवल पहले तीन वर्ण होंगे और result का उत्पादन होगा जो कि कुछ सामान्य भाषा में एक सामान्य RegEx पक्ष के संकेत के साथ starts-with() फ़ंक्शन जैसा हो सकता है।

सरल 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 

और यह कहा जाता है रूप

?GetRangePattern("ABC","DEF") 

इस

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

Answer 3

का उत्पादन

यह समस्या आम तौर पर नियमित अभिव्यक्तियों के बजाय तारों के सेट से परिमित ऑटोमाटा उत्पन्न करने के तरीके के रूप में तैयार की जाती है, हालांकि आप स्पष्ट रूप से एफए से आरई उत्पन्न कर सकते हैं क्योंकि वे equivalent हैं।

यदि आप ऑटोमाटा प्रेरण के लिए खोज करते हैं, तो आपको GA विषय सहित इस विषय पर बहुत सारे साहित्य मिल पाएंगे।