Çok-öbekli Veri için Aradeğerlemeci Ayrışım
Transkript
Çok-öbekli Veri için Aradeğerlemeci Ayrışım
Interpolative Decomposition for Data with Multiple Clusters Çok-öbekli Veri için Aradeğerlemeci Ayrışım İsmail Arı, A. Taylan Cemgil, Lale Akarun. Boğaziçi Üniversitesi, Bilgisayar Mühendisliği 25 Nisan 2013, SİU, Girne Problem 02 “ Katkı Düşük-mertebeli yaklaşımda başarılı olan Önem Örnekleme (Importance Sampling) tabanlı Aradeğerlemeci Ayrışım yöntemi veriyi betimlemede de başarılıdır. ♠ Üstteki savın deneyle sınanması ♠ K -ortancaya dayalı yeni bir AA yöntemi ♠ Birçok farklı sınıflandırma probleminde uygulama 03 Aradeğerlemeci Ayrışım (AA) ♠ Aradeğerlemeci Ayrışım (Interpolative Decomposition) X ∈ R M ×N K ≪ N matrisini tane sütununun doğrusal bileşimi biçiminde ifade etmeyi hedefler. X ≈ CZ = X(:, J )Z 04 • J seçilen K elemanlı indis kümesi • C seçilen sütunların oluşturduğu altmatris • Z bunlara karşılık gelen aradeğerleme katsayılarını içeren matris (1) CUR Ayrışımı ♠ AA, genellikle CUR ayrışımı'nda karşımıza çıkar ♠ X ≈ CU R 05 • C seçilen sütunların oluşturduğu altmatris, C • U bağlantı matrisi, U • R seçilen satırların oluşturduğu altmatris, R = X(J = C † XR † = X( Jr , Jc ) = X(:, Jc ) † r, :) Neden Aradeğerlemeci Ayrışım? ♠ Gereksiz ve alakasız sütunları eleyerek hatayı azaltır ♠ Hafızaya (RAM) sığamayacak kadar büyük veri ile çalışmayı mümkün kılar ♠ Temel bir araçtır • Veri sıkıştırma • Öznitelik çıkarımı • Veri analizi ve yorumlanması 06 AA ve Tekil Değer Ayrışımı (TDA) ♠ Yorumlanabilirlik açısından daha iyidir • AA gerçek veriyi kullanır • TDA doğrusal bileşimleri kullanır ♠ Seyrekliği korur • Veri seyrek ise AA da seyrektir • TDA seyrekliği korumayabilir 07 İki temel soru 1. Hangi sütunlar seçilmelidir? 2. Aradeğerleme katsayıları nasıl hesaplanmalıdır? 08 Aradeğerleme katsayılarının hesabı ♠ Z aradeğerleme katsayıları altta verilen optimizasyon ile elde edilir: ′ Z = arg min D[X∥X(:, J ) Z ] ′ Z ∈R D[⋅∥⋅] 09 K×N probleme uygun olarak seçilmiş bir masraf fonksiyonudur. (2) Hangi sütunları seçmeliyiz? ♠ Problem karmaşıklığı: NP-Zor [Natarajan 1993] ♠ İçbükey eniyileme tabanlı yöntemler, QR-tabanlı yöntemler, ... ♠ Önem örneklemeye (ÖÖ) dayalı rassal AA yöntemleri Kullanılan sütun seçme kriteri: • Öklid normu [Drineas v.d. 2007, Frieze v.d. 2004] • Vektör seyreklik değeri [Lee ve Choi 2008] • Sağ tekil vektör normu 2011] 10 [Mahoney ve Drineas 2009, Lee ve Choi 2008, Halko v. d. Önem Örnekleme'ye dayalı AA 1. X 'in kısmî Tekil Değer Ayrışımı'nı hesapla ⊺ Ar Σr Br ⇐ X (3) 2. Her n = 1 → N için, o sütunun seçilme olasılığı π 'i hesapla: n 1 πn = Yani, 3. J n. vektörün A ⇐ {π n } r Σr N n=1 ⊺ ∑(Br ) 2 ni , n = 1, … , N i=1 'nin sütunlarının oluşturduğu indirgenmiş uzaydaki koordinatlarının normu çokterimlisinden rasgele seçilmiş K indis 4. C ⇐ X(:, J ), Z ⇐ C 11 r r † X (4) Çok-öbekli durum ♠ Büyük yuvarlaklar öbek merkezlerini göstermektedir. Halkalar ise ÖÖ'de eşit olasılığa sahip konumları ifade eder. ♠ Dış halkaların üstündeki noktaların seçilme olasılığı içerdekilerden yüksektir. ♠ Görüldüğü üzere yaygın yöntem çok öbekli durumu kapsamaz . Şekil 1: İki adet öbekten oluşan 2 boyutlu noktalar. 12 K -ortanca ile Aradeğerlemeci Ayrışım 1. D ⇐ N × N uzaklık matrisi; D = ∥X(:, i) − X(:, j)∥ ij 2. J ⇐ 2 Rasgele K adet sütunu ilk ortancalar olarak belirle 3. Her i = 1 → maksDöngüSayısı için 1. Her n = 1 → N için Öbek merkezini ata: c n ⇐ arg min DnJk k|k∈{1,…K } 2. Her k = 1 → K için N Ortancayı yeniden hesapla: J k ⇐ arg min n|cn =k 4. C ⇐ X(:, J ), Z kn 13 ⇐ n ∑ Dnj j . nokta k. ortancaya en yakınsa 1, değilse 0. Neden K -ortanca? ♠ Gürültü ve aykırı değerlere karşı gürbüz [Park ve Jun 2009] ♠ Belirli bir uzaklık fonksiyonun bağımlı değil, hatta uzaklıkların simetrik olması da gerekmez ♠ Hızlı ve sade ♠ Zaman ve yer karmaşıklığı: O(N 14 2 ) AA'dan CUR Ayrışımına X ≈ CU R (5) ♠ Sütunları seçmek için X üstüne AA uygula: C = X(:, Jc ) ♠ Satırları seçmek için X üstüne AA uygula: R = X(Jr , :) ⊺ ♠ Bağlantı matrisini hesapla 15 U = X(Jr , Jc ) † Deneyler & Sonuçlar Kullanılan Verikümeleri ♠ 10 MNIST Elle Yazılmış Rakamlar 2 Fonem ♠ ♠ 11 Doku http://sci2s.ugr.es/keel/dataset.php?cod=105 http://sci2s.ugr.es/keel/dataset.php?cod=72 ♠ 11 Beyaz Şarap Kalitesi http://sci2s.ugr.es/keel/dataset.php?cod=209 2 MAGIC Gamma Teleskobu ♠ http://yann.lecun.com/exdb/mnist/ http://sci2s.ugr.es/keel/dataset.php?cod=102 Açık mavi kutular verikümesindeki sınıf sayısını gösterir. 17 Karşılaştırma Yöntemi 1. Temel Bileşenler Analizi ile boyut sayısını azalt 2. İncelenen yöntem ile her sınıftan K adet örnek seç 3. En Yakın Komşu (EYK) ile sınıflama yap 4. Kesinlik (accuracy) değerini hesapla 18 MNIST Verikümesi ♠ Elle yazılmış 10 farklı rakam ♠ 20 × 20 boyutlarında ♠ 50000 eğitim örneği ♠ 10000 test örneği 19 Karşılaştırma Sonuçları ! K -ortanca en iyi sonucu vermektedir ! Yaygın olarak kullanılan ÖÖ tabanlı yöntem beklentinin aksine tamamen rasgele seçime göre daha iyi sonuç vermemektedir. Şekil 2: Tüm veri kullanıldığında elde edilen kesinlik, kırmızı çizgi ile üst sınır olarak verilmiştir. 20 Karıştırma (Confusion) Matrisleri %0 %100 (a) 10-ortanca (b) 100-ortanca (c) 1000-ortanca (d) Tümü Şekil 3: Önerdiğimiz yöntem ile 10, 100, 1000 sütun seçildiğinde veya tümü kullanıldığında elde edilen hata matrisleri 21 Önerdiğimiz Yöntemin Seçtiği Örnekler 22 Yaygın Rassal Yöntemin Seçtiği Örnekler 23 Fonem Verikümesi ♠ 5 gerçel girdi ♠ 3818 nasal ses örneği ♠ 1586 oral ses örneği ♠ 5-kat çapraz geçerleme 24 Doku Verikümesi ♠ 40 gerçel girdi ♠ 11 farklı sınıf: sıkıştırılmış dana derisi, el yapımı kağıt, pamuk kanvas, ... ♠ 4 yönelimde girdi: 0 ∘ ♠ Toplam 5500 örnek ♠ 5-kat çapraz geçerleme 25 ∘ ∘ , 45 , 90 , 135 ∘ Beyaz Şarap Kalitesi Verikümesi ♠ 11 gerçel girdi ♠ 11 farklı sınıf: 0'dan 10'a şarap kalitesi ♠ Portekiz Vinho Verde türevlerine ait toplam 4898 örnek ♠ 5-kat çapraz geçerleme 26 MAGIC Gamma Teleskobu Verikümesi ♠ 10 gerçel girdi ♠ 2 farklı sınıf ♠ Toplam 19020 örnek ♠ 5-kat çapraz geçerleme 27 Karşılaştırma Sonuçları ! Farklı verikümelerinde de K -ortanca yaygın olarak kullanılan ÖÖ tabanlı yöntemden daha iyi sonuç vermektedir. Şekil 4: K-Ortanca ve Önem Örnekleme'de her sınıf için örneklerin %20'si kullanılmıştır. 28 Vargılar & Gelecek Çalışmalar ♠ Düşük-mertebe hedefinin veriyi betimlemede de başarılı olacağı varsayımı çoköbekli veri için geçerli değildir ♠ Yapay öğrenme araştırmaları çerçevesinde AA'ya yeni bir bakış açısı üretilmiştir ♠ Öbekleme ve AA yakından ilişkilidir ♠ Günümüzde -büyük veri kullanımı ile- AA gibi sade ve başarılı yöntemler önem kazanmaktadır 29 Teşekkürler...