l1-Magic ile seyrek betimleme
Son zamanlarda seyrek betimleme/kodlama konusunda çalışıyorum. Seyrek betimlemeden kasıt şu: İlgilendiğimizin vektörün büyük bir kısmı 0 olacak, yani yalnızca birkaç değeri 0'dan farklı olacak. Örneğin A∈Rm×n matrisi m boyutunda n tane sütun, vektöründen oluşsun ve her sütun veritabanındaki bir yüz resmini ifade etsin. Yani veri matrisinin sütunları örnekleri içersin. Amacımız da gözlemlediğimiz bir y∈Rm×1 vektörünün hangi kişiye ait yüz olduğunu bulmak olsun. Doğrudan y'nin değerleri üstünde çalışmak yerine şöyle bir model yazıyoruz:
Ax=y
ve x'i bulmak için şöyle bir eniyilemeye gidiyoruz: argmin‖x‖1
Yani eşitlikten taviz vermemeye çalışarak ∑i|xi| değerini mümkün olduğunca en küçüğe düşürmek istiyoruz.
Bu problemi çözdüğümüzde elde ettiğimiz x değerindeki 0'dan farklı olan değerler (özellikle yüksek olanlar) o yüze sahip kişinin başka resimlerine ait sütunlara tekabül ediyor. Eğer sonuç seyrek çıkmazsa, yani böyle ayrışan değerler gözükmezse kişinin veritabanında olmadığını söyleyebiliyoruz. Konuyla ilgili detaylı bilgiye [1]'den bakabilirsiniz.
Bahsi geçen eniyileme problemini çözmek için içbükey eniyileme (convex optimization) / doğrusal programlama kullanmak gerekiyor. Maalesef bu konuda derin bilgi sahibi değilim. Fakat yazının başlığında adı geçen l1-Magic araçkutusu buna benzer 7 adet l1 eniyileme problemini çözmek için fonksiyonlar sunuyor. Araçkutusunu indirdiğinizde örnek kodlar ve iyi hazırlanmış bir dokümantasyon içerdiğini göreceksiniz.
[1] J. Wright, A.Y. Yang, A. Ganesh, S.S. Sastry, ve Y. Ma, “Robust face recognition via sparse representation.,” IEEE transactions on pattern analysis and machine intelligence, vol. 31, Mar. 2009, pp. 210-27.
7 yorum
Seyreklik vs. deyince aklima geldi Compressed Sensing diye bir olay var, underdetermined bi dogrusal denklem sistemi icin oyle bi cozum buluyorsun ki esas datanin L1 normu minimum olsun gibi bisey.
Burada da bi ornegi var (yazilari populer kulture de hitap etsin diye cok genel kalmis): http://brainwindows.files.wordpress.com/2010/03/picture-101.png
Baktım şimdi. Yazı da burdaymış: http://brainwindows.wordpress.com/2010/03/01/compressed-sensing-in-neuroscience/
Burda da bu işin cenneti varmış: http://sites.google.com/site/igorcarron2/cs. Bir de garip (!) bir video yapmış yazar: http://www.youtube.com/watch?feature=player_embedded&v=xGeNRHl3EtU
Selam Ismail, compressed sensing hakkinda soyle guzel ve daha genel okuyucuya yonelik soyle bir makale de var, ben begenmistim:
http://www.ams.org/samplings/math-history/hap7-pixel.pdf
Bir de sanirim senin anlattigina baya benzer bir is yapmaya calisan K-SVD diye K-means'in genellestirmesi olan bir algoritma var, o da baya populer saniyorum; A ve x'i beraber bulmaya calisiyor.
Selam Cem, çok sağolasın bu yazıyı aldım yerimlerine. Özellikle içindeki "Candes and Tao found a shortcut that not only runs faster on a computer, but also explains why random sampling works so much better than regular sampling." sözü ilgimi çekti. nimcap'ın da ilgisini çekecektir :)
K-SVD için de bu sayfayı ekledim yerimlerine: http://www.cs.technion.ac.il/~ronrubin/software.html
compressed sensing veya sampling ile ilgili bütün tutoriallera burdan ulaşabilirsiniz.
http://dsp.rice.edu/cs
@abdülkadir Harika bir kaynak deposuymuş, teşekkürler.
evet ole şuana kadar kaydadeğer bütün çalışmalar burada. umarım faydalı olur...