Natural Language Processing (NLP)

Disusun Oleh:Divi Deswanti Sardy(09111002007)Mutia Aldina Arafah(09111002011)Maulidi Pranata SB(09111002021)Lacuba Maharani(09111002043)Aditya Rubinurwan (09111402008)

Teknik InformatikaFakultas Ilmu KomputerUniversitas Sriwijaya2014

1. Parsing1.1 Pengertian ParsingParsing adalah satu proses menganalisa suatu kumpulan kata dengan memisahkan kata tersebut dan menentukan struktur sintaksis dari tiap kata tersebut. Gramatika yang dipakai juga sangat berkaitan dengan proses parsing apa yang digunakan. Pada Bottom-Up Parsing gramatika yang dipakai akan lebih banyak bercabang ke arah simbol nun-terminal. Hal lain yang juga berkaitan erat dengan proses parsing adalah kamus atau leksikon yang digunakan. Dalam leksikon disimpan daftar kata yang dapat dikenali sebagai simbol terminal dalam grammar dan informasi yang diperlukan untuk tiap kata tersebut untuk proses parsing yang bersangkutan.Menurut Klas Burn terdapat dua model parsing yaitu :1. Keyword based parsing adalah model parsing yang sederhana dan efektif dalam mengurai teks input. Keyword based parsing tidak melibatkan pengetahuan sintak. Dalam praktek keyword based parsing bisa berjalan baik dengan sederhana (dalam pengertian sintaksisnya memiliki sedikit arti) dan input umum (dalam domain tetentu) tetapi memiliki masalah pada input yang lebih rumit dan tidak umum.2. Grammar based parsing adalah cara parsing yang lebih kompleks dimana dalam parsing ini melibatkan pengetahuan sintaksis. Secara teori memiliki tingkat keakuratan lebih tinggi dalam memahami dan mengerti arti dari input yang diberikan, namun demikian pada grammar based parsing memiliki kendala dalam performa atau kinerjanya karena diperlukan komputasi atau perhituangan serta kata-kata dan struktur kalimat yang diberikan harus dimengerti. Dalam aplikasinya, grammar based parsing memiliki potensi yang sangat tinggi dalam memahami input dengan baik tetapi sangat sulit dalam desain.Dari pendekatan dalam mengenali struktur suatu kalimat, proses parsing dapat dibagi menjadi dua bagian besar yaitu Top Down parsing dan Bottom Up parsing.,masing-masing memiliki kelebihan dan kekurangannya sendiri. Top-down parsing tidak dapat menangani grammar dengan left-recursion, sedangkan bottom-up parsing tidak dapat menangani grammar dengan empty production. Karena itu metode parsing yang terbaik ialah yang dapat menggabungkan kedua cara ini.Top Down parser memulai pemeriksaan dari simbol awal s dan mencoba untuk mencari bentuk simbol terminal berikutnya yang sesuai dengan jenis kata dari kalimat masukan. Cara sebaliknya diterapkan untuk Bottom Up parser yaitu mencari simbol simbol terminal menuju karah pembentukan simbol awal s.

1.1.1 Top Down ParsingTop down parsing adalah langkah dalam membentuk/membangun sebuah parse tree berdasarkan input dimulai dari root dan membuat nodes untuk parse tree secara preorder(depth first).Bentuk umum dari top down parsing adalah recursive descent parsing. Sebuah recursive descent parsing adalah top down parsing technique yang melaksanakan serangkaian prosedur rekursif untuk memproses input, yang melibatkan backtracking (berarti pemindaian input berulang-ulang). Backtracking memakan waktu dan karena itu, tidak efisien. Itu sebabnya kasus khusus dari parsing top down dikembangkan, disebut predictive parsing, di mana tidak ada backtracking diperlukan. Sebuah dilema dapat terjadi jika ada left recursion grammar. Bahkan dengan backtracking, Anda dapat menemukan parser untuk pergi ke infinite loop.Metode top-down mampu menangani grammar dengan empty production (misalnya d 0) namun tidak dapat menangani grammar dengan left recursion (misalnya np np conj np).Top-down parser bekerja dengan cara menguraikan sebuah kalimat mulai dari constituent yang terbesar yaitu sampai menjadi constituent yang terkecil. Hal ini dilakukan terus-menerus sampai semua komponen yang dihasilkan ialah constituent terkecil dalam kalimat, yaitu kata. Sebagai contoh, dengan menggunakan contoh grammar di atas, dapat dilakukan proses top-down parsing untuk kalimat The dog chased the cat yang ditunjukkan pada gambar 1. Dari gambar ini terlihat bahwa top-down parser menelusuri setiap node pada parse tree secara pre-orderBeberapa metode parsing yang bekerja secara top- down ialah: Top-down parser biasa Recursive-descent parser Transition-network parser Chart parser

