Çok-öbekli Veri için Aradeğerlemeci Ayrışım

Transkript

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
♠ 11 Beyaz Şarap Kalitesi
2 MAGIC Gamma Teleskobu
♠
http://yann.lecun.com/exdb/mnist/
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
25
∘
∘
, 45 , 90 , 135
∘
Beyaz Şarap Kalitesi Verikümesi
♠ 11 farklı sınıf: 0'dan 10'a şarap kalitesi
♠ Portekiz Vinho Verde türevlerine ait toplam 4898 örnek
26
MAGIC Gamma Teleskobu Verikümesi
♠ 2 farklı sınıf
♠ Toplam 19020 örnek
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...

Çok-öbekli Veri için Aradeğerlemeci Ayrışım

Transkript

Benzer belgeler

İçindekiler - Sakareller

Machine learning techniques based on classification

bilgisayarcı matematikçiler