Apakah menemukan ekspresi reguler minimum merupakan masalah NP-complete?

Saya memikirkan masalah berikut: Saya ingin menemukan ekspresi reguler yang cocok dengan serangkaian string tertentu (misalnya, alamat email yang valid) dan tidak cocok dengan yang lain (alamat email yang tidak valid).

Misalkan dengan ekspresi reguler yang kami maksud adalah mesin negara terbatas yang terdefinisi dengan baik, saya tidak akrab dengan terminologi yang tepat, tetapi mari kita sepakat pada beberapa kelas ekspresi yang diizinkan.

Alih-alih secara manual membuat ekspresi, saya ingin memberikannya satu set positif dan satu set contoh negatif.

Maka harus muncul dengan ekspresi yang cocok dengan +, menolak - dan minimal dalam beberapa hal yang didefinisikan dengan baik (jumlah negara dalam automata?).

Pertanyaan saya adalah:

• Sudahkah masalah ini dipertimbangkan, bagaimana ia dapat didefinisikan dengan cara yang lebih konkret dan dapat diselesaikan dengan efisien? Bisakah kita menyelesaikannya dalam waktu polinomial? Apakah NP lengkap, bisakah kita memperkirakannya entah bagaimana? Untuk kelas ekspresi apa itu bekerja? Saya akan sangat menghargai setiap pointer ke buku teks, artikel atau semacamnya yang membahas topik ini.
• Apakah ini terkait dengan kompleksitas Kolmogorov?
• Apakah ini terkait dengan cara belajar apa pun? Jika ekspresi reguler konsisten dengan contoh saya, berdasarkan minimal, dapatkah kita mengatakan sesuatu tentang kekuatan generalisasi pada contoh yang belum terlihat? Kriteria minimalitas apa yang lebih cocok untuk ini? Yang mana yang lebih efisien? Apakah ini ada hubungannya dengan pembelajaran mesin? Sekali lagi petunjuk apa pun akan sangat membantu ...

Maaf untuk pertanyaan berantakan ... Arahkan saya ke arah yang benar untuk mencari tahu. Terima kasih!

Ya, ini NP-Hard. Pitt dan Warmuth menunjukkan bahwa menemukan DFA terkecil yang konsisten dengan sampel yang diberikan tidak dapat diperkirakan dalam untuk konstanta apa pun , kecuali .$OPT^k$$k$$P = NP$

Mengenai pertanyaan pembelajaran: Kearns dan Valiant membuktikan bahwa Anda dapat menyandikan RSA menjadi DFA. Jadi, bahkan jika contoh berlabel berasal dari distribusi seragam, dapat digeneralisasi ke contoh di masa depan (juga bahkan berasal dari distribusi seragam) akan merusak RSA. Oleh karena itu, kami berpikir bahwa dalam kasus terburuk, memiliki contoh berlabel tidak membantu mempelajari DFA (dalam model PAC). Ini adalah salah satu hasil kekerasan kriptografi klasik untuk pembelajaran.

Kedua masalah ini saling terkait karena apa yang kita sebut Teorema Cukur Occam . Ini pada dasarnya menyatakan bahwa jika kita memiliki prosedur untuk menemukan hipotesis terkecil dari kelas yang diberikan yang konsisten dengan sampel yang dilabeli oleh hipotesis dari kelas yang sama, maka kita dapat PAC belajar kelas itu. Jadi, mengingat hasil kekerasan RSA, kami berharap bahwa menemukan DFA konsisten terkecil akan sulit secara umum!

Untuk menambahkan hasil belajar yang positif, Angluin menunjukkan bahwa Anda dapat mempelajari DFA jika Anda bisa membuat contoh sendiri, tetapi membutuhkan kekuatan tambahan untuk dapat bertanya, "Apakah hipotesis saya saat ini benar?" Ini juga merupakan makalah mani dalam pembelajaran.

Untuk menjawab pertanyaan Anda yang lain, ini semua memang terkait dengan kompleksitas Kolmogorov, karena masalah pembelajaran menjadi lebih mudah ketika representasi kanonik dari target DFA memiliki kompleksitas yang rendah.

