Parser Kalimat Sederhana untuk Bahasa Indonesia

Beberapa waktu lalu saya mendapat tugas kerja untuk membuat sebuah text summarizer (perangkum bacaan) menjadi sebuah kalimat sederhana. Istri saya yang lebih mendalami bidang NLP menyarankan untuk menggunakan teknik yang sederhana:

Temukan kalimat utama, dan jadikan kalimat tersebut sebagai rangkuman.

Saya setuju ide itu, selain tidak serumit jika mengunakan machine learning yang kompleks, rasanya cara itu sudah cukup cocok untuk kasus saya. Istri saya memberi tahu saya beberapa algoritma yang bisa digunakan dan sebuah peringatan bahwa bagian paling sulit adalah nanti bagaimana membuat parser kalimat (program yang dapat mengekstrak kalimat-kalimat yang menyusuk sebuah dokumen teks).

Saya buat parser ini menggunakan bahasa pemrograman Python, dengan bantuan beberapa package (re untuk regex, dsb.).

Split berdasar penanda akhir kalimat

Percobaan pertama yang saya lakukan adalah menggunakan regex untuk men-split data teks berdasarkan beberapa karakter yang biasa menjadi penanda akhir dari sebuah kalimat. Karakter pemisah yang saya gunakan awalanya aadalah tanda titik (“.”), tanda tanya (“?”), dan tanda seru (“!”) yang setelahnya terdapat sebuah spasi atau sudah di akhir dokumen.

Setelah coba dijalankan, saya menemukan beberapa fakta menarik. Pertama, seharusnya saya tidak perlu memisahkan berdasarkan tanda tanya dan tanda seru karena kedua tanda tersebut hanya muncul di kalimat langsung yang tidak perlu di split. Jadi berikutnya kita cukup split di tanda titik.

Kedua, asumsi saya menggunakan tambahan “sebuah spasi setelah karakter” ternyata benar-benar bermanfaat karena parser akhirnya tidak men-split tanda titik yang bukan akhir kalimat, misalnya 6.700 korban.

Kalimat langsung

“Roses are red. Violets are Blue,” said Hugo.

Dalam kasus saya, kalimat di dalam kalimat langsung tidak boleh dipisah. Untuk menghindari pemisahan, perlu dibuat aturan khusus (saya rasa ini bisa di-handle menggunakan regex). Ide saya sementara ini dengan membuat variabel untuk mengecek sebuah simbol pemisah ada di dalam double quote atau tidak, lalu jika tanda titik misalnya ada di antara double quote, maka kita beri “tanda” agar tidak di split.

“Tanda” agar tidak di-split

Untuk menandai sebuah simbol tidak boleh di split, saya sisipkan simbol yang unik (yang saya yakin tidak akan muncul di dokumen saya) sebelum dan setelah tanda titik. Saya gunakan simbol @#...@#.

“Roses are red@#.@# Violets are Blue,” said Hugo.

Mengatasi Singkatan

Ini adalah bagian yang juga sulit, misalnya ada kalimat:

Tadi malam saya bertemu H. Akbar M. dan drs. Rian. Kami adalah sahabat dekat dulunya.

Jika diperhatikan tanda titik setelah huruf “H” dan huruf “M”, bukanlah tanda akhir dari kalimat, begitu juga tanda titik setelah “drs”. Tanda titik yang digunakan untuk memisah kalimat adalah setelah kata “Rian”.

Awalnya saya berpikir untuk tidak mensplit tanda titik yang sebelumnya hanya satu huruf, tapi “drs” lebih dari satu huruf dan juga merupakan singkatan. Kita harus menemukan sebuah kata adalah singkatan atau bukan.

Deteksi singkatan

Pada projek ini ada dua aturan yang gunakan:

  1. Jika kata sebelum tanda titik hanya terdiri dari satu huruf, maka itu adalah singkatan. Contoh: “M.”, “H.”
  2. Jika tidak, maka cek terlebih dahulu di kamus singkatan (saya buat sendiri), jika ditemukan, maka kata tersebut singkatan. Contoh: “Prof.”, “Dr.”, “Hj.”, “dll.”, “Moch.”