Gambar 1. Cara kerja Top-down paserContoh Kasus :Top-down parser dapat diimplementasi- kan dengan berbagai bahasa pemrograman, namun akan lebih baik jika digunakan declarative language seperti Prolog atau LISP. Hal ini disebabkan oleh karena pada dasarnya proses parsing ialah proses searching yang dilakukan secara rekursif dan backtracking, dimana proses ini sudah tersedia secara otomatis dalam Bahasa Prolog. Dengan demikian parser yang ditulis dalam Prolog atau bahasa deklaratif lainnya akan menjadi jauh lebih sederhana daripada parser yang dibuat dalam bahasa procedural biasanya seperti Pascal, C dan sebagainya.

Program 1 menunjukkan implementasi top- down parser biasa dalam bahasa Prolog.Program 1 Simple Top-Down Parser1.DOMAINS2. list = symbol*3.PREDICATES4. rule(symbol,list)5. word(symbol,symbol)6. parse(symbol,list,list)7. parse_list(list,list,list)8.9.CLAUSES10. % rules11. rule(s,[np,vp]).12. rule(np,[d,n]).13. rule(vp,[v]).14. rule(vp,[v,np]).15. rule(d,[]).16.17. % lexicon18. word(d,the).19. word(d,a).20. word(n,dog).21. word(n,dogs).22. word(n,cat).23. word(n,cats).24. word(v,chase).25. word(v,chases).26. word(v,barked).27.28. % parse(C,S1,S)29. % periksa apakah S1 dimulai dengan constituent C30. % S ialah sisa kalimat setelah C dikeluarkan dari S131. parse(C,[Word|S],S) :-32. word(C,Word).% jika C ialah terminal (kata), stop33. parse(C,S1,S) :-34. rule(C,Cs), % jika C ialah nonter-minal, expand35. parse_list(Cs,S1,S).36.37. % parse_list([C|Cs],S1,S)38. % periksa apakah S1 dimulai dengan constituent berkategori39. % C diikuti oleh Cs40. % S ialah sisa kalimat setelah C dan Cs dikeluarkan41. % dari S142. parse_list([C|Cs],S1,S) :-43. parse(C,S1,S2),44. parse_list(Cs,S2,S).45. parse_list([],S,S).

Predikat parse berfungsi untuk melakukan proses parsing terhadap sebuah constituent tunggal (misalnya s, np dan sebagainya), sedangkan parse_list berfungsi untuk melakukan proses parsing terhadap sekumpulan constituent, misalnya [np,vp], [d,n] dan sebagainya. Parser akan dipanggil dengan query parse(s,X,[]), dimana s berarti kalimat dan X ialah input kalimat yang berbentuk list dari symbol. Sebagai contoh, untuk melakukan parsing terhadap kalimat "The dog chases the cat", maka query yang diberikan pada external goal Turbo Prolog ialah sebagai berikut:

?- parse(s,[the,dog,chases,the,cat],[])

dan Prolog akan memberikan jawaban YES karena kalimat tersebut sesuai dengan grammar yang ditunjukkan pada baris 11-15 oleh predikat rule.

1.1.2 Bottom Up ParsingBottom up parsing adalah sebuah langkah parsing menggunakan langkah shift-reduce parsing. Shift reduce parsing bekerja berdasarkan namanya, Shift dan Reduce sehingga setiap kali stack memegang simbol-simbol yang tidak dapat dikurangi lagi, kita menggeser masukan lain, dan ketika itu cocok, kita mengurangi. Bottom-up parser bekerja dengan cara mengambil satu demi satu kata dari kalimat yang diberikan, untuk dirangkaikan menjadi constituent yang lebih besar. Hal ini dilakukan terus-menerus sampai constituent yang terbentuk ialah sentence atau kalimat. Dengan demikian metode bottom-up bekerja dengan cara yang terbalik dari top-down. Metode bottom-up dapat menangani left recursion namun tidak dapat menangani empty production.

Cara kerja bottom-up parser ditunjukkan pada gambar 2.

