Apakah "proyeksi acak" secara ketat bukan proyeksi?

10

Implementasi saat ini dari algoritma Proyeksi Acak mengurangi dimensi sampel data dengan memetakannya dari hingga menggunakan matriks proyeksi matriks yang entri-entrinya dari distribusi yang sesuai (misalnya dari ): $\mathbb R^d$ $\mathbb R^k$ $d\times k$ $R$ $\mathcal N(0,1)$

$x^\prime = \frac{1}{\sqrt k}xR$

Secara mudah, ada bukti teoritis yang menunjukkan bahwa pemetaan ini kira-kira mempertahankan jarak berpasangan.

Namun, baru-baru ini saya menemukan catatan ini di mana penulis mengklaim bahwa pemetaan dengan matriks acak ini bukan proyeksi dalam arti aljabar linear yang ketat dari kata tersebut (halaman 6). Dari penjelasan yang diberikan di sana, ini karena kolom tidak sepenuhnya ortogonal ketika entri dipilih secara independen dari . Oleh karena itu, versi RP sebelumnya di mana ortogonalitas kolom ditegakkan dapat dianggap sebagai proyeksi. $R$ $\mathcal N(0,1)$ $R$

Dapatkah Anda memberikan penjelasan yang lebih terperinci tentang (1) apa definisi proyeksi dalam arti yang ketat ini dan (2) mengapa RP tidak proyeksi di bawah definisi ini ?.

terminology dimensionality-reduction linear-algebra random-projection Daniel López
sumber

1

Anda dapat menemukan jawaban untuk (1) dengan mencari di situs kami . Penegasan (2) adalah segera karena jika kolom yang selalu orthogonal, entri mereka tidak bisa mandiri.

Whuber

4

Apa definisi proyeksi dalam arti (aljabar linier) yang ketat ini?

https://en.wikipedia.org/wiki/Projection_(linear_algebra)

Dalam aljabar linear dan analisis fungsional, proyeksi adalah transformasi linear dari ruang vektor untuk dirinya sendiri bahwa seperti . Artinya, setiap kali diterapkan dua kali ke nilai apa pun, itu memberikan hasil yang sama seperti jika diterapkan sekali (idempoten). $P$ $P^2 = P$ $P$

Untuk proyeksi orthogonal atau proyeksi vektor, Anda memilikinya

https://en.wikipedia.org/wiki/Projection_(linear_algebra)

Proyeksi ortogonal adalah proyeksi di mana kisaran U dan ruang nol V adalah subruang ortogonal.
Mengapa RP bukan proyeksi di bawah definisi ini?

Michael Mahoney menulis dalam catatan kuliah Anda bahwa itu tergantung pada bagaimana RP dibangun , apakah RP adalah proyeksi dalam arti aljabar linier tradisional. Ini dia lakukan di poin ketiga dan keempat:

Ketiga, jika vektor acak benar-benar ortogonal (karena mereka sebenarnya berada dalam konstruksi JL asli), maka kita akan mendapatkan bahwa proyeksi JL adalah proyeksi ortogonal

...

tetapi meskipun ini salah untuk Gaussians, variabel acak , dan sebagian besar konstruksi lainnya, orang dapat membuktikan bahwa vektor yang dihasilkan adalah sekitar satuan panjang dan sekitar ortogonal $\lbrace \pm \rbrace$

...

ini "cukup baik."

Jadi Anda bisa melakukan, pada prinsipnya, proyeksi acak dengan konstruksi berbeda yang terbatas pada matriks ortogonal (walaupun tidak diperlukan). Lihat misalnya karya aslinya:

Johnson, William B., dan Joram Lindenstrauss. "Perpanjangan pemetaan Lipschitz menjadi ruang Hilbert." Matematika kontemporer 26.189-206 (1984): 1.

... jika seseorang memilih secara acak proyeksi ortogonal peringkat pada $k$ $l_2^n$

...

Untuk membuat ini tepat, kita membiarkan menjadi proyeksi ke koordinat pertama dan membiarkan dinormalisasi menjadi ukuran Haar pada , grup ortogonal pada . Kemudian variabel acak didefinisikan oleh menentukan gagasan tentang " proyeksi peringkat acak ." $Q$ $k$ $l_2^n$ $\sigma$ $O(n)$ $l_2^n$
$f : (O (n), σ) \to L (l_{2}^{n})$ $f: (O(n), \sigma) \to L(l_2^n)$ $f (u) = U^{⋆} Q U$ $f(u) = U^\star Q U$ $k$

Entri wikipedia menjelaskan proyeksi acak dengan cara ini (hal yang sama disebutkan dalam catatan kuliah di halaman 10 dan 11)

https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

