Görev 8

Bağlam:
İstatistiksel Makine Çevirisinde yaygın bir alt problem Kelime Sıralamasıdır. Size bir “kelime torbası” (karıştırılmış kelimeler kümesi) verilir ve dizinin olasılığını maksimize edecek şekilde özgün cümle sırasını yeniden oluşturmanız gerekir.

\(W = \{w_1, w_2, \dots, w_N\}\) \(N\) adet benzersiz kelimeden oluşan bir küme olsun.
Size, \(P(w_j | w_i)\) ile gösterilen bir Bigram Dil Modeli verilmektedir; bu model, \(w_j\) kelimesinin \(w_i\) kelimesinden sonra gelme olasılığını sağlar.
İki özel belirteç vardır: \(⟨\text{S}⟩\) (Başlangıç) ve \(⟨\text{E}⟩\) (Bitiş). Cümle \(⟨\text{S}⟩\) ile başlamalı ve \(⟨\text{E}⟩\) ile bitmelidir.

Amaç:
\(W\) kümesindeki kelimelerin bir \(\pi\) permütasyonunu bularak aşağıdaki cümle olasılığını maksimize edin:
\[
P(\pi) = P(w_{\pi_1} | ⟨\text{S}⟩) \times \left( \prod_{i=1}^{N-1} P(w_{\pi_{i+1}} | w_{\pi_i}) \right) \times P(⟨\text{E}⟩ | w_{\pi_N})
\]

A* algoritmasını uygulamak için bu maksimizasyon problemini bir minimizasyon problemine dönüştürürüz ve \(u\) kelimesinden \(v\) kelimesine geçiş maliyetini negatif log-olasılık olarak tanımlarız:
\[
C(u, v) = -\ln(P(v | u))
\]

Bölüm A: Durum Uzayının Biçimselleştirilmesi
Bu problemi A* algoritmasına uygun bir Durum Uzayı Graf araması olarak biçimselleştirin.
Özellikle aşağıdakileri tanımlayın:

    1. Bir Durum \(n\)’in yapısı.
    2. Başlangıç Durumu ve Hedef Durumu.
    3. Ardıl (Successor) Fonksiyonu (geçişlerin nasıl üretildiği) ve birikimli maliyet \(g(n)\).

[3 Puan]

Bölüm B: Sezgisel Tasarımı
Temel zorluk, arama uzayının faktöriyel yapısında (\(N!\)) yatmaktadır; bu da basit bir sezgiseli (örneğin \(h=0\)) mütevazı girdi boyutları için bile (örneğin \(N > 15\)) hesaplama açısından uygulanamaz hale getirir.
Cümleyi tamamlamak için kalan maliyeti tahmin eden önemsiz olmayan bir sezgisel \(h(n)\) tasarlayın. Sezgiseliniz aşağıdaki ölçütleri sağlamalıdır:

    1. Kabul edilebilir (admissible) olmalıdır.
    2. Monoton (tutarlı, consistent) olmalıdır.

Sezgiselinizi matematiksel olarak tanımlayın. Özellikleri henüz kanıtlamanız gerekmemektedir, ancak tasarımınızın arkasındaki mantığı açıklamanız gerekir.

İpucu: Henüz yerleştirilmemiş kelimeler kümesini göz önünde bulundurun. Geçerli bir tamamlanmış cümlede bu kelimelerin her biri tam olarak bir gelen kenara sahip olmalıdır.

[5 Puan]

Bölüm C: Teorik Kanıtlar
Bölüm B’de tanımladığınız \(h(n)\) sezgiseli kullanarak aşağıdaki özellikler için biçimsel kanıtlar verin:

    1. Kabul Edilebilirlik: \(h(n) \le h^*(n)\) olduğunu kanıtlayın; burada \(h^*(n)\), hedefe olan gerçek en düşük maliyettir.
    2. Monotonluk: \(h(n) \le cost(n, n') + h(n')\) olduğunu kanıtlayın; burada \(n'\), \(n\)’in bir ardılıdır.

[5 Puan]
[Toplam 13 Puan]