Gambar 2. Cara kerja bottom-up parserMetode parsing yang bekerja secara bottom-up antara lain ialah bottom-up parser biasa dan shift-reduce parser. 1.1.3 Gabungan Top-down Parsing dan Bottom-up parsingParsing dapat dilakukan secara top-down maupun bottom-up, masing-masing memiliki kelebihan dan kekurangannya sendiri. Top-down parsing tidak dapat menangani grammar dengan left-recursion, sedangkan bottom-up parsing tidak dapat menangani grammar dengan empty production. Karena itu metode parsing yang terbaik ialah yang dapat menggabungkan kedua cara ini.Baik top-down parsing mapun bottom-up parsing memiliki kekurangan dan kelebihannya masing-masing. Metode top-down mampu menangani grammar dengan empty production (misalnya d 0) namun tidak dapat menangani grammar dengan left recursion (misalnya np np conj np). Sedangkan metode bottom-up dapat menangani left recursion namun tidak dapat menangani empty production.Dengan demikian metode parsing yang terbaik ialah metode yang dapat menggabungkan top-down dan bottom-up parsing. Ada beberapa metode yang dikembangkan yang menggabungkan kedua metode ini, di antaranya ialah left-corner parsing serta Earley's parsing.Cara kerja left-corner parsing ialah dengan mula-mula menerima sebuah kata, menentukan jenis constituent apa yang dimulai dengan jenis kata tersebut, kemudian melakukan proses parsing terhadap sisa dari constituent tersebut secara top-down. Dengan demikian proses parsing dimulai secara bottom-up dan diakhiri secara topdown. Program 3 menunjukkan implementasi left-corner parser dalam Turbo Prolog, sedangkan alur kerjanya ditunjukkan pada gambar berikut.

Cara Kerja Left-Corner Parser

Contoh Program Left-Corner Parser1: DOMAINS2: list = symbol*3:4: PREDICATES5: rule(symbol,list)6: word(symbol,symbol)7: link(symbol,symbol)8: parse(symbol,list,list)9: parse_list(list,list,list)10: complete(symbol,symbol,list,list)11:12: CLAUSES13: % rules14: rule(s,[np,vp]).15: rule(np,[d,n]).16: rule(vp,[v]).17: rule(vp,[v,np]).18: rule(d,[]).19:20: % lexicon21: word(d,the).22: word(d,a).23: word(n,dog).24: word(n,dogs).25: word(n,cat).26: word(n,cats).27: word(v,chases).28: word(v,chased).29: word(v,barked).30:31: %links32: link(np,s).33: link(d,np).34: link(d,s).35: link(v,vp).36: link(X,X).37:38: % parse(C,S1,S)39: % parse constituent dengan kategori C yang dimulai dengan40: % input string S1 dan berakhirdengan input string S41: parse(C,[Word|S2],S) :-42: word(W,Word),43: link(W,C),44: complete(W,C,S2,S).45: parse(C,S2,S) :-46: rule(W,[]),% untuk null constituent47: link(W,C),48: complete(W,C,S2,S).49:50: % parse(C1,S1,S)51: % parsing list C1 dan hasilnya di S52: parse_list([C|Cs],S1,S) :-53: parse(C,S1,S2),54: parse_list(Cs,S2,S).55: parse_list([],S,S).56:57: % complete(W,C,S1,S)58: % Memastikan bahwa W ialah subconstituent pertama dari C,59: % kemudian melakukan left-corner parsing terhadap sisa dari C60: complete(C,C,S,S).% jika C=W jangan lakukan apa-apa61: complete(W,C,S1,S) :-62: rule(P,[W|Rest]),63: parse_list(Rest,S1,S2),64: complete(P,C,S2,S).

Misalnya diberikan query :?- parse(s,[the,dog,chased,cat],[])maka parser akan memberikan jawaban YES karena kalimat tersebut sesuai dengan grammar pada baris 14-18.

1.1.4 Shift Reduce Parsing Shift-Reduce Parsing (SR Parsing) merupakan teknik parsing yang termasuk kategori bottom-up parsing yang paling umum dipakai dan paling unggul. SR parsing digunakan sebagai peruntun token dan membentuk barisan produksi untuk membangun pohon parse (parse tree). SR Parsing menggunakan tumpukan (stack) guna menjaga urutan masing-masing token. Tiap langkah dalam SR parsing terdapat dua langkah dasar : operasi shift, yang merupakan operasi penambahan kata dari kalimat masukan pada elemen teratas stack yang sering disebut sebagai top. Dan operasi reduce yang merupakan operasi pemindahan elemen top pada stack dan menggantinya dengan elemen baru yang berupa grammar rule sesuai informasi elemen yang digantikan tersebut.

Langkah dasar dari Shift Reduce Parser dapat dijabarkan sebagai berikut:1. Di awali dengan kalimat yang akan di urai per token kedalam bentuk stack1. Hingga stack kosong, lakukan: 1. Scan melalui input sampai dikenali sesuatu yang sesuai dengan RHS dari salah satu aturan produksi (ini disebut handle) 1. Terapkan aturan produksi secara terbalik, yaitu, menggantikan RHS dari aturan yang muncul dalam bentuk sentensial dengan LHS aturan (tindakan yang dikenal sebagai reduce)

