Dynamic Programming (Dinamik Programlama)

#algoritma #optimizasyon #pekistirmeli-ogrenme #nlp

Karmaşık optimizasyon problemlerini örtüşen alt problemlere bölerek ve her alt problem çözümünü önbelleğe alarak verimlice çözen algoritma tasarım paradigması.

Dinamik programlama (DP), karmaşık problemleri birbiriyle örtüşen alt problemlere ayrıştırarak çözen ve her alt problemin sonucunu bellekte saklayarak aynı hesaplamanın tekrar yapılmasını önleyen bir algoritma tasarım paradigmasıdır. Yöntem, 1950'lerde ABD'li matematikçi Richard Bellman tarafından geliştirilmiş; adındaki "programlama" sözcüğü yazılım değil, matematiksel optimizasyonu ifade etmektedir. Dinamik programlamanın iki temel koşulu vardır: optimal altyapı (optimal substructure) — bir problemin optimal çözümü, alt problemlerinin optimal çözümlerinden oluşmalıdır; örtüşen alt problemler (overlapping subproblems) — aynı alt problemler defalarca karşılaşılmalıdır. Bu iki özelliğin bir arada bulunduğu yerde DP büyük verimlilik kazanımları sağlar. Uygulamada iki ana strateji kullanılır: tabanlı yaklaşım (bottom-up/tabulation) en küçük alt problemden başlayarak büyük probleme iteratif biçimde ilerler ve sonuçları bir tabloda depolar; yukarıdan aşağıya yaklaşım (top-down/memoization) özyinelemeli çağrıları önbelleğe alarak aynı hesaplamaların tekrarını engeller. Yapay zeka ve makine öğrenimi alanında dinamik programlama hayati önem taşır. Pekiştirmeli öğrenmede (reinforcement learning) politika değerlendirme (policy evaluation) ve politika yineleme (policy iteration) algoritmaları doğrudan DP ilkelerine dayanır. Bellman denklemi — DP'nin kurucusu tarafından formüle edilmiş — modern Q-öğrenmesinin ve derin pekiştirmeli öğrenmenin (DRL) matematiksel temelini oluşturur. Markov karar süreçleri (MDP) çözümünde hem değer yineleme (value iteration) hem de politika yineleme DP formülasyonuna dayanır. Doğal dil işlemede Levenshtein (düzenleme) mesafesi iki dizi arasındaki minimum edit sayısını DP tablosuyla hesaplar; Viterbi algoritması Gizli Markov Modellerinde (HMM) en olası durum dizisini DP ile bulur; CTC (Connectionist Temporal Classification) kaybı ise ses tanıma modellerinde hizalama belirsizliğini DP ile çözer. Tokenizasyonda kullanılan BPE (Byte Pair Encoding) algoritması da DP prensiplerinden yararlanır. Klasik DP örnekleri arasında En Uzun Ortak Alt Dizi (LCS), 0/1 Sırt Çantası, Matris Zinciri Çarpımı ve Floyd-Warshall en kısa yol algoritması sayılabilir. Modern yapay zeka bağlamında Monte Carlo Ağaç Araması (MCTS) ve bazı hiperparametre optimizasyonu yaklaşımları da DP fikirlerinden faydalanır.

Dinamik Programlama Nasıl Çalışır?

Dinamik programlama, büyük bir problemi birbiriyle örtüşen daha küçük alt problemlere böler. Her alt problemin çözümü bir kez hesaplanır ve tabloya (tabulation) ya da önbelleğe (memoization) kaydedilir; aynı alt problemle tekrar karşılaşıldığında hesap yeniden yapılmak yerine saklanan sonuç doğrudan kullanılır. Bu yaklaşım, özellikle üstel karmaşıklıktaki problemleri polinom zamana indirerek büyük verimlilik sağlar. Örneğin Fibonacci sayılarını özyinelemeyle hesaplamak O(2^n) süre alırken, DP ile O(n) süreye düşer.

Bottom-Up ve Top-Down Stratejileri

