Matrix norm based-solution methods and machine learning: Stochastic games and their applications

Matris norm tabanlı çözüm yöntemleri ve makine öğrenmesi: Stokastik oyunlar ve uygulamaları

PDF İndir

Tez No: 911413
Yazar: MURAT ÖZKAYA
Danışmanlar: DOÇ. DR. BURHANEDDİN İZGİ
Tez Türü: Doktora
Konular: Matematik, Mathematics
Anahtar Kelimeler: Belirtilmemiş.
Yıl: 2024
Dil: İngilizce
Üniversite: İstanbul Teknik Üniversitesi
Enstitü: Lisansüstü Eğitim Enstitüsü
Ana Bilim Dalı: Matematik Mühendisliği Ana Bilim Dalı
Bilim Dalı: Matematik Mühendisliği Bilim Dalı
Sayfa Sayısı: 128

Özet

Bu tezde matris oyunları, stokastik oyunlar, Markov oyunları ve bimatris oyunlar gibi çeşitli dinamik oyun türlerini ele aldık. İlk olarak, sıfır toplamlı olmayan bimatris oyunları inceledik. Bu oyun türünün çözümleri, literatürde genellikle çeşitli teoremler kullanılarak denge noktalarının bulunması ya da verilen bimatris oyununun iki farklı matris oyununa dekompoze edilmesi ile elde edilmektedir. Bu tez kapsamında ise İzgi ve Özkaya tarafından 2019 yılında literatüre kazandırılan matris norm (MN) metodunu bimatris oyunlarda kullanmak üzere geliştirmeyi hedefledik. Bu doğrultuda ilk olarak bimatris oyunların iki farklı matris oyununa ayrıştırılarak çözülmesi yaklaşımını benimseyerek bu oyunları için bir notasyon geliştirdik. Daha sonra geliştirdiğimiz notasyonu kullanarak, ilgili matris oyununun oyun değeri için o oyunun oyun değerini de içeren, 1 ve $\infty$ normuna bağlı alt ve üst sınırlar sunduk ve ispatlarını \cite{mn} nolu çalışmadaki kanıtları esas alarak ifade ettik. Ardından, sınırlardaki oyun değerinden kurtulmak üzere bu sınırları geliştirerek sınırları sadece 1 ve $\infty$ normuna bağlı olacak şekilde revize ettik. Elde ettiğimiz bu aralıktan seçilen geçici oyun değerinin kullanılmasıyla strateji kümesinin maksimum ve minimum elemanları için sırasıyla alt ve üst sınırlar veren bir teorem sunduk. Maksimum ve minimum eleman arasındaki ilişkiyi gösteren ve birinin bilinmesi durumunda diğeri için sınırlar elde etmeyi sağlayan farklı bir teorem ifade ettik. Daha sonra, oyun değeri için sunduğumuz sınırları geliştiren ve farklı matris norm türleri kullanılarak oyun değeri için aralık veren yeni sınırları sunduk. Strateji kümesinin maksimum ve minimum elemanlarının kullanılması ile birlik oyun değeri için elde edilen sınırların çok daha iyi bir hale getirilmesini sağlayan farklı bir teorem ifade ettik ve ispatladık. Ayrıca bu teorem sunulan yöntemin iteratif olarak kullanılmasına olanak sunmuştur. Bu verilen teoremler tez kapsamında sunulan yöntemin matris norm metodundan ayrıştırılmasını ve daha iyi sınırlar elde edilmesi sağlamıştır. Bütün bu teoremlerin sunulması ile birlikte genişletilmiş matris norm yöntemini sunmuş olduk. Genişletilmiş matris norm yönteminin nasıl kullanılacağına ilişkin adımları içeren bir diagram sunarak yöntemi özetledik. Bunlara ek olarak hem matris norm yöntemi hem de genişletilmiş matris norm yöntemi için geçerli olacak şekilde ilgili yöntemlerin yakınsamalarını inceleyerek, teoremler sunduk. Sunmuş olduğumuz yönteme ilişkin ve bimatris oyunların gerçek hayat problemlerine uygulanışını gösteren çeşitli örnekler verdik. Bu kapsamda, ilk olarak cinsiyetler savaşı (Battle of Sexes) adı verilen klasik bir oyunu hem matris norm yöntemi ile hem de genişletilmiş matris norm yöntemi ile çözdük ve bu yöntemlerin sonuç üzerindeki etkilerini ortaya koyduk. Ardından, Taş-Kağıt-Makas oyununu ele alarak matris norm tabanlı bu yöntemlerin yakınsamalarını numerik olarak inceledik ve sonuçlarını görselleştirerek sunduk. Ayrıca bimatris oyunların gerçek hayat problemlerine uygulanışını küresel bir sağlık sorunu haline gelen Covid-19 pandemisi üzerinden yaptık. Bu örnekte, Türkiye, Güney Kore ve İtalya olmak üzere seçtiğimiz üç farklı ülkenin Covid-19 pandemisinin ilk dalgasındaki karantina uygulamalarını esas alarak oyunu modelledik. İlk dalgayı, Başlangıç-Yayılım-Bitiş şeklinde üç farklı aşamaya ayırdık ve her bir ülkenin her bir aşamadaki davranışını modelleyen oyunlar sunarak denge noktaları hesapladık. Bunlara ek olarak, bireylerin pandemi sürecinde tekrarlı davranışlar sergilemesi durumunda enfekte olma durumlarını incelemek üzere tekrarlı bimatris oyunlar kullarank farklı bir şekilde modelledik ve çözümlerini sunduk. Bunun sonucunda, Türkiye, Güney Kore ve İtalya'nın pandemi boyunca karantinadan nasıl faydalandıklarını gösterdik. Tezin ikinci bölümünde ise bir önceki bölümde sunulan genişletilmiş matris norm metodunun büyük boyutlu matris oyunlarının çözülmesinde kullanılırken ortaya çıkan strateji kümesinin elemanlarının dağıtılması sorununu ele aldık. Matris norm tabanlı yöntemler $2\times2$ ve $3\times3$ boyutlu matris oyunları icin gerek oyun değerinin elde edilmesi gerekse uygun strateji kümesinin oluşturulması acısından rahatlıkla kullanılabilirken, oyun boyutu büyüdükçe strateji kümesinin elemanlarının bulunması ve uygun şekilde dağıtılması zorlaşabilmektedir. Bu zorluğu ortadan kaldırmak amacıyla genişletilmiş matris norm metodu yapay zeka ile desteklenerek strateji kümesinin elemanlarının optimal şekilde dağıtılması ve strateji kümesinin en uygun şekilde oluşturulması hedeflenmiştir. Bunun doğal bir sonucu olarak da büyük boyutu oyunların oyun değerleri daha iyi tahmin edilebilir bir hale gelmiştir. Bu doğrultuda ilk olarak $5\times5$, $10\times10$ ve $50\times50$ boyutlarına sahip, miktarları 500-500000 arasında değişen, getir matrislerini, genişletilmiş matris norm metodu ile elde edilen sınır değerlerini ve gerçek çözüme ilişkin değerleri içeren çeşitli veri kümeleri oluşturulmuştur. Oluşturulan veri kümelerinin \%80'nini geliştirilecek olan yapay sinir ağını eğitmek ve kalan \%20'si ise test amacıyla kullanılmıştır. Ardından, strateji kümesinin elemanlarını ve dağılımları kestirmek üzere bir yapay sinir ağı modeli sunulmuştur. Geliştirilen bu yapay sinir ağı, getiri matrisini ve genişletilmiş matris norm metodu ile elde edilen $p_{max}$ ve $p_{min}$ sınır değerleri ve oyunun getiri matrisini ve yaklaşık oyun değerini girdi olarak alarak strateji kümesinin eksik elemanları tahmin edip, uygun sıralamada sunacak şekilde tasarlanmıştır. Daha sonra ise yapay sinir ağları yardımı ile elde edilen bu strateji kümesi kullanılarak yaklaşık oyun değeri hesaplanmış ve gerçek oyun değeri ile karşılaştırılmıştır. Elde edilen sonuçlar incelendiğinde $5\times5$ boyutlu matris oyunları için hata miktarı \%4.9, $10\times10$ boyutlu oyunlar için \%5.5 ve $50\times50$ oyunlar için \%9.9 olarak hesaplanmıştır. Hatalara ilişkin elde edilen sonuç görselleştirilerek daha açık bir şekilde sunulmuştur. Üçüncü bölümde stokastik matris oyunları ve bu oyunların literatürde en çok kabul gören çözüm yöntemi olan Shapley iterasyonunu ele alınmıştır. Bu kapsamda incelenen stokastik matris oyunlarının analitik çözümlerinin oyunun matris boyutu $2\times2$ iken bile kuadratik denklem çözümünü gerektireceği tespit edilmiştir. Bu nedenle büyük boyutlu stokastik matris içeren oyunları çözümleri için numerik yöntemlerin kullanılması gerekmektedir. Literatürde ise bu tür oyunların numerik çözümlerinin yapılabilmesini sağlayan en bilinen yöntemin Shapley iterasyonu olduğu görülmüştür. Bu çözüm yöntemi oyuna herhangi bir başlangıç değeri vererek iterasyonu başlatıp, oluşan matris oyununu geleneksel yöntemler kullanarak analitik olarak çözmeyi esas almaktadır. Hassasiyet değeri yüksek çözümler elde edilmesini gerektiren oyunlar için ise bu yöntem kullanıldığında iterasyon sayısı ile istenen hassasiyet değerine bağlı olarak artmaktadır. Bu nedenle ilk olarak bu iterasyon miktarının azaltılmasını sağlayabilecek ve Shapley iterasyonu ile genişletilmiş matris norm metodu iki farklı şekilde birleştirilerek hibrit yöntemlerin elde edilmesi hedeflenmiştir. Bu doğrultuda, Shapley iterasyonu genişletilmiş matris norm yönteminin ilk çıktısını kullanacak şekilde bir araya getirilerek zayıf hibrit Shapley iterasyonu elde edilmiştir. Daha sonra Shapley iterasyonu genişletilmiş matris norm yönteminin iteratif versiyonu ile birleştirilip güçlü hibrit Shapley iterasyonu oluşturulmuştur ve sunulan bu hibrit yöntemlerin ispatları detaylı bir şekilde yapılmıştır. Sunulan hibrit yöntemleri nasıl kullanılacağı açıklayan detaylı bir algoritma sunulmuştur. Bu yöntemlerin hibrit olması nedeniyle, yani ara adımlar Shapley iterasyonunun dahil olması sebebiyle analitik çözüme ihtiyaç duymasından dolayı tamamen genişletilmiş matris norm metodunu temel alan yeni iki farklı iteratif yöntem sunulmuştur. Bu yöntemlerden biri genişletilmiş matris norm metodunu direkt olarak kullanırken diğeri bu yöntemi iteratif olarak kullanmaktadır. Bu yöntemleri sunulması ile birlikte stokastik matris oyunlarının çözümü için kullanılabilecek ve analitik çözümün elde edilmesini gerektirmeyecek alternatif iki metot kazandırılmıştır. Daha sonra bu yöntemlerin uygulanışlarını göstermek amacıyla iki farklı örnek incelenmiştir. İlk örnek $2\times2$ boyutlu stokastik getiri matrisine sahipken diğeri $3\times3$ boyutlu stokastik getiri matrisine sahiptir. Geliştirilen dört yöntemin sonuçları Shapley iterasyonu ile elde edilen sonuçlar kullanarak $10^{-3}$ tolerans seviyesinde karşılaştırılmıştır. Güçlü hibrit Shapley iterasyonunun $2\times2$ oyun için yaklaşık \%0.3'lük hata miktarıyla, sunulan diğer yöntemlerden çok daha iyi performans gösterdiği gözlemlenirken zayıf hibrit Shapley iterasyon yaklaşık \%0.4, iteratif genişletişmiş matris norm iterasyonu \%1, genişletilmiş matris norm iterasyonu \%1.4 hata miktarı ile güçlü hibrit Shapley iterasyonunu performans sıralamasında takip etmektedir. $3\times3$ boyutlu stokastik getiri matrisine sahip oyun üzerinde bu yöntemler uyguladığında ilk örnekteki performans sıralamasının değişmediği görülmektedir. Öte yandan, sunulan yöntemlerin performanslarının daha detaylı ve daha büyük oyunlar üzerinden test edilebilmesi için $5\times5$ ve $10\times10$ boyutlu stokastik matris oyunları oluşturulmuştur. Oyun boyutu büyüdükçe performans sıralamasının korumasına rağmen güçlü hibrit Shapley iterasyonunun diğer yöntemlere karşı daha fazla üstünlük kurduğunu sonucuna ulaşılmıştır. Fakat kurulan bu üstünlüğe rağmen görece olarak en zayıf performansı veren yöntem olan genişletilmiş matris norm iterasyonunun hata miktarı $10\times10$ boyutlu oyun için bile \%0.5-\%1.6 arasında değişmektedir. Elde edilen tüm performans kıyaslamaları sonuçlarının daha açık bir şekilde görülebilmesi için sonuçlar görselleştirerek sunulmuştur. Dördüncü bölümde ise Markov ödül oyunları ve bu oyunların çözüm yöntemleri detaylı bir şekilde ele alınmıştır. Markov ödül oyunları literatürde genel olarak değer iterasyonu, politika iterasyonu veya dinamik programlama gibi yöntemler kullanılarak çözülmektedir. Bu çözüm yöntemlerinde, oyundaki her bir durum ve aksiyon ayrı ayrı değerlendirildiği diğer bir deyişle durum-aksiyon tabanlı olarak yapıldığı gözlenmiştir. Bu nedenle çözüm süreçlerinde sürekli olarak güncelleme ile yeniden hesaplama yapılmasını gerektiği görülmüş ve bu durumun özellikle değer ve politika iterasyonu yöntemleri için daha öne çıktığı tespit edilmiştir. Dinamik programlama yönteminde de benzer bir durum söz konusu olmasına rağmen bu yöntem farklı problemler için farklı sistemler oluşturulmasını gerektirdiği için bir daha farklı bir kullanım dezavantajı oluşturmaktadır. Bu gibi durumlar göz önüne aldığında literatürde Markov ödül oyunlarının, ilgili aşamanın bütün durumlarını ve aksiyonları tek seferde değerlendiren ve gerekli hesaplamaları bütünsel olarak yapmaya imkan sağlayan bir yöntemin olmaması göze çarpmaktadır. Bu nedenle bu çalışmada matris normları tabanlı holistik yani bütünsel bir yaklaşım sağlayan, aşama-aksiyonları bir arada değerlendirmeye yarayan alternatif bir yöntem sunulmuştur. Geliştirilen matris norm tabanlı holistik yöntem ilk olarak oyunun karar ağacının özel bir yaklaşımla her bir aşama için getiri matrisine dönüştürülmesi işlemi ile başlamaktadır. Daha sonra literatürde hareketli matris olarak bilinen bir matris türü kullanılarak oyunun geçiş matrisi ve oyun ağacından elde edilen getiri matrisi birleştirilerek ilgili aşamanın tüm durumları için ilgili ağırlıklandırılmış ödüllerden oluşan bir matris oluşturulmaktadır. Ardından hareketli matrisin her bir sütununun $\infty$-normu kullanılarak ve uygun işlem aşamaları takip edilerek farklı bir matris elde edilmektedir. Oluşturulan bu matris kullanılarak bir aşamanın tüm durumları için stratejileri ilgili sütunlardaki sıfırlar ile temsil eden, yani optimal stratejileri sunan bir matris elde edilmektedir. Oyunun bir önceki aşamasındaki ödüllerin güncellenebilmesi için $1$-normunu içeren bir prosedür kullanılarak, oyunun ödülleri güncellenmekte ve bu durum ilk aşamaya kadar geriye doğru takip edilerek toplam ödül hesaplanabilmektedir. Bu yöntem sayesinde, tüm oyun holistik bir şekilde çözülebilmektedir. Sunulan matris norm tabanlı holistik yöntemin uygulanışı hem çözüm diyagramı şeklinde hem de algoritmik bir şekilde sunulmuştur. Daha sonra 2-aşama ve 2-aksiyon içeren bir Markov ödül oyunu çözüm diyagramı kullanarak çözülmüştür. Buna ek olarak, 3-aşama ve 3-aksiyon içeren farklı bir oyun algoritma kullanılarak detaylı bir şekilde çözülmüştür. Bunlara ek olarak, geliştirilen bu yöntem ile elde edilen getiri matrisini ve oyununun için verilen geçiş matrisini girdi olarak alan ve optimal stratejileri tahmin edip çıktı olarak veren bir evrişimli yapay sinir ağı geliştirilmiştir. Bu yapay sinir ağını eğitmek için 3000 ve 5000 adet 3-aşamalı ve 3-aksiyonlu Markov ödül oyunlarından oluşan iki farklı veri kümesi oluşturulmuştur. Bu veri kümelerinin \%80'nini yapay sinir ağını eğitim, \%20'sini ise yapay sinir ağını test etmek için kullanılmıştır. 3000 oyun kullanılarak eğitilen yapay sinir ağının hata miktarı yaklaşık olarak \%3, 5000 oyun kullanılarak eğitilen yapay sinir ağının hata miktarı yaklaşık olarak \%2.8 olarak elde edilmiş ve ilgili sonuçlar görselleştirilmiştir. Bunun sonucunda hem sunulan yöntem kullanılarak hem de bu sürece yapay sinir ağları dahil ederek daha hızlı sonuçlar elde etmeyi başarılmıştır. Son bölümde ise tez boyunca sunulan tüm araştırmalara yönelik sonuçları sunulmuştur.