Pada langkah 2.1 "shift" simbol input ke satu sisi (LHS); maka parser yang beroperasi dengan berulang kali dengan menerapkan langkah 2,1 dan 2,2 dikenal sebagai parser shift-reduce. Operasi SR parsing ini menggunakan dua stack, RHS (Right Handle Stack) yang menyimpan masukan kalimat yang telah dipecah manjadi urutan token dan disimpan dalam bentuk stack, serta LHS (Left Handle Stack) yang menampung hasil operasi (shift dan reduce) dari token pada RHS.

Gambar 3. Contoh ilustrasi SR parsing pada kalimat berbahasa Inggris

1.1.5 Shift Reduce Parsing Sebagai Pemeriksa Sintaks

Pemeriksaan sintaks pada pola yang terbentuk dari sekumpulan kata memegang kendali penting pada perangkat lunak ini. Jika sekumpulan kata yang dimasukkan dapat diterima sebagai suatu kalimat secara sintaksnya, maka hasil akhir dari perangkat lunak yang akan dibangun akan didapat, yaitu berupa visualisasi pohon penurunan yang menggambarkan struktur kalimat berdasarkan sintaksnya. Sebaliknya, jika sekumpulan kata tersebut menurut sintaks-nya tidak diterima sebagai suatu kalimat, maka hasil akhir berupa visualisasi pohon penurunan tidak dapat ditampilkan. Secara umum, dalam algoritmaShift Reduce Parsing memiliki 4 aksi sebagai berikut:1. Shift menambah satu elemen (token yang didapat dari masukan) pada stack. Aksi Shift hanya berupa pemindahan (shifting) item pertama (bagian teratas dalam tumpukan kata, dalam hal ini per-item berupa satu buah kata) dari RHS (Right Handle Stack) ke LHS (Left Handle Stack)2. Reduce menghapus elemen teratas pada LHS dan menggantinya dengan menambah satu elemen nonterminal yang sesuai.3. Accept mengenali kalimat jika hanya terdapat simbol root dan masukan kosong4. Error terjadi jika tiga poin di atas tidak mungkin dilakukan lagi, yang mengartikan bahwa masukan bukan berupa kalimat Jika LHS kosong, maka hanya aksi Shift yang dapat dilakukan. Jika RHS kosong, hanya aksi Reduce yang dilakukan. Jika RHS dan LHS tidak kosong, maka terdapat kemungkinan aksi yang terjadi adalah keduanya, dan pemroses harus memberikan satu kondisi untuk menenentukan aksi yang dilakukan. Jika Aksi yang dilakukan adalah Reduce, maka ditentukan suatu non-terminal (dalam hal ini rule) apa yang harus ditambah ke dalam LHS menggantikan item teratas dari LHS itu sendiri. Jika aksi yang dilakukan Shift, maka akan terbentuk suatu node terminal baru sebagai leaf dari pohon parsing dan akan terbentuk subtree baru. Dalam perancangan perangkat lunak ini, masukan yang berupa kumpulan kata dalam bahasa Komering Rasuan akan diartikan terlebih dahulu ke dalam bahasa Indonesia dan kemudian aturan sintaks yang digunakan adalah sintaks Bahasa Indonesia.

1.1.6 Pengaplikasian Algoritma Shift-Reduce ParserDitentukan rule sintaks sebagai berikut:E->S P|S P O|S P K|SPOKS->FN|NP->FV|V|FAdj|Adj|FNumO->FN|NK->FPrepFN->N|FN N|FN Dem|FN V|FN Adj|Adv FN|FN NumFV->V|Adv FV|FV Adv|FV N|FV AdjFAdj-> Adj|FAdj Adj|FAdj N|FAdj Adv|Adv Fadj|Fadj VFPrep->Prep FN|Prep N|FPrep FNFNum->Num N|Num Num|FNum N|FNum NumDimisalkan masukan beberapa kumpulan kata:indok mongan kan (ibu makan nasi), Dengan berdasarkan pada data kamus, didapat hasil sebagai berikut:indok;ibu;Nmongan;makan;Vkan;nasi;N Skema dasar shift-reduce pada kalimat indok mongan kan dapat dilihat pada gambar 4.

Gambar 4. Skema dasar Shift-Reduce Parsing pada kalimatindok mongan kan

Berikut digambarkan skema aksi reduce pada implementasi Shift Reduce Parser dengan penggunaan stack temporer serta modifikasi pada algoritmanya.

Gambar 5. Proses Reduce (posisi LHS) dalam Proses parsing kalimat indok mongan kan

