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ı: 101
Ö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 novel approach for generating instance-based plausible and proximate counterfactual explanations
Örnek tabanlı makul ve yakın karşı olgusal açıklama üretmeye dayalı yeni bir yaklaşım
YAĞIZ LEVENT GÜME
Yüksek Lisans
İngilizce
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiVeri Mühendisliği ve İş Analitiği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ERKAN IŞIKLI
- Görüntü işlemede yama sıralama tabanlı yaklaşımlar
Patch ordering based approaches for image processing
ÖZDEN ÇOLAK
Doktora
Türkçe
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. ENDER METE EKŞİOĞLU
- Algorithms for sparsity constrained principal component analysis
Seyrek kısıtlı temel bileşen analizi için algoritmalar
FATİH SELİM AKTAŞ
Yüksek Lisans
İngilizce
2023
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA ÇELEBİ PINAR
- Uzun dalga kızılötesi hiperspektral görüntülerde hedef tespiti
Target detection from long-wave infrared hyperspectral images
SEFA KÜÇÜK
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik MühendisliğiHacettepe ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SENİHA ESEN YÜKSEL
- Learning to relax nonconvex quadratically constrainedquadratic programs
Dışbükey olmayan kuadratik kısıtlı kuadratik programlarıgevşetmeyi öğrenmek
MEBRURE BUKET ÖZEN
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. BURAK KOCUK