Özet (Çeviri)

In this thesis, we comprehensively consider dynamic games including bimatrix games, stochastic games and Markov games. First of all, we develop the matrix norm (MN) method for non-zero sum bimatrix games and comprehensively present the proofs of the extended matrix norm (EMN) method that is extended version of the MN method. These developments provide an improvement for the game value obtained by the matrix norm method. Moreover, a refinement theorem for the boundaries offers more squeezed boundaries for the game value and the theorem also makes the extended matrix norm method suitable for iterative usage. In addition to these, we express some preliminary results associated with the convergence of the matrix norm methods. As an illustration for the implementation of the EMN method, we present some comprehensive applications on different games and also demonstrate the convergence of the method numerically. Additionally, we demonstrate the utilization of the bimatrix games on real-life problems by modeling the risk of infection during Covid-19 and analyze three different country for different stages of first wave of Covid-19 pandemic. We also used repeated bimatrix game to model the people's behavior in a repetitive scenario during the pandemic. Secondly, we consider to eleminate the challenging part of the matrix norm method, which is the usage of the method for the games having more than three strategies in strategy set, by utilizing artifical intelligence. Therefore, we present a new machine learning-driven concept to solve large-scale zero-sum matrix games by using the relations revealed from the offline extended matrix norm method. The proposed neural network architecture take the boundaries produced by the EMN method and the payoff matrix as inputs and provides an estimation for the game value with properly distributed strategy set. The neural network is trained over different games with various sizes up to $50 \times 50$. The results show that the neural network can obtain the game values with a relative error less 10\% at maximum for even $50\times50$ sized matrix games and even less for smaller sized matrix games. Thirdly, we investigate stochastic matrix games and their solution methods. We focus on the most common approach, that is Shapley iteration, for solving these games. We begin with boosting Shapley iteration by integrating the extended matrix norm method into the solution process in two different form, weak and strong. Thus, we aim to decrease the necessary number of iterations for Shapley iteration. However, these hybrid methods and original Shapley iteration requires analytic solution in the process so that we introduce two different analytic-solution free methods in order to eliminate this requirement. These numerical methods are establihed on the extended matrix norm method and its iterative form. After the introduction of these methods, we compare the performance of the proposed methods with Shapley iteration. The results demonstrate that the strong and weak hybrid Shapley iteration works as good as Shapley iteration and some time the the strong hybrid Shapley iteration outperforms all the methods. We also investigate the ranking between these method by using them on relatively larger stochastic matrix games. Fourthly, we consider a single-agent stochastic games, which are also known as Markov reward games. We especially focus on Markov reward games in form of decision tree. We proposed an alternative and holistic matrix norm-based solution method which is distinguished from the existing methods such as value iteration, policy iteration and dynamic programming due to its approach to the solution process. The matrix norm-based method considers all actions and the corresponding stage at once in contrast to the well-known methods that are state and action based methods. The proposed method includes a special transformation of the decision tree into a payoff matrix, the moving matrix concept, $1$-norm and $\infty$- norm. The moving matrix is one of the crucial component of the method since it helps to evaluate the effects of all actions on the stage at once which renders the method holistic. We present a comprehensive solution diagram and an algorithm of the application of the proposed method. We demonstrate the implementation of the method on different games with different state and action sets. In addition to this, we propose a convolutional neural network architecture, that uses the payoff matrix obtained by decision tree transformation and transition matrix as inputs, for solving Markov rewards games. We achieve to compute optimal strategies for the games with relative error less than \%3.