Salah satu komponen terpenting dalam pemrosesan bahasa alami adalah pengurai (parser) struktur morfologis dari suatu kalimat. Pengurai morfologis ini mengidentifikasi dan memberi label imbuhan yang tergabung dalam sebuah morfem leksikalis sehingga membentuk satu kesatuan kelas kata yang memiliki makna tunggal ataupun bermakna ganda. Proses penguraian morfem yang terkandung dalam jenis kata tertentu dalam sebuah kalimat bahkan lebih atau pada paragraf dalam sebuah teks, mirip dengan proses penguraian dalam tata bahasa pemrograman dalam dunia komputer. Perbedaan yang mendasar pada keduanya adalah tata bahasa dalam dunia komputer merupakan tata bahasa yang bebas konteks (context free grammar), sedangkan tata bahasa pada Bahasa Indonesia merupakan tata bahasa alami yang peka terhadap konteks (context sensitive).Parser berperan dalam memeriksa urutan token-token kelas kata yang membentuk struktur sintaks kalimat-kalimat dari bahasa Indonesia.

1.1.7 LR Parser

LR parser adalah parser untuk context free grammar yang membaca input dari kiri ke kanan. LR parser cukup sulit untuk dilakukan sendiri tanpa bantuan parser generator. Berdasarkan bagaimana tabel parsing dihasilkan, parser ini mempunyai beberapa variant yaitu Simple LR Parser(SLR), Lookahead LR Parser (LALR), dan Cannonical LR Parser.

Lookahead LR parser mempunyai beberapa kelebihan dibanding dengan variant LR parser lainnya, yaitu :a. LALR parser mempunyai ukuran yang kecil. Jika pada LR parser lainnya mempunyai 1000 state, maka pada LALR Parser mempunyai state yang lebih sedikit.b. LALR parser dapat menangani banyak grammar dibanding dengan SLR parser.c. LALR menggunakan lookahead yang mana lebih spesifik karena LALR dapat menerima banyak konteks parsing. LALR akan melihat dulu konteks yang ada di depannya, sebelum menentukan konstituennya.Walaupun mempunyai kelebihan dibanding dengan variant parser lainnya, Lookahead LR parser juga mempunyai kelemahan, yaitu :a. Software engineer harus menggunakan LALR parser generator, yang mungkin tidak user friendly dan memerlukan waktu untuk proses mempelajarinya.b. cukup susah untuk mempelajari dan mengerti algoritma parsing.c. Pencarian pesan error pada parser generator relatif sulit.d. Jika terdapat error, cukup sulit menentukan letak eror, apakah pada grammar atau parser code.e. Jika terdapat eror pada parser generator, kemungkinan sangat susah untuk diperbaiki.

1.1.8 Arsitektur Lookahead LR Parser

Gambar 6. Arsitektur Lookahead LR Parser

Gambar di atas merupakan arsitektur dari LR parser yang terdiri dari input stream, stack, parse table, action table, goto table, dan output stream. Sedangkan di tengah-tengah arsitektur tersebut yang merupakan inti dari parser adalah parsing logic. Scanner digunakan sebagai tokenize input data sebelum dikirim ke parser. Pada current token, dalam hal reduce action, state selanjutnya adalah melihat ke goto table. Aksi-aksi yang dapat ditemukan pada table action adalah shift, reduce, atau accept. Jika tidak ada aksi yang didefinisikan pada state dan token tersebut, proses parsing error dan diabaikan.a. Shift n : ambil kategori yang sedang dibaca, letakkan ke dalam stack, dan ubahstate menjadi n.b. Reduce n : ambil tumpukan dari stack dan satukan dengan menggunakan aturan ke- n, letakkan kembali hasilnya ke stack, ubah state sesuai dengan goto table.c. Accept : masukan diterima dan proses parsing berhasil.

Agar lebih jelas, akan diberikan contoh sederhana terhadap penentuan struktur sebuah kalimat menggunakan algoritma Lookahead LR Parser. tabel berikut merupakan contoh penulisan tata bahasa (grammar)

Keterangan :KG : Kata gantiFV : Frase verbaKT : kata keteranganKK : kata kerjaKB : kata benda

Table parsing yang berpadanan dengan aturan tata bahasa di atas dapat dilihat pada table action, goto table, dan table produksi di bawah ini:

action table, goto table, dan production table di atas merupakan table parsing yang menentukan aksi apa yang diberikan pada sebuah token. Jika diberikan sebuah kalimat Saya Ingin Makan pizza, maka tahapan proses parsing terhadap kalimat tersebut adalah seperti tabel berikut :

Keterangan :1. Pada state 0, kata yang dibaca adalah saya yang jika diperiksa pada kamusmerupakan kataganti (KG), kemudian, aksi yang dilakukan adalah shift 2 yaituletakkan KG dan 2 ke stack, pindah ke state 2 (lihat action table).

2. Pada state 2, aksi yang dilakukan adalah R1 (Reduce 1) yaitu mengambil isistack dan mereduksinya dengan aturan R1(lihat go to table) S => saya ;kemudian, pindah ke state 1.

3. Pada state 1, kata yang dibaca adalah ingin yang merupakan kataketerangan (KT) aksi yang dilakukan adalah shift 6 yaitu letakkan KT dan6 ke stack, pindah ke state 6.

