Pruning algorithms for partially observable Markov decision processes
Kısmi gözlemlenebilir Markov karar süreçleri için budama algoritmaları
- Tez No: 489520
- Danışmanlar: PROF. DR. MÜBECCEL DEMİREKLER
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 140
Özet
Durum, eylem ve gözlem uzayının ayrık olduğu kısmi gözlemlenebilir Markov karar süreçlerinde değer fonksiyonunu parçalı doğrusal bir fonksiyon olarak göstermek mümkündür. Kesin değer yineleme algoritması, bu değer fonksiyonunu ararken her adımda üssel sayıda lineer fonksiyon yaratmaktadır. Bu fonksiyonların önemli bir kısmını değer fonksiyonunun değerini hiç değiştirmeden elemek mümkündür. Bu budama prosedürü lineer programlamanın kullanılması sayesinde mümkün olmaktadır. Bu çalışma ilk olarak budama prosedürünün geometrik bir çerçevesini vermektedir. Bu çalışmada gösterilmektedir ki, lineer programlama iterasyonları, budama probleminin vektör uzayı gösteriminde farklı dışbükey alanların seçimine denk gelmektedir. Buna ek olarak, budama problemine cebirsel bir çerçeve de sunulmuştur. Bu çerçeve lineer programların inşa edilmesi ve kullanılması üzerine kurulmaktadır. Problemin daha küçük boyutlu lineer programlar kullanılarak nasıl çözülebileceği ve lineer programların iterasyonlarının ne anlama geldiği anlatılmıştır. Problemin geometrik ve cebirsel çerçevesi arasında ayrıca bir ilişki de kurulmuştur. Kesin değer yineleme algoritmasının her adımında vektör sayısındaki üssel artışın nedeni verili olan vektör kümeleri üzerinde yapılan çapraz toplama işlemidir. Bu işlem sonucunda yeni bir vektör kümesi oluşmaktadır. Bilinmektedir ki, yeni oluşan setteki toplanan vektörlerden herhangi birinin elenebilir olduğunu görmek için çapraz toplama işlemine giren toplanan vektörlerin destek kümelerinin kesişimine bakmak yeterlidir. Elinizdeki çalışma, verili olan geometrik ve cebirsel çerçeveyi çapraz toplama operasyonunun özelliklerini incelemek üzere kullanmaktadır. Bu çalışmada iki yeni budama algoritması önerilmektedir. Bunlardan ilki olan FastCone verili herhangi bir vektör seti için kullanılabilir. Algoritmanın herhangi bir anında verili olan bir temiz vektör seti için, seçilmiş olan kirli vektörün içine düştüğü dışbükey alan hızlı bir şekilde bulunmaktadır. Eğer bulunan çözüm, seçilmiş olan kirli vektörü elemek için yeterli değilse bu işlem için yararlı olabilecek temiz vektörler bulunmaya çalışılmaktadır. İkinci algoritmanın ismi Cross-Sum Pruning with Multiple Objective Functions olarak belirlenmiştir. Bu algoritma ile amaçlanan herhangi bir simpleks adımında aktif olan vektörlerin destek kümeleriyle kesişimi boş küme olan vektörleri belirlemektir. Bu operasyonun işlevi şöyle özetlenebilir. Eğer farklı iki kümeden alınan iki vektörün destek kümelerinin kesişimi boş küme ise, bu iki vektörü içeren bütün sıralı çiftlerin elenmesi mümkün hale gelmektedir. Bu iki vektörün destek kümelerinin kesişiminin boş küme olduğunu anlamak için ise simpleks tablosundaki bir sırada işaret kontrolu yapmak yeterli olmaktadır. Algoritma performanslarını gösterebilmek için önerilen algoritmalar, konvansiyonel algoritmalar ve onların revize edilmiş versiyonları ile analitik ve deneysel olarak kıyaslanmıştır.
Özet (Çeviri)
It is possible to represent the value function in partially observable Markov decision processes as a piecewise linear function if the state, action, and observation space is discrete. Exact value iteration algorithm searches for this value function by creating an exponential number of linear functions at each step, many of which can be pruned without changing the value of the value function. The pruning procedure is made possible by the use of linear programming. This study first gives a geometric framework of the pruning procedure. It shows that the linear programming iterations refer to the selection of different convex regions in the vector space representation of the pruning problem. We also put forward an algebraic framework, which is the utilization and maintenance of linear programs. It shows how the problem can be decomposed into small sized LPs and what the LP iterations refer to. While stating these two theoretical frameworks, their relations have also been exploited. The exponential increase in the number of vectors in any step of the exact value iteration algorithm is due to an operation called the cross-sum addition of a set of vectors. This operation results in a new set of vectors. It is known that for any of the summand vectors in this new set to be non-dominated, the addend vectors entering the cross-sum addition should have intersecting support sets. The given geometric and algebraic framework has further been extended to exploit this particular property of the cross-sum operation. Two novel pruning algorithms have been offered in this study. First algorithm, called FastCone, can be used for pruning any given set of vectors. For a given set of clean vectors at any step, the algorithm hastily searches for the convex region that a dirty vector is in and tries to find a clean vector if only the given set of clean vectors is not sufficient to make the decision about this dirty vector. The second algorithm is called Cross-Sum Pruning with Multiple Objective Functions, where the aim is to find the vectors that have non-intersecting support sets with the current active vectors in each simplex iteration. This approach is useful because when two vectors from two different sets with non-intersecting support sets are detected, it is possible to delete all ordered pairs containing these two vectors. And this amounts to a simple sign check of the coefficients of a row of the simplex tableau. To show the algorithms' performance, both algorithms have been compared to the conventional algorithms and their revised versions both analytically and experimentally.
Benzer Tezler
- Protocols for stochastic shortest path problems with dynamic learning
Başlık çevirisi yok
VURAL AKSAKALLI
Doktora
İngilizce
2007
Eğitim ve ÖğretimJohns Hopkins UniversityEğitimde Ölçme ve Değerlendirme Ana Bilim Dalı
PROF. DONNİELL E. FİSHKİND
PROF. CAREY E. PRİEBE
- Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar
New methods and algorithms for solving the resource-constrained project scheduling problem
İHSAN UĞUR
- Covolutional neural networks based on non-euclidean operators
Öklidce mensup olmayan operatörler bazında konvolüsyonel sinir ağları
DIAA HISHAM JAMIL BADAWI
Yüksek Lisans
İngilizce
2018
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
Prof. AHMET ENİS ÇETİN
- Development of graphical code-based algorithms for the detection of abnormalities in mammogram ımages
Mamogram görüntülerinde anormalliklerin tespiti için grafik kod tabanlı algoritmaların geliştirilmesi
IMAN M. HAMADAMIN HAMADAMIN
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik MühendisliğiFırat ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HASAN GÜLER
- AO* and Penalty Based Algorithms for the Canadian Traveler Problem
Kanadalı Gezgin Problemi İçin AO* ve Ceza Tabanlı Algoritmalar
ÖMER FURKAN ŞAHİN
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Şehir ÜniversitesiEndüstri ve Sistemler Mühendisliği Ana Bilim Dalı
DOÇ. DR. VURAL AKSAKALLI