Benzer Tezler

Tez No
713812
Machine learning based augmentation of medical microwave imaging
Medikal mikrodalga görüntülemenin makine öğrenmesiyle iyileştirilmesi
MERVE KAPLAN ŞAFAK
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik Mühendisliği İstanbul Teknik Üniversitesi
Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ÇAYÖREN
Tez No
540743
Improved extreme learning machines and applications
Geliştirilmiş aşırı öğrenme makineleri ve uygulamaları
MOHANAD ABD SHEHAB AL KARAWI
Doktora
İngilizce
2018
Elektrik ve Elektronik Mühendisliği Yıldız Teknik Üniversitesi
Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NİHAN KAHRAMAN
Tez No
335888
ARM tabanlı gömülü sistemlerde kulak tanıma sisteminin gerçeklenmesi
Realizing of ear recognition system with arm based on embedded system
ÜMİT KAÇAR
Yüksek Lisans
Türkçe
2013
Elektrik ve Elektronik Mühendisliği İstanbul Teknik Üniversitesi
Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. MÜRVET KIRCI
Tez No
143102
H∞ model eşleme probleminin lineer matris eşitsizlikleri yaklaşımı ile çözümü
The solution of the H∞ model matching problem via linear matrix inequalities
MURAT AKIN
Doktora
Türkçe
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol İstanbul Teknik Üniversitesi
Kontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. LEYLA GÖREN
Tez No
470034
Parallel direct and hybrid methods based on row block partitioning for solving sparse linear systems
Seyrek doğrusal sistemleri çözmek için satır blok bölümlemeye dayalı paralel direkt ve hibrit metotlar
FAHREDDİN ŞÜKRÜ TORUN
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol İhsan Doğramacı Bilkent Üniversitesi
Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
DOÇ. DR. MURAT MANGUOĞLU

Geri Dön