4. Pada state 6, aksi yang dilakukan adalah R4 yaitu mengambil isi stack danmereduksinya dengan aturan R4 (lihat go to table) KT=>ingin. Pindah kestate 5.

5. Pada state 5, kata yang dibaca adalah makan yang marupakan kata kerjaatau KK. Aksi yang dilakukan adalah shift 10 yaitu letakkan KK dan 10pada stack dan pindah ke state 10.

6. Pada state 10, aksi yang dilakukan adalah Reduce 5 yaitu mengambil isi stack dan mereduksinya dengan aturan R5 (lihat go to table) KK=> makan. Pindah ke state 9.

7. Pada state 9, aksi yang dilakukan adalah R3 yaitu mengambil isi stack dan mereduksinya dengan aturan R3, FV => KT KK . kemudian pindah ke state 4.

8. Pada state 4, aksi yang dilakukan adalah R2 yaitu mengambil isi stack danmereduksinya dengan aturan R2, P => FV. Pindah ke state 3.

9. Pada state 3, kata yang dibaca merupakan pizza yaitu katabenda (KB). Aksiyang dilakukan adalah shift 8. Letakkan KB dan 8 ke stack, pindah ke state 8.

9. Pada state 3, kata yang dibaca merupakan pizza yaitu katabenda (KB). Aksiyang dilakukan adalah shift 8. Letakkan KB dan 8 ke stack, pindah ke state 8.

10. Pada state 8, aksi yang dilakukan adalah R6 yaitu mengambil isi stack danmereduksinya dengan aturan R6 O => KB. Pindah ke state 7.

11. Pada state 7, kolom $ menunjukkan accept berarti kalimat diterima tatabahasa, dan menghasilkan informasi bahwa kalimat mempunyai struktur SPO.

2. Machine Translation2.1 Pengertian Machine TranslationMachine Translation (MT) bertugas secara otomatis mengkonversi satu bahasa alami ke yang lain, menjaga makna dari teks input, dan menghasilkan teks yang fasih pada bahasa output. Machine translation adalah salah satu subbidang tertua dari penelitian kecerdasan buatan, pergeseran berskala besar baru-baru ini yang terjadi terhadap teknik empiris telah membawa perbaikan yang sangat signifikan dalam kualitas terjemahan. Disisi lain, machine translation juga merupakan salah satu masalah yang paling sulitm dan merupakan bagian dari kelas masalah bahasa sehari-hari yang disebut Al-complete, karna hal ini membutuhkan berbagai macam pengetahuan yang dimiliki manusia (tata bahasa, semantik, fakta-fakta tengtang dunia yang sebenarnya, dsb.) untuk memecahkan masalah tersebut dengan baik.Proses terjemahan manusia dapat digambarkan sebagai: 1. Decoding makna teks sumber; dan 2. Re-encoding makna ini dalam bahasa target. Di balik prosedur sederhana ini terletak operasi kognitif yang kompleks. Untuk men-decode makna teks sumber secara keseluruhan, penerjemah harus menafsirkan dan menganalisis semua fitur teks, sebuah proses yang membutuhkan pengetahuan mendalam tentang tata bahasa, semantik, sintaksis, idiom, dll, dari bahasa sumber , serta budaya penuturnya. Penerjemah perlu pengetahuan yang sama dan mendalam untuk meng-encode kembli arti dalam bahasa target. Di sinilah letak tantangan dalam terjemahan mesin: bagaimana memprogram komputer yang akan "mengerti" teks seperti yang dilakukan manusia, dan yang akan "menciptakan" sebuah teks baru dalam bahasa target dimana "suara" itu seolah-olah telah ditulis oleh seorang manusia.Dalam aplikasi yang paling umum, hal tersebut masih berada di luar teknologi saat ini. Meskipun bekerja jauh lebih cepat, tidak ada program transalasi otomatis atau prosedur, yang tanpa partisipasi manusia, dapat menghasilkan output yang mendekati kualitas penerjemah manusia hasilkan. Bagaimanapun, teknologi tersebut telah menyediakan pendekatan dari teks asli, yang cukup berguna untuk dipakai dalam berbagai tujuan, termasuk membuat penggunaan terbaik dari waktu yang terbatas dan mahal dari penerjemah manusia, atau sebagai cadangan untuk kasus-kasus yang total akurasi tidak terlalu dibutuhkan.Masalah ini dapat dipecahkan dengan pendekatan dengan berbagai cara, meskipun evolusi akurasi telah membaik.Machine translation dapat menggunakan metode yang didasarkan pada aturan-aturan linguistik, hal ini berarti bahwa kata-kata akan diterjemahkan secara linguistik, yaitu kata-kata yang paling cocok (secara lisan) pada bahasa tujuan akan menggantikan kata-kata yang terdapat pada bahasa sumber.Sering dikatakan bahwa keberhasilan machine translation memerlukan penyelesaian dahulu pada masalah pemahaman bahasa alami.Umumnya, metode berbasis aturan mengurai teks, biasanya menciptakan perantara, representasi simbolis, dari teks dalam bahasa target yang dihasilkan. Menurut sifat dari representasi perantara, pendekatan digambarkan sebagai mesin terjemahan interlingual atau transfer berbasis mesin penerjemahan. Metode ini membutuhkan kamus yang luas dengan morfologi, sintaksis, dan semantik informasi, dan set besar aturan.Jika data yang diberikan cukup, biasanya program machine translation akan bekerja dengan cukup baik sehingga penutur asli dari satu bahasa dapat mengerti makna perkiraan apa yang ditulis oleh penutur asli lainnya. Kesulitan mendapatkan data yang cukup dari jenis yang tepat untuk mendukung metode tertentu. Misalnya, korpus multibahasa memerlukan data yang besar untuk metode statistik, namun hal tersebut tidak diperlukan untuk metode berbasis tata bahasa. Tapi kemudian, metode tata bahasa membutuhkan ahli bahasa terampil untuk secara hati-hati merancang tata bahasa yang mereka gunakan. Untuk menerjemahkan antara bahasa yang terkait erat, teknik yang disebut sebagai Transfer-based machine translation dapat digunakan.

