Word Embedding Bahasa Indonesia menggunakan Fasttext (tanpa Gensim)

Updated 11 Juli 2019: Fasttext released version 0.9.1

Pada artikel sebelumnya saya sempat menuliskan bagaimana menggunakan Gensim untuk me-load pre-trained model word embedding FastText. Ternyata metode tersebut “kebetulan” mudah digunakan untuk data bahasa Indonesia. Ketika kita memilih bahasa lain yang memiliki ukuran data lebih besar, menggunakan Gensim bisa jadi memunculkan masalah karena untuk me-load pre-trained model FastText, Gensim membutuhkan resource RAM yang cukup tinggi

Sebagai contoh jika kita coba me-load pre-trained model bahasa Inggris di Google Colab yang memiliki kapasitas RAM 12GB, Google Colab akan crash karena notebook kita menggunakan sumberdaya melebihi yang disediakan.

Berikut contoh program untuk me-load model bahasa Inggris menggunakan Gensim (detail sintaks program sebelumnya sudah sempat saya bahas di post sebelumnya)

# Install Gensim
!pip install --upgrade gensim

# Download dan unzip dataset
!wget https://dl.fbaipublicfiles.com/fasttext/vectors-crawl/cc.en.300.bin.gz
!gunzip cc.en.300.bin.gz
# Load model
from gensim.models.fasttext import FastText
model = FastText.load_fasttext_format('cc.en.300.bin')

Dan hasilnya, RAM kita yang 12GB itu secara perlahan akan habis digunakan. Lalu berakhir Google Colab kita akan mengalami crash dengan pesan berikut:

Untuk itu ada cara lain yang ingin saya bahas singkat di post ini bagaimana cara me-load pre-trained model Fasttext jika RAM kita terbatas

Menggunakan Fasttext Python Library

Seperti yang telah saya singgung di artikel sebelumnya, terdapat dua library yang dapat kita gunakan saat ingin menerapkan FastText di Python. Yang pertama adalah menggunakan Gensim, dan yang kedua adalah menggunakan package resmi dari FastText. Dokumentasinya dapat dibaca di halaman github ini.

Continue reading

Mengenal Google Colab

Apa itu Google Colab?

Seperti Google Drive, Google Doc, dan sebagainya, Google Colab adalah salah satu produk Google berbasis cloud yang bisa kita gunakan secara gratis. Perbedaannya adalah Google Colab dibuat khusus untuk para programmer atau researcher yang mungkin kesulitan untuk mendapatkan akses komputer dengan spek tinggi. Google Colab adalah coding environment bahasa pemrograman Python dengan format “notebook” (mirip dengan Jupyter notebook), atau dengan kata lain Google seakan meminjami kita komputer secara gratis! untuk membuat program oleh Google.

Saya sendiri beberapa kali telah menggunakan Google Colab untuk beragam keperluan dan merasakan banyak manfaatnya, beberapa manfaat yang saya rasakan:

  • Free GPU! Google Colab memudahkan kita untuk menjalankan program pada komputer dengan spek tinggi (GPU Tesla, RAM ~12GB, Disk ~300GB yang masih bisa sambung dengan Google Drive, akses internet cepat untuk download file besar) dan running dalam waktu yang lama (Google Colab mengizinkan kita untuk merunning program hingga 12 jam). Karenanya, bagi teman-teman yang ingin belajar Deep Learning tidak perlu khawatir lagi akan terhalang sulitnya mendapatkan akses komputer dengan spek tinggi.
  • Colaborate! Google Colab juga memudahkan kita berkolaborasi dengan orang lain dengan cara membagi kodingan secara online (mirip Google Doc). Kita bisa lebih mudah bereksperimen secara bersamaan, atau sekadar menggunakan fitur ini untuk mempelajari codingan orang lain yang telah rapi (karena format notebook)
  • Mudah berintegrasi! Google Colab terbilang sangat fleksibel dalam hal integrasi. Kita dapat dengan mudah menghubungkan Google Colab dengan jupyter notebook di komputer kita (local runtime), menghubungkan dengan Google Drive, atau dengan Github
  • Fleksibel! Salah satu yang saya favoritkan adalah kita bisa dengan mudah merunning deep learning program via HP! ya karena pada esensinya Google Colab hanya perlu running di browser, kita bisa mengawasi proses training (atau bahkan coding) via browser smartphone kita selama smartphone kita terhubung dengan Google Drive yang sama.