Secara tidak langsung, aturan ini juga menangani singkatan panjang seperti “S.W.A.T.”. Setelah berhasil mendeteksi singkatan, dengan ide yang sama kita kasih “tanda” pada tanda titiknya, lalu split dengan fungsi regex seperti sebelumnya.

Hapus “tanda”

Setelah berhasil split kalimat, jangan lupa untuk menghilangkan simbol yang tadi kita gunakan sebagai “tanda”. Caranya bisa dengan manual seach atau dengan regex.

Program

Program bisa diakses di Google Colab berikut

Image from: https://museafrica.com

A* algorithm for puzzle

A* Algorithm in Python to solve 8 puzzle problem

My team got this as A* algorithm assignment in Artificial Intelligence class few years ago taught by Mrs. Afiahayati, Ph.D. We should create an implementation of A* algorithm (read: “A” Star) to solve 8 puzzle problem. This puzzle problem is the small version of 15 sliding puzzle game.

A* Algorithm

In my opinion A* Algorithm (read more about it here) is looks like combination of Breadth First Search (BFS) and Depth First Search (DFS) algorithm (or maybe Dijkstra’s too(?)). It’s using Heuristic scoring to estimate the step from vertex to goal so make the system may running faster, and like Dijkstra’s, it’s a complete search which always finding a best solution. Read this to get better explanation.

My team agreed to use Manhattan distance to estimate distance between the current state and the goal state (h) and count the number of step as exact cost (g).

Implementation

I wrote the code using Python. And after several hours coding I found python have a “magical” function that make easy to write 🙂 My first implementation was not using any class at all and it made the code hard to read. After I saw this implementation, I realize that code is much prettier than mine, so I rewrite my code using Node class with similar class concept from that code.

See the complete source code on Github

documentation neural network

How Do I Learn Neural Network (and Deep Learning)

First, I am nobody in this topic, please don’t hesitate to give better suggestion. This is actually just a “documentation” about my experience when I work on my undergraduate thesis in 2015. Once again, please don’t hesitate to discuss and give better suggestion about this topic, or.. correct my English if I made some mistakes 🙂

Background

Okay, before I tell you my story, I’ll tell you about my background when I started to learn neural network. I wrote this section only have one intention, to make you easy measure what you need, nothing else.

  1. I have familiarity with some of mathematical symbols, like how to read sigma symbol, derivative symbol and many others (but not every symbols).
  2. I have familiarity with basic math operation like derivative function, algebra, matrix and vector operation (but only “the basic”).
  3. I’ve never coded in python, but I’ve been using C++ around 2-3 years and I used to code  Matlab style programming language in some project before (and thanks, this knowledge is very helpful)
  4. I studied the Introduction of Artificial Intelligence at the fourth semester in college, but I won’t said I did it well 🙁

After a month googling randomly, I started to make a list what should I learn, the order of the list below it’s just the best order in my opinion. In my experience I jumped many times over the topic because at that time, I didn’t know what I didn’t know 🙁

If you want to learn about Deep Learning, lets begin with: What is Machine Learning?

Then start to learn about Neural Network

Let’s do some math, Backpropagation?

I suggest you to fully-understand this algorithm in order to give some intuitions to help you in model tuning or error handling when you start implement the neural network

  • Easy start : I watched again the neural network demistifyed, and slowly got the intuition how backpropagation work, I followed and tried the math step-by-step
  • Watch the 4th week on Coursera Introduction to Machine Learning
  • Try the example of how backpropagation works : https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/
  • Read carefully the second chapter from http://neuralnetworksanddeeplearning.com/
  • And if you start thinking they have different formula / calculation / interpretation, start to prove that you are wrong. I started to compare all the calculations to understand more

Python for machine learning?

So what is Deep Learning?

What is Convolutional Neural Network (I use CNN in my undergraduate thesis)?

Backpropagation in CNN?

I don’t know it is necessary or not, but I learned it. I think if you understand the basic of backpropagation it’s enough. But if you are curious how backpropgation through max pooling or convolution layer, it does not hurt to learn it.

And…great, It’s done, That’s all my references that I used when I did my undergraduate thesis, I hope it will be useful for someone :/ or at least for me in the future 🙂