2.2 Rule-based Machine TranslationParadigma rule-based machine traslation (RBMT) terdiri dari transfer-based machine translation, interlingual machine translation and dictionary-based machine translation paradigms. Jenis penerjemahan ini digunakan terutama dalam pembuatan kamus dan program tata bahasa. Tidak seperti metode lain, RBMT melibatkan informasi lebih lanjut tentang linguistik dari sumber dan target bahasa, menggunakan aturan morfologi dan sintaksis dan analisis semantik dari kedua bahasa. Pendekatan dasar melibatkan menghubungkan struktur kalimat masukan dengan struktur kalimat output menggunakan parser dan sebuah analisa untuk bahasa sumber, generator untuk bahasa target, dan leksikon transfer untuk terjemahan sebenarnya. Kekurangan terbesar RBMT adalah bahwa segala sesuatu harus dilakukan secara eksplisit: variasi ortografis dan masukan errouneous harus dibuat bagian dari analisa bahasa sumber untuk mengatasinya, dan aturan seleksi leksikal harus ditulis untuk semua contoh ambiguitas. Beradaptasi dengan domain baru dalam dirinya sendiri tidak sulit, karena tata bahasa inti adalah domain di sama, dan penyesuaian-domain tertentu terbatas pada penyesuaian pilihan leksikal.

2.2.1 Tranfer-based machine translationTransfer-base machine translation mirip dengan interlingual machine traslation, dimana hal ini menciptakan terjemahan dari representasi menengah yang menstimulasikan arti dari kalimat aslinya. Namun tidak seperti Interlingual MT, sebagian transfer-base MT tergantung pada pasangan bahasa yang terlibat dalam terjemahan.

2.2.2 Interlingual Machine TranslationInterlingual machine translation merupakan salah satu contoh dari pendekatan mesin terjemahan berbasis aturan. Dalam pendekatan ini, bahasa sumber, yaitu teks yang akan diterjemahkan, berubah menjadi bahasa interlingual, yaitu "bahasa netral" yang merupakan representasi yang independen dari bahasa apapun. Bahasa target kemudian dihasilkan dari Interligua tersebut. Salah satu keuntungan utama dari sistem ini adalah bahwa Interligua menjadi lebih berharga sebagai jumlah bahasa target itu dapat berubah menjadi meningkat. Namun, satu-satunya sistem mesin terjemahan interlingual yang telah dibuat operasional pada tingkat komersial adalah sistem Kant (Nyberg dan Mitamura, 1992), yang dirancang untuk menerjemahkan Caterpillar Teknis English (CTE) ke dalam bahasa lain.

2.2.3 Dictionary-based Machine TranslationMachine translation dapat menggunakan metode yang didasarkan pada entri kamus, yang berarti bahwa kata-kata akan diterjemahkan sebagai mereka dengan menggunakan kamus.

