Metode bentuk normal Chomsky: implikasi kinerja pengurai CYK?

Bagan parser dapat diimplementasikan berdasarkan bentuk normal Chomsky atau langsung berdasarkan aturan produksi. Mari kita asumsikan kita memiliki parser bagan CYK yang menggunakan bentuk normal Chomsky. Binarisasi tidak didefinisikan secara unik. Apakah ini berdampak pada kinerja bagan CYK parse. Bisakah ini dieksploitasi untuk meningkatkan kinerja parser bagan CYK?

Meskipun jawaban yang jelas adalah bahwa kompleksitas mendasar tidak dapat berubah, mungkin ada algoritma yang lebih baik atau lebih buruk untuk mengurai string yang sebenarnya akan Anda temui. Namun, sepertinya masalah kurang frekuensi relatif produksi tata bahasa individu (A, B, dan C dalam pertanyaan) dan lebih merupakan masalah yang tidak terpakai, jalan buntu mengurai bahwa satu binarisasi dapat menghasilkan satu binarisasi.

Dengan sedikit pencarian saya menemukan Binarisasi yang Lebih Baik untuk Parsing CKY (Song, Ding, dan Lin, EMNLP 2008), yang tampaknya menyimpulkan secara pasti bahwa Anda dapat memilih binarisasi "lebih baik" atau "lebih buruk" dibandingkan dengan string yang sebenarnya Anda harapkan harus mengurai. Nama mereka untuk "jalan buntu" yang diharapkan dapat diminimalkan dalam praktik tampaknya adalah konstituen yang tidak lengkap , dan ada contoh yang bagus di halaman pertama.

Sebenarnya, bentuk normal Chomsky (CNF) tidak perlu menjalankan CYK, hanya binarisasi. Binarisasi sangat penting untuk menjaga kompleksitas parsing cubic, meskipun esensial hanya sehubungan dengan non-terminal (NT). Tetapi kemudian, jika Anda memiliki aturan termasuk hanya 2 non-terminal dan beberapa terminal, algoritma CYK menjadi lebih kompleks untuk diprogram dan dijelaskan.

Seperti yang Anda katakan, ada banyak cara untuk melakukan binarisasi. Beberapa akan menghasilkan tata bahasa yang lebih kecil dari yang lain. Sebagai contoh

X -> B C D
Y -> B C E 

dapat di binerkan sebagai

X -> Z D
Y -> Z E
Z -> B C

dengan demikian menghemat satu aturan dengan faktorisasi, yang dapat menghemat perhitungan, dan pada ukuran hasilnya.

Tetapi dengan aturan lain, Anda mungkin ingin memfaktorkan akhir aturan daripada awal.

Saya tidak akrab dengan karya Song, Ding, dan Lin , yang dikutip oleh jawaban Rob Simmons . Ide ini menarik tetapi saya bertanya-tanya seberapa efektif itu dapat dibandingkan dengan cara lain untuk mengoptimalkan perhitungan. Saya tidak terlalu takut.

Intinya adalah bahwa menganalisis masalah hanya berkenaan dengan algoritma CKY murni tampaknya sedikit latihan akademis tapi mahal karena ada jenis optimasi lain yang secara signifikan dapat meningkatkan penghapusan parsing jalan buntu.

CYK hanyalah salah satu variasi sederhana dalam kelompok algoritma yang semuanya dibangun pada model pemrograman dinamis yang sama, tampaknya. Saya katakan jelas karena versi paling sederhana dari algoritma ini tidak dikenal sebagai pemrograman dinamis, tetapi sebagai produk silang. Ini adalah konstruksi lama dari tata bahasa CF yang menghasilkan perpotongan bahasa tata bahasa CF F dan bahasa biasa dari FSA A., karena Bar Hillel, Perles dan Shamir (1961) , seperti dikatakan oleh Lang pada tahun 1995 .

Semua parser bagan, atau parser CF umum yang didasarkan pada pemrograman dinamis dapat dilihat sebagai varian "yang dioptimalkan" dari konstruksi lintas-produk, optimasi yang digunakan terutama untuk menghindari perhitungan parser yang tidak berguna. Tetapi masalahnya halus karena menghindari perhitungan yang tidak berguna dapat mengakibatkan duplikasi yang berguna, yang mungkin lebih buruk.

Menjadi bottom-up, algoritma CKY menghasilkan perhitungan parsial parsial yang tidak berguna yang tidak dapat diturunkan dari aksioma tata bahasa.

Algoritma seperti parser GLR (untuk menyebutkan salah satu yang lebih dikenal, meskipun versi cacat telah diterbitkan), memiliki beberapa pengetahuan top-down yang akan menghindari banyak perhitungan tidak berguna seperti itu, mungkin dengan biaya. Dan ada banyak varian lain dengan perilaku berbeda sehubungan dengan penghematan perhitungan yang tidak berguna ..

Dengan strategi optimasi ini, strategi binarisasi harus dianalisis. Apa gunanya mengoptimalkan apa yang mungkin menjadi masalah kecil, dan mengabaikan teknik yang lebih kuat.

Optimalisasi proses parsing juga terkait erat dengan "kualitas" dari struktur parse yang diperoleh, yang mewakili semua kemungkinan parse, dan sering disebut (dibagi-) parse-forest. Saya membahasnya dalam jawaban lain .

Beberapa masalah ini dibahas dalam literatur. Misalnya oleh Billot dan Lang menganalisis beberapa aspek binarisasi sehubungan dengan strategi penguraian.