Bottom-up (tabulation): En küçük alt problemden başlanır ve büyük probleme doğru iteratif biçimde ilerlenir. Tüm sonuçlar bir tabloya yazılır; özyineleme yoktur, yığın taşması riski bulunmaz ve bellek kullanımı öngörülebilirdir. Top-down (memoization): Problem yukarıdan özyinelemeli olarak çözülür; daha önce hesaplanan sonuçlar bir sözlükte (dictionary veya hash map) saklanır. Algoritmanın doğal ve okunabilir ifadesini korur; yalnızca gerçekten ihtiyaç duyulan alt problemler hesaplanır.

Pekiştirmeli Öğrenmede Dinamik Programlama

Pekiştirmeli öğrenmede (RL) dinamik programlama, hem politika değerlendirme (policy evaluation) hem de politika yineleme (policy iteration) algoritmalarının temelidir. Richard Bellman'ın formüle ettiği Bellman optimallik denklemi, bir durumun değerini gelecekteki beklenen ödüllere göre ifade eder: V(s) = max_a [R(s,a) + γ·V(s')]. Bu denklem Q-öğrenmesinin ve DQN, PPO, SAC gibi derin RL algoritmalarının matematiksel çerçevesini oluşturur. Ortam dinamikleri tam bilindiğinde (model-based RL) DP doğrudan optimal politikayı bulur; model-free durumda ise Bellman denkleminin stokastik yaklaşımları kullanılır.

Doğal Dil İşleme ve Konuşma Tanımada Kullanım

NLP'de dinamik programlama birden fazla kritik görevde rol oynar. Levenshtein (düzenleme) mesafesi, iki dizi arasındaki minimum ekleme/silme/değiştirme sayısını DP tablosuyla O(m·n) sürede hesaplar; yazım denetimi, DNA dizilimi hizalaması ve makine çevirisi değerlendirmesinde (BLEU skoru temeli) kullanılır. Viterbi algoritması, Gizli Markov Modellerinde en olası durum dizisini bulur; konuşma tanıma ve sözcük türü etiketlemede (POS tagging) temeldir. CTC kaybı, ses tanıma modellerinde etiket ile çıktı uzunluğu uyuşmazlığını DP ile çözer.

Klasik Problemler ve Modern Uygulamalar

DP'nin klasik örnekleri: En Uzun Ortak Alt Dizi (LCS) iki dizi arasındaki en uzun ortak parçayı O(m·n)'de bulur; 0/1 Sırt Çantası kısıtlı kapasitede maksimum değeri elde eder; Matris Zinciri Çarpımı toplam çarpım maliyetini minimize eder; Floyd-Warshall tüm çiftler arasındaki en kısa yolları O(n³)'te hesaplar. Modern yapay zekada Monte Carlo Ağaç Araması (MCTS), BPE tokenizasyonu ve bazı neural architecture search (NAS) yaklaşımları DP fikirlerinden faydalanır.

Sık Sorulan Sorular

  • check_circle Dinamik programlama ile böl ve yönet arasındaki fark nedir?: Böl ve yönet (divide and conquer) alt problemleri bağımsız olarak çözer; DP ise örtüşen alt problemlerin çözümlerini yeniden kullanır. Merge sort böl ve yönet örneğidir; Fibonacci veya en kısa yol DP örneğidir.
  • check_circle Her problem DP ile çözülebilir mi?: Hayır. Bir problem optimal altyapı ve örtüşen alt problemler özelliklerini taşımalıdır. Gezgin Satıcı Problemi gibi NP-hard problemler DP ile kesin çözüme kavuşsa da üstel durum uzayı nedeniyle pratikte ölçeklenmez.
  • check_circle Memoization ve tabulation hangi durumda tercih edilir?: Tabulation (bottom-up) tüm alt problemler gerektiğinde ve yığın taşması riski olduğunda tercih edilir; memoization (top-down) yalnızca gerekli alt problemleri hesapladığı için seyrek alt problem yapısında verimlidir ve kodun okunabilirliğini korur.
  • check_circle Q-öğrenmesi neden dinamik programlamaya dayanır?: Q-öğrenmesi, Bellman optimallik denklemini iteratif biçimde yaklaşarak Q-değerlerini günceller: Q(s,a) ← Q(s,a) + α[r + γ·max Q(s',a') − Q(s,a)]. Bu güncelleme kuralı doğrudan DP'nin değer yineleme (value iteration) adımından türetilmiştir.