2.3 Statistical Machine TranslationStatistical Machine Translation mencoba untuk menghasilkan terjemahan menggunakan metode statistik berdasarkan corpora teks bilingual, seperti Canadian Hansard Corpus, catatan Inggris-Perancis parlemen Kanada dan EUROPARL, catatan Parlemen Eropa. Dimana corpora tersebut tersedia, hasil yang baik dapat dicapai menerjemahkan teks serupa, tetapi corpora tersebut masih jarang untuk beberapa pasangan bahasa. Pertama perangkat lunak terjemahan mesin statistik adalah Candide dari IBM. Google menggunakan SYSTRAN selama beberapa tahun, tapi beralih ke metode terjemahan statistik pada bulan Oktober 2007. Pada tahun 2005, Google meningkatkan kemampuan terjemahan internal dengan menggunakan sekitar 200 miliar kata dari bahan PBB untuk melatih sistem mereka; akurasi terjemahan ditingkatkan. Google Translate dan program penerjemahan statistik serupa bekerja dengan mendeteksi pola di ratusan juta dokumen yang sebelumnya telah diterjemahkan oleh manusia dan membuat dugaan cerdas berdasarkan temuan. Umumnya, dokumen lebih manusiawi-diterjemahkan tersedia dalam bahasa tertentu, semakin besar kemungkinan itu adalah bahwa terjemahan akan berkualitas baik. Baru pendekatan ke statistik mesin terjemahan seperti Metis II dan PRESEMT menggunakan ukuran corpus minimal dan bukannya fokus pada derivasi dari struktur sintaksis melalui pengenalan pola. Dengan pengembangan lebih lanjut, ini memungkinkan mesin translasi berbasis statistik untuk beroperasi off dari korpus teks monolingual. kejatuhan terbesar SMT mencakup itu menjadi tergantung pada jumlah besar teks-teks paralel, masalah dengan bahasa yang kaya morfologi (terutama dengan menerjemahkan ke dalam bahasa tersebut), dan ketidakmampuan untuk memperbaiki kesalahan tunggal.2.3.1 Contoh Arsitektur Statistical Machine TranslationMoses adalah sistem statistical machine translation yang memungkinkan anda untuk secara otomatis melatih model terjemahan untuk setiap pasangan bahasa. Yang anda butuhkan adalah kumpulan teks diterjemahkan (corpus paralel). Setelah anda memiliki model yang terlatih, algoritma pencarian yang efisien cepat menemukan terjemahan probabilitas tertinggi di antara jumlah eksponensial pilihan.Secara umum, arsitektur mesin penerjemah statistik Moses seperti pada gambar berikut :

Sumber data utama yang dipergunakan adalah parallel corpus dan monolingual corpus. Proses training terhadap parallel corpus menggunakan GIZA++ menghasilkan translation model (TM). Proses training terhadap bahasa target pada parallel corpus ditambah dengan monolingual monolingual corpus bahasa target menggunakan SRILM menghasilkan language model (LM), sedangkan PoS model (PoS-M) dihasilkan dari bahasa target pada parallel corpus yang setiap katanya sudah ditandai dengan PoS. TM, LM dan PoS-M hasil proses di atas digunakan untuk menghasilkan decoder Moses. Selanjutnya Moses digunakan sebagai mesin penerjemah untuk menghasilkan bahasa target dari input kalimat dalam bahasa sumber.

Catatan : PoS Model merupakan salah satu fitur linguistik yang dapat digunakan pada moses, fitur lain yang dapat digunakan seperti lemma, gender, proses pembentukan kata (morfem) dan lain-lain.

2.4 Example-based Machine TranslationPendekatan Example-based Machine Translation (EBMT) berbasis diusulkan oleh Makoto Nagao pada tahun 1984. EBMT didasarkan pada gagasan analogi. Dalam pendekatan ini, korpus yang digunakan adalah salah satu yang berisi teks yang telah diterjemahkan. Mengingat kalimat yang akan diterjemahkan, kalimat dari korpus ini dipilih yang mengandung komponen sub-sentensial yang sama. Hal serupa kemudian digunakan untuk menerjemahkan komponen sub-sentensial dari kalimat asli ke dalam bahasa target, dan ini frase diletakkan bersama-sama untuk membentuk sebuah terjemahan lengkap.

2.5 Hybrid Machine TranslationHybrid Machine Translation (HMT) memanfaatkan kekuatan dari metodologi Statistical Translation dan rules-based translation. Beberapa organisasi MT (seperti Asia Online, LinguaSys, Systran, dan Universitas Politeknik Valencia) mengklaim pendekatan hybrid yang menggunakan keduanya, rules dan statistik . Pendekatan berbeda dalam beberapa cara: 1. Aturan pasca-diproses oleh statistik: Terjemahan dilakukan menggunakan mesin berbasis aturan. Statistik kemudian digunakan dalam upaya untuk menyesuaikan / memperbaiki output dari mesin aturan. 2. Statistik dipandu oleh aturan: Aturan yang digunakan untuk data proses pra dalam upaya untuk lebih mengarahkan mesin statistik. Aturan juga digunakan untuk pasca-proses output statistik untuk melakukan fungsi-fungsi seperti normalisasi. Pendekatan ini memiliki lebih banyak kekuasaan, fleksibilitas dan kontrol saat menerjemahkan.