Baris pertama adalah vektor satuan acak yang dipilih secara seragam dari . Baris kedua adalah vektor satuan acak dari ortogonal ruang ke baris pertama, baris ketiga adalah vektor satuan acak dari ortogonal ruang ke dua baris pertama, dan seterusnya. $S^{d − 1}$

Tetapi Anda biasanya tidak mendapatkan ortogonalitas ini ketika Anda mengambil semua entri matriks dalam variabel acak dan bebas matriks dengan distribusi normal (seperti Whuber disebutkan dalam komentarnya dengan konsekuensi yang sangat sederhana "jika kolom selalu ortogonal, entri mereka dapat tidak mandiri ").

Matriks dan produk dalam kasus kolom ortonormal, dapat dilihat sebagai proyeksi karena berkaitan dengan matriks proyeksi . Ini agak sama dengan melihat regresi kuadrat terkecil biasa sebagai proyeksi. Produk bukan proyeksi tetapi memberi Anda koordinat dalam vektor basis yang berbeda. Proyeksi 'nyata' adalah , dan matriks proyeksi adalah . $R$ $P = R^TR$ $b = R^T x$ $x' = Rb = R^TRx$ $R^TR$

Matriks proyeksi perlu menjadi operator identitas pada subruang yang merupakan kisaran proyeksi (lihat properti yang disebutkan pada halaman wikipedia). Atau dengan kata lain ia perlu memiliki nilai eigen 1 dan 0, sehingga subruang yang menjadi matriks identitasnya adalah rentang vektor eigen yang terkait dengan nilai eigen 1. Dengan entri matriks acak, Anda tidak akan mendapatkan properti ini. Ini adalah poin kedua dalam catatan kuliah $P=R^TR$ $U$

... itu "terlihat seperti" matriks ortogonal dalam banyak cara ... adalah subruang yang terdistribusi secara seragam ... tetapi nilai eigennya tidak berada di . $range(P^T P)$ $\lbrace 0, 1 \rbrace$

^{perhatikan bahwa dalam kutipan ini matriks berhubungan dengan matriks dalam pertanyaan dan bukan dengan matriks proyeksi yang tersirat oleh matriks $P$ $R$ $P = R^TR$ $R$}

Jadi proyeksi acak dengan konstruksi yang berbeda, seperti menggunakan entri acak dalam matriks, tidak persis sama dengan proyeksi ortogonal. Tetapi ini lebih sederhana secara komputasional dan, menurut Michael Mahoney, ini "cukup baik."

Sextus Empiricus
sumber

1

Terima kasih atas jawaban Anda, saya pikir itu berjalan ke arah yang sama dengan yang saya berikan di atas. Hanya untuk memperjelas saya pikir Anda harus menunjukkan bahwa . Maka saat Anda menjelaskan, jika entri iid dari kami tidak dapat memastikan bahwa atau bahwa memiliki nilai eigen di . Sebaliknya, jika kolom adalah ortonormal, kedua kondisi terpenuhi. Tetapi itu adalah kunci untuk menunjukkan bahwa proyeksi adalah , dan bukan saja!

P = R R^{T}

$P = RR^T$

R \in R^{d \times k}

$R\in\mathbb R^{d\times k}$

N (0, 1)

$\mathcal N(0,1)$

P^{2} = P

$P^2 = P$

P

$P$

{0, 1}

$\{0,1\}$

R

$R$

R R^{T}

$RR^T$

R

$R$

Daniel López

1

@ DanielLópez Saya telah memperbaruinya.

Sextus Empiricus

6

Itu benar: "proyeksi acak" secara tegas bukan proyeksi.

Proyeksi didefinisikan secara jelas objek matematika: https://en.wikipedia.org/wiki/Projection_(linear_algebra) - itu adalah operator idempotentent linear, yaitu operator linear sehingga . Menerapkan proyeksi dua kali sama dengan menerapkannya hanya sekali karena setelah suatu titik diproyeksikan pada subruang, ia harus tetap di sana jika diproyeksikan lagi. Tidak ada tentang ortogonalitas dalam definisi ini; sebenarnya, suatu proyeksi bisa miring (lihat Wikipedia). $P$ $P^2 = P$

Perhatikan bahwa hanya matriks persegi yang dapat mewakili "proyeksi" dalam pengertian ini. "Proyeksi acak" menggunakan matriks acak dengan , sehingga tidak mungkin berupa proyeksi dalam arti definisi di atas. $d\times k$ $R$ $k\ll d$

Sekalipun Anda membuat kolom ortonormal (mis. Dengan menerapkan proses Gram-Schmidt), argumen ini akan tetap berlaku. Seseorang baru-baru ini menanyakan pertanyaan ini tentang PCA: Apa yang sebenarnya harus disebut "matriks proyeksi" dalam konteks PCA? - a matrix dari vektor eigen ortonormal secara tegas bukan proyeksi juga. $R$ $d\times k$ $U$