Bagimana cara menggunakannya?

Seperti Aplikasi Google pada umumnya, yang kita butuhkan adalah akun Google dan silakan ke https://colab.research.google.com/. Setelah itu kita akan disuguhkan tampilan sebagai berikut:

tampilan google colab

Untuk membuat notebook baru, cukup klik New Python 3 Notebook (atau Python 2 tergantung apa yang akan digunakan) lalu kita akan dibawa ke halaman yang mirip dengan Jupyter Notebook. Nantinya, setiap notebook yang kita buat akan disimpan di Google Drive kita.

tampilan google colab 2

Pengaturan GPU

Jika kita ingin menjalankan program Python kita menggunakan GPU (atau bahkan TPU), kita cukup perlu klik “Edit > Notebook Settings”, lalu pada bagian “Hardware Accelerator” pilih GPU.

mengatur gpu google colab

Hal-hal lain seputar Google Colab

Di bagian ini saya akan menjelaskan catatan-catatan tambahan penggunaan Colab yang tidak wajib kalian tahu, tapi siapa tahu akan bermanfaat nantinya.

Pip Package Installation

Ketika kita butuh instal python package di Colab, kita bisa melakukan instalasi menggunakan pip.

!pip install seaborn

Jika diperhatikan perintahnya sama seperti perintah instalasi pip pada umumnya, hanya saja bedanya di awali dengan tanda !. Tanda tersebut digunakan sebagai penanda bahwa perintah yang akan kita jalankan adalah command line. Kita juga bisa menggunakan tanda ! untuk perintah terminal lain seperti !wget untuk mendownload dataset, !gzip untuk mengextract file zip, !cp untuk mengcopy file, dan sebagainya.

Menghubungkan dengan Google Drive

Google Colab akan mereset notebook beserta semua temporary filenya maksimal 12 jam sekali. Karenanya akan lebih baik jika file yang akan kita gunakan atau kita hasilkan tersimpan dengan rapi di Google Drive. Kita bisa melakukan hal tersebut dengan menjalankan program di bawah

from google.colab import drive
drive.mount('/content/drive')

Jika perintah di atas dijalankan, maka kita akan diberikan URL yang akan mengantarkan kita ke halaman permohonan akses Google Drive. Jika ktia sudah mengizinkan, kita akan diberikan kode yang dapat dituliskan di kolom kecil di akhir output tersebut.

Setelah terhubung, maka akan tampak daftar file di bagian kiri Notebook

Untuk mengakses file-file tersebut, kita arahkan proses load / save ke path drive/My Drive/FOLDERTUJUAN

Mengupload file ke Colab

Alternatif lain jika tidak ingin menghubungkan Google Colab ke Google Drive adalah dengan mengupload langsung file yang diperlukan ke Colab. Colab menyediakan tempat penyimpanan file sementara yang akan direstart (dihapus) dalam rentangan waktu tertentu.

Upload file ke Google Colab dengan perintah berikut:

from google.colab import files
upload = files.upload()

Jika perintah di atas di-run akan memunculkan kotak dialog untuk mengupload file. Perintah di atas cukup praktis untuk mengupload file-file kecil (bukan dataset besar, lebih mudah diletakkan di drive)

Pengaturan tema

Bagi yang suka coding dengan “night mode”, Colab juga menyediakan pilihan untuk mengubah tema notebooknya menjadi gelap. Pengubahan tema dilakukan di “tools” > “preferences” > “site”

dark google colab

Selain itu Colab juga menyediakan beberapa “hiburan” lain untuk diatur semisal memunculkan kucing (“kitty mode”) atau anjing (“corgy mode”) di atas layar atau juga percikan api (“power level”) jika mengetik panjang. Ini semua bisa ditemukan di “tools” > “preferences” > “miscellaneous”

Catatan seputar versi sistem

Perlu dicatat, tipe GPU dan versi Cuda (software “penghubung” komputasi menggunakan GPU) bisa jadi berbeda setiap kita buka Colab. Google Colab juga tidak menjamin akan selalu menginstall package Python termutakhir. Karenanya ada beberapa hal yang perlu diingat:

  1. Ketika melatih model machine learning pastikan semua-nya disimpan. “Semua” di sini mulai dari bobot neural network, parameter, modelnya, versi package, apapun! karena bisa jadi besok pas mau di-run lagi hasilnya berubah karena ada perubahan versi sistem. Ini khususnya ketika ada unsur “random” di kode kita.
  2. Ketika install package, pastikan dilengkapi dengan nomor versinya. agar tidak terpengaruh perubahan sistem:
!pip install torch==1.5 numpy==1.17

Penutup

Saya pribadi sangat merasa terbantu hingga saat ini dengan adanya Google Colab. Saya jadi tidak perlu repot izin pinjam komputer lab atau mengusulkan pembelian komputer spek tinggi di kantor. Saya sudah menggunakan Colab untuk beberapa projek Deep Learning yang tidak terlalu besar, dan sampai saat ini kesannya positif, lumayan untuk belajar atau bahkan untuk menghasilkan model yang baik di kasus-kasus sederhana. Batasan 12 jam running juga tidak terlalu menghalangi karena dengan spek komputer yang sudah baik, proses running jadi tidak perlu selama itu kok.

Selamat mencoba! dan semoga bermanfaat!

Word Embedding Bahasa Indonesia menggunakan Fasttext (dengan Gensim)

Mengenal Word Embedding

Word embedding mudahnya adalah istilah yang digunakan untuk teknik mengubah sebuah kata menjadi sebuah vektor atau array yang terdiri dari kumpulan angka.

Ketika kita akan membuat model machine learning yang menerima input sebuah teks, tentu machine learning tidak bisa langsung menerima mentah-mentah teks yang kita miliki. Cara “tradisional” untuk membaca teks tersebut adalah sebagai berikut:

  1. Buat kamus kata dengan cara mendaftar semua kata yang ada di dataset
  2. Setiap menerima sebuah string kata, string tersebut diubah menjadi sebuah integer dengan memberinya nomor. Penomoran ini bisa ditentukan berdasarkan urutan di kamus kata yang kita miliki. Misalnya pada ilustrasi di bawah, string “Makan” menjadi angka 3, string “Lari” menjadi angka 5, dst.
  3. Angka-angka tersebut kita ubah lagi menjadi sebuah vektor (array 1 dimensi) yang memiliki panjang sepanjang banyak kata yang kita miliki di kamus. Array tersebut hanya akan bernilai 1 atau 0 (disebut one hot encoding). Nilai 1 diposisikan pada indeks yang merupakan nomor kata tersebut sedangkan elemen lainnya bernilai 0. Contohnya untuk kata “makan”, dengan banyak kosakata yang kita miliki adalah 100 kata, maka dari kata tersebut kita akan memperoleh sebuah vektor dengan panjang 100 yang berisi 0 semua kecuali pada posisi ke 3 yang bernilai 1.
Ilustrasi mengubah string menjadi one-hot encoding
Continue reading

Implementasi Greedy -Codeforces 1131B

CONTEST

Soal berjudul Draw! ini merupakan bagian dari contest  Codeforces Round #541 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek di  Official Editorial Codeforces. Soal ini termasuk dalam jenis soal implementasi greedy dengan solusi berfokus pada cara implementasi untuk mencari solusi jawaban. Meskipun berkode B, yang biasanya merupakan soal mudah pada contest Codeforces, namun soal ini cukup menantang.

SOAL

Diketahui dalam sebuah pertandingan sepak bola, panitia mencatatkan informasi skor kedua tim sebanyak beberapa kali, sesuai waktu yang telah ditentukan (momen). Informasi tersebut dicatat sebanyak $n$ kali dengan penulisan berpasangan $(a_i,b_i)$. Ini menunjukkan bahwa pada saat tertentu dalam pertandingan, skornya adalah $a_i : b_i$. Jika diketahui skor sekarang adalah $(x : y)$, maka apabila sebuah gol terjadi, skor di papan saat itu berubah menjadi $x+1 : y$ atau $x : y+1$.

Berapakah banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung?

Input

Baris input pertama terdiri dari sebuah integer $n$ $(1 \leq n \leq 10000)$  — banyaknya pencatatan yang dilakukan panitia (banyak momen).

Setiap baris dari total $n$ baris berikutnya terdiri dari integer $a_i$ dan $b_i$  $(0 \leq a_i,b_i \leq 109)$, yang menyatakan skor pertandingan pada momen tersebut (jumlah gol dari tim pertama dan gol dari tim kedua).

Semua momen diinputkan secara terurut, sehingga sekuens $x_i$ dan $y_j$ non-decreasing. Skor terakhir yang tercatat merupakan skor final dari pertandingan tersebut.

Output

Print banyak kemungkinan skor seri terjadi selama pertandingan tersebut berlangsung. Skor $(0:0)$ pada awal pertandingan juga dihitung seri.

Contoh dan pembahasan

Contoh Pertama
input $n$ dan skor tiap momen:

3
2 0
3 1
3 4

output banyak skor seri:

2

Pada momen ke-1 skor tim $a$ adalah 2 dan skor tim $b$ adalah 0. Pada momen tersebut jika dijabarkan semua skor yang mungkin terjadi sebelum pencatatan adalah $\{(0,0),(1,0),(2,0)\}$, sehingga skor seri yang pernah terjadi adalah $(0,0)$. Pada momen ke-2 skor berubah untuk tim $a$ menjadi $3$ dan tim $b$ skor menjadi $1$. Pada momen ini, skor yang mungkin terjadi adalah $\{(2,1),(3,1)\}$ dimana tim $b$ mencetak gol lebih dulu atau sebaliknya tim $a$ duluan yang mencetak gol dengan skor $\{(3,0),(3,1)\}$. Dari kedua opsi tersebut diketahui bahwa tidak ada skor seri yang mungkin terjadi. Terakhir, momen ke-3 terjadi penambahan gol untuk tim $b$ secara berturut-turut yang dibuktikan dengan tidak bertambahnya skor tim $a$ dari momen terakhir pencatatan. Maka dari itu skor yang terjadi sebelum pencatatan pada momen ini adalah $\{(3,2),(3,3),(3,4)\}$ dimana terjadi skor seri yakni $(3,3)$.

Total dari 3 momen pencatatan tersebut ada sebanyak 2 kali skor seri, seperti yang terlihat di tabel berikut.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 2 & 0 & \{(0,0)\} \\
2 & 3 & 1 & \{ \} \\
3 & 3 & 4 & \{(3,3)\}
\end{array}
$$

Contoh Kedua
input $n$ dan skor tiap momen:

3
0 0
0 0
0 0

output banyak skor seri:

1

Pada contoh ini, skor kedua tim tidak berubah/bertambah dari awal momen sampai akhir. Maka skor seri yang memungkinkan hanya 1 kali, yakni $(0,0)$ itu sendiri.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 0 & 0 & \{(0,0)\} \\
2 & 0 & 0 & \{\text{ } \} \\
3 & 0 & 0 & \{\text{ } \}
\end{array}
$$

Contoh Ketiga
input $n$ dan skor tiap momen:

1
5 4

output banyak skor seri:

5

Pada contoh ini hanya terjadi satu kali momen pencatatan dengan skor $(5,4)$. Dengan melihat minimal skor di antara kedua tim kita dapat menentukan bahwa skor seri yang mungkin terjadi adalah semua skor yang dimulai dari $0$ sampai dengan skor minimal di momen tersebut $\min{(5,4)} = 4$, sehingga ada sebanyak 5 kali skor seri seperti pada tabel di bawah ini.

$$
\begin{array}{c|lcr}
i& x_i & y_i & \text{kemungkinan skor seri} \\
\hline
1 & 5 & 4 & \{(0,0),(1,1),(2,2),(3,3),(4,4)\}
\end{array}
$$

Pembahasan

Cara menghitung banyaknya skor seri dalam suatu pertandingan dapat disederhanakan dengan mencari kemungkinan skor seri di setiap momen pencatatan. Di setiap momen pencatatan, hal yang perlu diperhatikan adalah minimal skor pada momen saat ini yakni $\min{(x_i,y_i)}$ dan maksimal skor pada momen sebelumnya yakni $\max{(x_{i-1},y_{i-1})}$. Nilai yang menjadi patokan tiap momen adalah nilai $\min{(x_i,y_i}) – \max{(x_{i-1},y_{i-1})}$ yang pada langkah-langkah di bawah ini kemudian ditulis dengan $s$. Nilai $s$ ini merupakan banyaknya skor seri yang mungkin pada tiap momen.

n = int(input())
T = 0
minSkorLast = 0
maxSkorLast = 0
for moment in range(n):
    skor = [int(item) for item in input().split(" ")]
    minSkor = min(skor[0],skor[1])
    maxSkor = max(skor[0],skor[1])
    s = minSkor-maxSkorLast+1
    if s > 0:
        if maxSkorLast != minSkorLast:
            T = T + s
        else:
            T = T + s - 1
    minSkorLast = minSkor
    maxSkorLast = maxSkor
print(T+1)

Pertama, kita akan menyimpan total banyaknya skor seri pada suatu variabel $T$ tentunya di awal inisialisasi dengan 0 (baris 2 kode python).

Perlu diingat bahwa permulaan pertandingan skor $(0,0)$ merupakan seri sehingga inisialnya kita sudah menyimpan 1 nilai seri. Untuk mempermudah, asumsi bahwa skor yang tercatat pada momen $(i-1)$ adalah seri diterapkan di perhitungan tiap momen, ditunjukkan dengan penambahan nilai $s$ dengan $1$ di awal perhitungan tiap momen (baris 9 kode python).

Kedua, jika $s$ adalah positif, maka ada perubahan skor pada momen $(i)$ sekarang dibanding dari momen $(i-1)$ sebelumnya, yang memungkinkan adanya skor seri di momen $i$ ini (baris 10 kode python).

Ketiga, jika skor yang dicatat pada momen $(i-1)$ sebelumnya merupakan skor seri, maka pada momen sekarang $(i)$ tidak perlu dihitung ulang. Sehingga penyimpanan skor seri dikurangi, yakni dengan mengkurangkan nilai $s$ dengan $1$ (baris 14 kode python). Selain itu, maka total banyaknya skor seri $T$ ditambahkan dengan nilai $s$ pada momen $(i)$ ini (baris 12 kode python). Proses ini diulangi sampai sejumlah momen pencatatan pada input atau sejumlah $n$.

Geometri – Codeforces 1100C

CONTEST

Soal berjudul NN and the Optical Illusion ini merupakan bagian dari contest  Codeforces Round #532 (Div 2). Pembahasan pada post kali ini dibuat menurut pemahaman penulis, sedangkan pembahasan official dari tim pembuat soal bisa dicek di  Official Editorial Codeforces.

Soal ini di Codeforces termasuk ke dalam tag jenis soal geometri dan binary search. Soal ini berkode C yang berarti memiliki tingkat kesulitan yang cukup mudah sampai sedang. Pada artikel ini, penulis mencoba melihat dengan pendekatan geometri dan menggunakan rumus trigonometri untuk memecahkan problem. 


Perbandingan penyusunan lingkaran menghasilkan optical illusion
RINGKASAN SOAL