Saya menjawab aspek terkait pembelajaran dari pertanyaan itu.

Masalah ini tampaknya disebut "pembelajaran DFA" dalam literatur.

Emas [Gol78] menunjukkan bahwa NP-complete untuk memutuskan, mengingat k ∈ℕ dan dua set terbatas P dan N string, apakah ada deterministic finite-state automaton (DFA) dengan paling banyak k state yang menerima setiap string dalam P dan tidak ada string dalam N . Makalah [PH01] tampaknya membahas masalah yang berkaitan dengan motivasi ini (mungkin ada lebih banyak; ini baru muncul ketika saya mencoba menemukan makalah yang relevan dengan Google).

Referensi

[Gol78] E Mark Gold. Kompleksitas identifikasi otomat dari data yang diberikan. Informasi dan Kontrol , 37 (3): 302–320, Juni 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh dan Vasant Honavar. Belajar DFA dari contoh sederhana. Machine Learning , 44 (1–2): 9–35, Juli 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/ ~ honavar/Papers/parekh- dfa.pdf

Sepanjang diskusi ini, telah diasumsikan bahwa menemukan ekspresi reguler minimal sama dengan menemukan FSM minimal mengenali bahasa, tetapi ini adalah dua hal yang berbeda. Jika saya ingat dengan benar, DFA dapat diminimalkan dalam waktu polinomial, sedangkan menemukan ekspresi reguler minimal yang mewakili bahasa reguler yang diberikan adalah PSPACE-hard. Yang terakhir adalah salah satu hasil yang berasal dari cerita rakyat Teori Automata, tetapi bukti tidak dapat ditemukan di mana pun. Saya pikir itu dinyatakan sebagai latihan dalam buku Papadimitrou.

Lihat juga posting stack overflow ini. Buku yang Anda cari tampaknya adalah Pengantar Teori Komputasi oleh Michael Sipser.

Anda mengajukan beberapa pertanyaan berbeda, jadi ajukan satu per satu:

Is finding a minimal Finite State Machine for a language L NP-complete?

Bukan itu. Posting Stack Overflow membahas algoritma naif n ^ 2 untuk mengurangi FSM ke ukuran minimalnya. (Bekerja mundur dari keadaan berhenti, gabungkan keadaan yang "identik" dalam arti yang tepat.)

Ternyata (saya tidak mengikuti tautan), ada algoritma n log n untuk melakukan ini.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

Saat Anda mengucapkannya, set pelatihan Anda menjelaskan bahasa yang terbatas . Bahasa yang terbatas memetakan secara trivial ke FSM - buat serangkaian negara linear yang berakhir dengan status berhenti untuk setiap string dalam bahasa Anda, tidak diperlukan perulangan. Kemudian, jalankan algoritma minimalisasi FSM pada mesin yang dihasilkan.

Is this a good way to build a classifier?

Saya tidak akan mengatakannya. Meminimalkan FSM tidak mengubah kekuatan diskriminatifnya - itulah intinya. FSM minimal menerima set string persis seperti FSM non-minimal yang setara.

Secara umum, ekspresi reguler tidak cocok untuk mengklasifikasikan data novel. Untuk setiap set pelatihan terbatas, Anda akan mendapatkan RE / FSM yang hanya cocok dengan contoh-contoh positif dalam set itu, tanpa kemampuan untuk menggeneralisasi ke data baru. Saya belum pernah melihat pendekatan yang mencoba menemukan bahasa reguler tak terbatas yang cocok dengan beberapa corpus pelatihan.

Untuk pembelajaran mesin, Anda akan mencari sesuatu seperti classifier Bayes yang naif, pohon keputusan, jaringan saraf, atau sesuatu yang lebih eksotis. Inteligensi Buatan Russell dan Norvig : Suatu Pendekatan Modern adalah tempat yang baik untuk menemukan gambaran teknik pembelajaran mesin (dan banyak lagi, lebih banyak lagi.)