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

İsmail Arı, A. Taylan Cemgil, Lale Akarun. Boğaziçi Üniversitesi

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

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.

Aradeğerlemeci Ayrışım (AA)

  • Aradeğerlemeci Ayrışım (Interpolative Decomposition) $\m{X} \in \mathbb{R}^{M \times N}$ matrisini $K \ll N$ tane sütununun doğrusal bileşimi biçiminde ifade etmeyi hedefler.
    \begin{align} \label{eq:basic_id} X \approx \color{#0689e7}C \color{green}Z = \color{#0689e7}\col{X}{J}\color{green}Z \end{align}
    • $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

CUR Ayrışımı

  • AA, genellikle CUR ayrışımı'nda karşımıza çıkar
  • $X \approx \color{#0689e7}C\color{#7030a0}U\color{#ff7e37}R$
    • $C$ seçilen sütunların oluşturduğu altmatris, $C=\col{X}{\Jcol}$
    • $U$ bağlantı matrisi, $U=C^\dagger XR^\dagger=X(\Jrow,\Jcol)^\dagger$
    • $R$ seçilen satırların oluşturduğu altmatris, $R=\row{X}{\Jrow}$

Neden Aradeğerlemeci Ayrışım?

  • Gereksiz ve alakasız sütunları eleyerek hatayı azaltır

AA ve Tekil Değer Ayrışımı (TDA)

İki temel soru

  1. Hangi sütunlar seçilmelidir?
  2. Aradeğerleme katsayıları nasıl hesaplanmalıdır?

Aradeğerleme katsayılarının hesabı

  • $\m{Z}$ aradeğerleme katsayıları altta verilen optimizasyon ile elde edilir: \begin{align} \DeclareMathOperator*{\argmin}{arg\min\ } \m{Z} = \argmin_{\m{Z}'\in \mathbb{R}^{K\times N}} \mathcal{D}\left[\m{X} \| \col{X}{J} \m{Z'}\right] \end{align} $\mathcal{D}[\cdot\|\cdot]$ probleme uygun olarak seçilmiş bir masraf fonksiyonudur.

Hangi sütunları seçmeliyiz?

  • Problem karmaşıklığı: NP-Zor [Natarajan 1993]

Önem Örnekleme'ye dayalı AA

  1. $X$'in kısmî Tekil Değer Ayrışımı'nı hesapla
    \begin{align} \color{red}\m{A}_r\color{black} \m{\Sigma}_r \color{#0689e7}\m{B}_r^\intercal\color{black} \Leftarrow X \end{align}

Çok-öbekli durum

  • Büyük yuvarlaklar öbek merkezlerini göstermektedir. Halkalar ise ÖÖ'de eşit olasılığa sahip konumları ifade eder.
İki adet öbekten oluşan 2 boyutlu noktalar.

$K$-ortanca ile Aradeğerlemeci Ayrışım

  1. $\m{D} \Leftarrow $ $N\times N$ uzaklık matrisi; $D_{ij} =\|\col{X}{i}-\col{X}{j}\|_2$

Neden $K$-ortanca?

  • Gürültü ve aykırı değerlere karşı gürbüz [Park ve Jun 2009]

AA'dan CUR Ayrışımına

$$X \approx \color{#0689e7}C\color{#7030a0}U\color{#ff7e37}R$$

  • Sütunları seçmek için $X$ üstüne AA uygula: $C=\col{X}{\Jcol}$
  • Satırları seçmek için $X^\intercal$ üstüne AA uygula: $R=\row{X}{\Jrow}$
  • Bağlantı matrisini hesapla $U=X(\Jrow,\Jcol)^\dagger$

Deneyler & Sonuçlar

Kullanılan Verikümeleri

Açık mavi kutular verikümesindeki sınıf sayısını gösterir.

Karşılaştırma Yöntemi

  1. Temel Bileşenler Analizi ile boyut sayısını azalt

MNIST Verikümesi

  • Elle yazılmış 10 farklı rakam
  • 20 $\times$ 20 boyutlarında
  • 50000 eğitim örneği
  • 10000 test örneği

Karşılaştırma Sonuçları

Tüm veri kullanıldığında elde edilen kesinlik, kırmızı çizgi ile üst sınır olarak verilmiştir.

Karıştırma (Confusion) Matrisleri

$\% 0$ $\% 100$
(a) 10-ortanca
(b) 100-ortanca
(c) 1000-ortanca
(d) Tümü
Önerdiğimiz yöntem ile 10, 100, 1000 sütun seçildiğinde veya tümü kullanıldığında elde edilen hata matrisleri

Önerdiğimiz Yöntemin Seçtiği Örnekler

     
     
     
     
     

Yaygın Rassal Yöntemin Seçtiği Örnekler

     
     
     
 
     
     

Fonem Verikümesi

  • 5 gerçel girdi
  • 3818 nasal ses örneği
  • 1586 oral ses örneği
  • 5-kat çapraz geçerleme

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^{\circ}, 45^{\circ}, 90^{\circ}, 135^{\circ}$
  • Toplam 5500 örnek
  • 5-kat çapraz geçerleme

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

MAGIC Gamma Teleskobu Verikümesi

  • 10 gerçel girdi
  • 2 farklı sınıf
  • Toplam 19020 örnek
  • 5-kat çapraz geçerleme

Karşılaştırma Sonuçları

  • Farklı verikümelerinde de $K$-ortanca yaygın olarak kullanılan ÖÖ tabanlı yöntemden daha iyi sonuç vermektedir.
K-Ortanca ve Önem Örnekleme'de her sınıf için örneklerin $\%20$'si kullanılmıştır.

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

Teşekkürler...