NN berselancar di media sosial dan selalu melihat suatu gambar yang terdiri dari sebuah lingkaran di tengah (inner circle) dan sejumlah $n$ lingkaran di luar (outer circle). Semua outer circle berukuran sama dengan jari-jari $R$ dan bersinggungan dengan inner circle yang memiliki jari-jari $r$. Gambar di atas merupakan contoh dua buah gambar yang pernah dilihat NN.

Bantu NN untuk menghitung jari-jari outer circle $R$, jika diketahui jari-jari inner circle $r$ dan jumlah outer circle $n$.

Input

Terdiri dari satu baris dengan dua angka terpisahkan oleh spasi. Masing-masing secara berurutan adalah nilai $n$ dan $r$ dimana $(3 \leq n \leq 100, 1 \leq n \leq 100)$, yakni jumlah outer circle dan jari-jari inner circle.

Output

Terdiri dari sebuah nilai $R$ — jari-jari outer circle yang dibutuhkan untuk membentuk gambar (agar semua outer circle) bersinggungan dengan inner circle. Jawaban diterima jika nilai error absolutnya tidak melebihi 10-6

Jika jawaban NN adalah $a$, dan jawaban juri adalah $b$, maka jawaban NN diterima jika dan hanya jika $\frac{\quad \lvert a-b\rvert \quad}{\max{(a, \lvert b\rvert)}} \le 10^{-6}$

Contoh dan pembahasan

input $n$ dan $r$:

3 1

output $R$:

6.4641016

Input di atas dapat diilustrasikan pada gambar di bawah ini. Setiap titik pusat dari outer circle jika dihubungkan dapat membentuk segi-$n$ sama sisi. Dikarenakan $n$ pada contoh ini adalah 3, maka yang terbentuk adalah segi tiga sama sisi $ABC$, di mana sisinya merupakan dua kali panjang jari-jari outer circle yakni sebesar $2R$. Kemudian, dari segitiga sama sisi tersebut dapat digambar lagi sebuah segitiga sama kaki $BCD$ (warna biru) untuk mencari nilai $R$.

Dari segitiga sama kaki $BCD$ di atas dapat dicari nilai $R$ dengan menerapkan salah satu rumus trigonometri:

Rumus trigonometri:
$\sin{\angle\text{BDt}} = \frac{\text{Bt}} {\text{BD}}$

Rumus mencari R:
$\sin{\angle\text{BDt}} = \frac{\text{R}} {\text{R+r}}$
$(\text{R}*\sin{\angle\text{BDt}}) + (\text{r}*\sin{\angle\text{BDt}}) = \text{R}$
$\text{R}*(\sin{\angle\text{BDt}} – 1) = -\text{r}*\sin{\angle\text{BDt}}$
$\text{R} = \frac{-\text{r} \; * \; \sin{\angle\text{BDt}}} {\sin{\angle\text{BDt}} \;- \;\text{1}}$
$\text{atau}$
$\text{R} = \frac{\text{r} \; * \; \sin{\angle\text{BDt}}} {\text{1} \;- \;\sin{\angle\text{BDt}}}$

Besar $\angle \text{BDC}$ diperoleh dari hasil bagi sudut lingkaran yakni $\text{360}^\circ$ dengan jumlah outer circle yakni $n$. Setelah diketahui besaran sudut, maka dengan menggunakan rumus di atas dapat dihitung nilai $R$. 

Nilai R:
$\angle \text{BDC} = \frac{360^\circ}{ \text{n}}$
$\angle \text{BDt} = \frac{\angle \text{BDC}}{\text{2}}$
$\angle \text{BDt} = \frac{120^\circ} {\text{2}} = 60^\circ$ 

$\text{R} = \frac{\text{1} \; * \; \sin{\text{60}^\circ}} {\text{1} \;- \;\sin{\text{60}^\circ}}$
$\text{R} = \frac{0.8660254}{0.1339745}$
$\text{R} = \text{6.46410161514}$