Sparsity constrained minimax optimization with applications to game theory and machine learning
Oyun teorisi ve makine öğrenimi uygulamalarıyla seyreklik kısıtlı minimum-maksimum optimizasyon
- Tez No: 954153
- Danışmanlar: PROF. DR. MUSTAFA ÇELEBİ PINAR
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Klasik oyun teorisi yöntemleri bir oyuncu için çoğunlukla yoğun stratejiler üretmektedir; ancak bu durum, gerçek dünya uygulamalarında pratik olmayabilir. Bu tez, iki oyunculu oyunlarda seyrek stratejileri hesaplamak için minimum-maksimum eniyileme problemine seyreklik kısıtını dahil etmeyi incelemektedir. Teori ve algoritmalar, bu probleme eşdeğer olan sınırı maksimize eden artırma probleminde seyrek sınıflandırıcıların hesaplanmasında da uygulanabilmektedir. Öncelikle, seyrek optimizasyon literatüründeki en iyilik koşulları türevi olmayan fonksiyonlar için genişletildi. Ayrıca, hâlihazırda bulunan bu koşulları kapsayan ve komşu araması yapmayı sağlayan yeni bir koşul geliştirildi. Bu koşulları sağlayan en iyiliğe aday noktaları bulma amacıyla pratik açgözlü algoritmalar geliştirildi. Minimum-maksimum fonksiyonunun özellikleri kullanılarak, seyreklik kısıtlı problem ve seyreklik düzenleyicili problemin bağlantıları oluşturuldu. Literatürdeki seyreklik artırıcı cezalara bir alternatif olarak, birim simpleks üzerinde seyreklik-düzenleyicili eniyileme problemleri için yeni bir içbükey ceza önerildi. Elde edilen problem Dışbükey Farkı (DC) Algoritması'nın hızlandırılmış bir versiyonu ile çözülebilmektedir. Önerilen algoritmalar oyun teorisi için rastgele oluşturulmuş matrisler ve ikili sınıflandırma için gerçek veriler üzerinde deneysel olarak test edildi. Algoritmaların performansı, iyi bilinen düzenleme teknikleri ve problemin MILP formülasyonuyla karşılaştırıldı.
Özet (Çeviri)
Classical game-theoretic methods often yield dense strategies for a player, which might not be practical in real-world implementations. This thesis studies incorporating the sparsity constraint to the minimax optimization problem to compute sparse strategies in bimatrix games. The theory and algorithms also apply to the equivalent problem of computing sparse classifiers in the margin maximizing boosting problem. Optimality conditions in the sparse optimization literature are extended to nonsmooth functions. A new optimality condition for neighborhood search that covers the existing conditions is proposed. Practical greedy algorithms are developed to find candidate points satisfying optimality conditions. Based on the properties of the Minimax function, connections between the cardinality-constrained problem and the cardinality-regularized problem are established. A new concave penalty for cardinality-regularized optimization problems over the unit simplex is proposed, which offers an alternative to the sparsity-promoting penalties in the literature. The resulting problem is solved efficiently using a faster version of the Difference of Convex (DC) algorithm. The proposed algorithms are tested empirically on random game matrices and real data for binary classification. The performance is compared to well-known regularization techniques and the MILP formulation of the problem.
Benzer Tezler
- A Graphical interface for power system applications
Başlık çevirisi yok
CENGİZ KIRIŞTIOĞLU
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ.DR. İSMET ERKMEN
- Kuzey Batı Anadolu cisim dalgalarının spektral özellikleri
Spektral parameters of body waves in Northwest Anatolia
MEHMET ERGİN
- Vector computer implementation of fast decoupled load flow
Hızlı ayrıştırılmış yük akış modelinin vektör bilgisayarında uygulanması
SERDAR HIZIROĞLU
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ.DR. NEZİH GÜVEN
- Fault analysis based on sparse vector methods
Başlık çevirisi yok
JAMAL BADRAN
Yüksek Lisans
İngilizce
1991
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ.DR. NEZİH GÜVEN
- Nean value algorithms and neuristics for queueing networks
Kuyruk ağları için ortalama değer algoritmaları ve bulgusal yöntemleri
RIFAT AYKUT ARAPOĞLU
Yüksek Lisans
İngilizce
1993
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. GÜVEN ÇAĞLAR
