Menggunakan Machine Learning untuk Pemeringkatan Dokumen
Pemeringkatan dokumen bertujuan untuk mendapatkan susunan dokumen yang sesuai dengan tingkat kerelevanannya terhadap query yang diberikan. Dokumen yang memiliki nilai relevan lebih tinggi akan diberi bobot yang lebih tinggi. Yang kita inginkan adalah, dokumen dengan bobot yang paling tinggi akan berada pada list teratas, dan seterusnya. Jadi, bagaimana kita mengukur seberapa “relevan” dokumen tersebut?
Salah satu teknik yang dapat digunakan adalah menggunakan machine learning, atau biasanya lebih sering disebut sebagai learning-to-rank. Karena kita menggunakan machine learning, maka dibutuhkan:
- Data Latih
Berisi pasangan dokumen dan query yang direpresentasikan oleh beberapa fitur. Fitur memetakan pasangan query dan dokumen menjadi nilai real. Untuk mendapatkan nilai pada fitur, kita bisa menggunakan teknik pemeringkatan pada umumnya seperti TF (Term Frequency), IDF (Inverse Document Frequency), Kombinasi dari TF dan IDF, Query Likelihood, BM25 dan lain-lain. Kemudian setiap dokumen tersebut juga harus memiliki label atau relevant judgement. Tingkat relevant judgement ada bermacam-macam dan dapat kita tentukan sendiri, misalnya terdiri dari {relevan, tidak relevan} atau {relevan, semi relevan, tidak relevan} atau bisa juga order dari relevan dokumen yang didapatkan pada sebuah retrieval system yang dianggap sebagai pseudo trends. - Data Uji
Data uji sama dengan data latih, biasanya jika kita memiliki 15 query, di mana setiap query berisi 100 dokumen, maka kita bisa membaginya ke dalam 70% untuk data latih dan 30% untuk data uji. Cara membaginya dapat berdasarkan query atau dokumen.
Sudah terdapat banyak model/algoritma yang dapat digunakan untuk mengaplikasikan learning-to-rank. Mereka dibagi ke dalam 3 pendekatan berdasarkan bagaimana algoritma mendefinisikan ruang input, ruang output, dan cara pembelajaran. Pendekatan tersebut adalah Pointwise, Pairwise, dan Listwise. Dalam artikel ini akan dijelaskan masing-masing pendekatan dan salah satu model dari masing-masing pendekatan.
Pointwise
Beberapa contoh model pemeringkatan yang menggunakan pointwise adalah MART (Gradient boosted regression tree), Random Forest, dan Linear Regression. Pada pointwise, dokumen diproses secara independen, atau satu per satu. Model pembelajarannya menggunakan vektor fitur pada dokumen untuk memprediksi derajat kerelevanan dokumen terhadap query.
Linear Regression dalam Pointwise
Karena menggunakan Linear regression, tujuan model ini adalah mencari sebuah regression line yang dapat memisahkan dan mengklasifikasikan dokumen. Salah satu caranya adalah menggunakan metode least-squares.
Pairwise
Beberapa contoh model pemeringkatan yang menggunakan pairwise adalah RankNet, RankBoost, dan LambdaMart. Pada pairwise, dokumen diproses secara berpasang-pasangan. Ruang inputnya terdiri dari pasangan dari dokumen yang direpresentasikan sebagai vektor fitur kedua dokumen tersebut, sehingga ruang outputnya adalah relative order antara dokumen yang memiliki nilai antara {+1, -1}.
RankNet dalam Pairwise
RankNet dibangun menggunakan neural network dan diusulkan oleh tim peneliti dari Microsoft. Neural network-nya memiliki hidden layer dan menggunakan backpropagation untuk meminimalkan susunan yang salah antara pasangan hasil. Proses pembelajaran pada RankNet dapat dilihat pada gambar di bawah ini:
Diberikan pasangan [A, B] pada Rᵈ dengan target probabilitas P bar, algoritma ini berusaha untuk mempelajari bahwa probabilitas A harus diberi peringkat yang lebih tinggi daripada B jika score S-nya lebih tinggi pada ground truth. Prediksi probabilitas ranking P memiliki persamaan:
Fungsi ini mentransfer output score pada neural network menjadi probabilitas menggunakan fungsi logistik dari perbedaan dua skor item. Gradient Descent digunakan sebagai fungsi optimisasi. Fungsi loss-nya menggunakan cross-entropy antara distribusi prediksi ranking yang didapatkan dari model neural network P dengan target ranking P bar.
Pada setiap iterasi, dilakukan perbaikan nilai gradient dan parameter. Seperti dilihat pada gambar di mana w* adalah parameter baru, w adalah parameter sekarang, dan juga terdapat parameter gradient-nya dan learning rate. Learning rate adalah kecepatan belajar yang semakin besar nilainya dapat menyebabkan konvergen yang lebih cepat namun rawan terhadap loncatan. Algoritma ini dijalankan terus menerus hingga mencapai titik di mana gradient bernilai 0 atau telah mencapat batas jumlah iterasi.
Listwise
Beberapa contoh model pemeringkatan yang menggunakan listwise adalah AdaRank, Coordinate Ascent, dan ListNet. Listwise memproses langsung daftar dokumen dalam satu query sebagai inputnya. Model pembelajarannya menggunakan fungsi multivariate, outputnya adalah permutasi dari daftar dokumen terhadap query.
Coordinate Ascent dalam Listwise
Coordinate Ascent dikenal juga sebagai linear feature-based model dan diusulkan oleh Metzler & Croft pada tahun 2006. Model pembelajarannya mencari nilai terbaik untuk bobot w yang dapat memetakan fitur-fitur dari pasangan query dan dokumen. Secara matematika, skor untuk sebuah dokumen d pada query q dapat dituliskan sebagai:
di mana Fi(d, q) adalah fungsi fiturnya. Teknik ini membutuhkan sebuah fungsi evaluasi E(Rw; T) yang akan digunakan sebagai fungsi objektif.
Jadi tujuan dari model ini adalah mencari bobot w yang dapat memaksimalkan fungsi E() pada keseluruhan training data T. Fungsi objective yang akan dimaksimalkan dalam proses pembelajaran bisa berupa Precision, Recall, MAP, DCG, nDCG, bpref dan lain-lain.
Implementasi
Salah satu pustaka yang dapat digunakan untuk mengimplemetasikan model-model dalam learning-to-rank adalah RankLib. Kita bisa mendapatkan dokumentasi lengkapnya di sana. RankLib bersifat open source yang dikembangkan oleh The Lemur Project dan ditulis dalam bahasa permrograman Java. The Lemur Project mengembangkan banyak software yang biasa digunakan oleh peneliti dalam bidang Perolehan Informasi dan Penambangan Text.
