[MD-sorular] bir optimizasyon sorusu

[Ceyhun B. Akgül]

Bu dediginiz genel olarak "greedy" algoritma denilen bir yaklasim:
http://en.wikipedia.org/wiki/Greedy_algorithm
En bilinen uygulamalarindan biri de "gezgin satici" problemidir.
Optimal cozumun makul zamanda bulunamayacagi durumlarda sıklıkla basvurulan
bir yontemdir.
"Zero-norm minimization" alaninda bu yaklasim uygulanmis mi acikcasi
bilmiyorum ancak uygulanmis olmasi akla yakin, ne de olsa aklin yolu birdir.

Diger yandan oruntu tanima (pattern recognition) problemlerinde en iyi
oznitelikleri (features) secmek icin bu yaklasimin birebir aynisi olan pek
cok bulussal (heuristic) algoritmanin onerilmis oldugunu biliyorum. Bunlarin
genelde birbirlerinden farkli arama yonlerini secmede kullandiklari
yontemler (ornegin bir sonraki adimda hangi ozniteligin/ozniteliklerin
secilmesi gerektigi gibi).
Bu alanda anahtar sozcuk olarak "sequential forward feature selection"
kullanilabilir.
Daha genel minvalde "derivative-free optimization" da yararli olabilir.

ceyhun


2009/5/24 Kerem Altun <kerem.altun at gmail.com>

> Merhaba,
>
> Optimizasyonla ilgili bir kavramin ismini soracagim aslinda. J(x) diye bir
> fonksiyonumuz olsun, bunun maksimum degerini bulacagiz. x burada N boyutlu
> bir vektor, ya da J'yi N degiskenli bir fonksiyon olarak da dusunebiliriz.
> x'in elemanlari 0 ya da 1 degerini alabiliyorlar yalnizca. J(x) de cok
> karmasik bir fonksiyon, yani oyle turev falan alamiyoruz.
>
> x'in 0-normunu, "x vektorundeki 0 olmayan eleman sayisi" olarak
> tanimlayalim. Bu bir norm degildir ama yine de norm diyoruz. J'yi maksimum
> yaparken, x'in 0-normunu da minimum yapmak istiyoruz. Yani en az bileseni 1
> yaparak maksimum J'yi elde etmeye calisiyoruz.
>
> Soyle bir yontem dusunulebilir: once x'in tek bir elemanini 1 yapip tum
> olasiliklari deneyerek J'yi maksimum yapan x'i buluruz. Daha sonra x'in
> baska bir elemanini daha 1 yapariz, oyle ki J'yi en cok artirsin. Sonra bir
> elemani daha 1 yapariz, sonra bir daha vs... Bu cozum optimal degildir,
> cunku: Diyelim ilk asamada x_i'yi 1 yapinca J maksimum oldu. Sonra x_j
> elemanini da 1 yapinca J en cok artti, sonra x_k'yi da 1 yaptik J en cok
> artti, ve diyelim burada durduk. Ama belki bastan bambaska 3 elemani
> secseydik daha buyuk bir J bulabilecektik.
>
> Umarim yontemi anlatabilmisimdir. Suboptimal olsa da kolay uygulanabilecek
> bir yontem. Bu yontemin matematikteki adi nedir? Eminim bu yontemi ilk
> dusunen ben degilimdir, birileri mutlaka bir isim vermistir ama nasil
> arastiracagimi bilemiyorum. Tesekkurler.
>
> Kerem
>
>
> _______________________________________________
> MD-sorular e-posta listesi
> sorular at matematikdunyasi.org
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>



-- 
Ceyhun Burak Akgul, PhD
Marie Curie Research Fellow
Video Processing and Analysis Group
Philips Research Europe

High Tech Campus 36, WOp122 (WO 01)
5656AE Eindhoven, The Netherlands
Phone: +31 40 27 46156  Fax: +31 40 27 42630
www.tsi.enst.fr/~akgul
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20090524/33ff17bd/attachment.htm