Soal 4: Mutual Information & Relative Entropy — Sistem Rekomendasi

Pertanyaan (Level C2)

Dalam sistem rekomendasi, variabel X merepresentasikan minat pengguna terhadap kategori film, dan variabel Y merepresentasikan film yang akhirnya diklik. Jelaskan mengapa mutual information dapat digunakan dan tuliskan formulanya. Jelaskan kapan relative entropy digunakan.

Jawaban

Bagian A: Mutual Information $I(X; Y)$

1. Kenapa Pake Mutual Information?

Mutual Information (MI) ngukur seberapa banyak informasi yang dishare antara dua variabel random X dan Y. Di sistem rekomendasi:

X = Minat pengguna ke kategori film (misal: Action, Drama, Comedy)
Y = Film yang akhirnya diklik pengguna

Mutual information cocok dipake karena:

1. Ngukur Ketergantungan

MI ngukur seberapa kuat hubungan antara minat (X) sama perilaku klik (Y). MI = 0 artinya independen (minat ga ngaruh ke klik), MI > 0 artinya ada hubungan.

2. Feature Selection

MI bisa dipake buat milih fitur yang paling relevan — kategori film mana yang paling nyambung sama klik beneran pengguna.

3. Hubungan Non-linear

Beda sama korelasi Pearson yang cuma nangkep relasi linear, MI bisa nangkep hubungan non-linear antara minat sama klik.

4. Ngurangin Ketidakpastian

MI ngukur seberapa gede ketidakpastian soal klik (Y) berkurang setelah kita tau minat pengguna (X), atau sebaliknya.

2. Rumus Mutual Information

Mutual Information — Definisi Dasar (pake selisih entropy)

$$I(X; Y) = H(X) - H(X \mid Y)$$ $$I(X; Y) = H(Y) - H(Y \mid X)$$

MI itu pengurangan entropy (ketidakpastian) dari satu variabel setelah kita tau variabel yang lain.

Mutual Information — Bentuk penjumlahan langsung

$$I(X; Y) = \sum_{x \in X} \sum_{y \in Y} P(x, y) \cdot \log_2\left(\frac{P(x, y)}{P(x) \cdot P(y)}\right)$$

Dimana $P(x,y)$ = joint probability, $P(x)$ sama $P(y)$ = marginal probabilities.

Hubungan sama Entropy (konsep Venn Diagram)

$$I(X; Y) = H(X) + H(Y) - H(X, Y)$$

3. Sifat-sifat Mutual Information

Simetris: $I(X; Y) = I(Y; X)$ — informasi yang dishare sifatnya dua arah.
Non-negatif: $I(X; Y) \geq 0$ — selalu $\geq 0$, nol cuma kalo X dan Y independen.
Terbatas: $I(X; Y) \leq \min(H(X), H(Y))$ — MI ga bisa lebih gede dari entropy masing-masing variabel.

🔴 Venn Diagram hubungan entropy, conditional entropy, mutual information Dua lingkaran tumpang tindih: H(X) kiri, H(Y) kanan, overlap = I(X;Y)

4. Contoh di Sistem Rekomendasi

Misal di dataset:

$P(\text{Action}) = 0.4$, $P(\text{Drama}) = 0.35$, $P(\text{Comedy}) = 0.25$
Joint distribution $P(X, Y)$ nunjukin probabilitas pengguna dengan minat X ngeklik film Y.

Kalo $I(X; Y)$ tinggi → rekomendasi berdasarkan minat pengguna bakal efektif soalnya minat beneran nyambung sama klik.

Kalo $I(X; Y) \approx 0$ → sistem rekomendasi harus nyari fitur lain, soalnya minat ga ada hubungannya sama perilaku klik.

Bagian B: Relative Entropy (KL Divergence)

1. Definisi

Relative Entropy atau Kullback-Leibler (KL) Divergence ngukur seberapa beda dua distribusi probabilitas P dan Q. KL divergence ngukur berapa banyak informasi yang ilang kalo kita pake distribusi Q buat ngira-ngira distribusi P yang sebenernya.

KL Divergence Formula

$$D_{KL}(P \parallel Q) = \sum_{x \in X} P(x) \cdot \log_2\left(\frac{P(x)}{Q(x)}\right)$$

Dimana P = distribusi sebenernya, Q = distribusi perkiraan/model.

2. Kapan Pake Relative Entropy?

1. Evaluasi Model

Ngecek seberapa bagus model prediksi (Q) ngedeketin distribusi asli (P). Makin kecil $D_{KL}$, makin oke modelnya.

2. Training Sistem Rekomendasi

Dipake sebagai loss function: ngeminimalin KL divergence antara distribusi prediksi model sama distribusi preferensi beneran pengguna.

3. Deteksi Drift

Ngendusin perubahan perilaku pengguna: kalo $D_{KL}(P_{\text{old}} \parallel P_{\text{new}})$ gede → terjadi concept drift, model harus di-retrain.

4. A/B Testing

Ngebandingin distribusi klik antara dua grup pengguna (control vs treatment) buat ngukur efek dari perubahan UI/algoritma.

3. Sifat Penting KL Divergence

Ga simetris: $D_{KL}(P \parallel Q) \neq D_{KL}(Q \parallel P)$ — bukan metrik jarak beneran.
Non-negatif: $D_{KL}(P \parallel Q) \geq 0$ (Gibbs' inequality), sama dengan 0 cuma kalo P = Q.
Hubungan sama MI: $I(X; Y) = D_{KL}(P(X,Y) \parallel P(X) \cdot P(Y))$ — Mutual Information itu KL divergence antara joint distribution sama product of marginals.

Intinya, Mutual Information ngukur ketergantungan antara minat pengguna (X) sama klik film (Y) — cocok buat feature selection dan memahami hubungan antar variabel. Relative Entropy (KL Divergence) ngukur perbedaan antara dua distribusi — cocok buat evaluasi model, training, sama deteksi perubahan pola. Dua-duanya alat yang penting banget buat ngebangun sistem rekomendasi berbasis teori informasi.