amuba
sumber

3

Dalam paragraf terakhir, Anda mengatakan bahwa jika kolomnya ortonormal maka proyeksi masih bukan proyeksi dalam arti proyeksi dalam aljabar linier. Namun, ini hanya karena matriksnya bukan matriks persegi. Ini lebih disebabkan oleh notasi daripada karena prinsip. Jika Anda memperpanjang matriks dengan nol maka matriks adalah proyeksi linier.

Sextus Empiricus

1

@ MartijnWeterings Tidak, saya kira tidak. Ambil ruang 2D dan U yang 1x2 dan terlihat seperti ini: [sqrt (2) / 2, sqrt (2) / 2] (sesuai dengan proyeksi pada diagonal). Sekarang rentangkan dengan nol. Itu tidak akan sama dengan kuadrat itu sendiri.

amoeba

1

Itu harus diperluas dengan cara lain, bisa dilakukan

kjetil b halvorsen

2

@amoeba, saya setuju bahwa ini memperluas konsep / definisi, tetapi saya akan mengatakan bahwa itu lebih bernuansa daripada yang mencakup istilah terbalik ini yang tidak sama dengan . Kombinasi linear ketika terbuat dari vektor ortogonal memang menyerupai proyeksi ortogonal ke subruang yang lebih kecil dan Anda dapat mengulangi proyeksi yang menghasilkan hal yang sama. Hanya saja bersamaan dengan proyeksi, serangkaian vektor basis yang berbeda dipilih (setidaknya itulah yang dapat dilihat) dan representasi matriks tidak berfungsi seperti , tetapi secara geometris tampak seperti proyeksi.

R (R^{T} R)^{- 1} R^{T}

$R (R^TR)^{-1}R^T$

I

$I$

U

$U$

P^{2} = P

$P^2=P$

Sextus Empiricus

2

Itu benar, @ MartijnWeterings, tetapi mengapa dengan kolom non-ortogonal tidak "terlihat seperti" proyeksi miring ?

R

$R$

amoeba

1

Saya pikir kuncinya di sini adalah untuk mempertimbangkan ruang kolom dari RP matriks sebagai subruang yang kita lakukan proyeksi. Secara umum, terlepas dari apakah kolom adalah ortogonal, seseorang dapat memproyeksikan sampel ke ruang kolom menggunakan persamaan berikut [1]: $d\times k$ $R$ $R$ $x\in \mathbb R^d$ $R$

$p = xR(R^TR)^{-1}R^T$ , di mana . $p\in\mathbb R^d$

Jika seperti dalam versi yang lebih lama atau RP kolom matriks dibatasi menjadi ortonormal, maka , dan oleh karena itu proyeksi ke ruang kolom menjadi: $R$ $R^TR = I\in \mathbb R^{k\times k}$ $x$ $R$

$p = xRR^T$ , dengan , $p\in\mathbb R^d$

dan menjadi matriks proyeksi , karena itu persegi dan . $RR^T\in\mathbb R^{d\times d}$ $(RR^T)^2=RR^TRR^T=RR^T$

Mungkin klaim bahwa versi yang lebih tua dari Proyeksi Acak (jika kolom adalah ortonormal) sebenarnya adalah sebuah proyeksi yang merujuk pada fakta bahwa dalam hal itu penyematan ke dan rekonstruksi posterior kembali ke dari sampel diberikan oleh memang merupakan proyeksi ke ruang kolom , dan adalah matriks proyeksi . $R$ $\mathbb R^k$ $\mathbb R^d$ $x\in\mathbb R^d$ $xRR^T$ $R$ $RR^T$

Saya akan berterima kasih jika Anda dapat mengkonfirmasi / memperbaiki alasan saya di sini.

Referensi:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projections.pdf

Daniel López
sumber

1

R (R^{T} R)^{- 1} R^{T}

$R(R^T R)^{-1} R^T$

1

R R^{T}

$RR^T$

R

$R$

2

R (R^{T} R)^{- 1} R^{T}

$R(R^TR)^{-1}R^T$

(R^{T} R)^{- 1} R^{T}

$(R^TR)^{-1}R^T$

R^{T}

$R^T$

R^{T}

$R^T$

β = (R^{T} R)^{- 1} R^{T} y

$\beta=(R^TR)^{-1}R^Ty$

β

$\beta$

\hat{y} = R (R^{T} R)^{- 1} R^{T} y

$\hat{y}=R(R^TR)^{-1}R^Ty$

β

$\beta$

-1

Jika Anda menggunakan pembalikan tanda acak yang dapat dihitung ulang atau permutasi sebelum transformasi Fast Walsh Hadamard, proyeksi acaknya adalah orthogonal.

Sean O'Connor
sumber

Apakah "proyeksi acak" secara ketat bukan proyeksi?

Jawaban: