Boyutluluğun laneti - Curse of dimensionality

Boyutluluk laneti ortaya çıkan çeşitli olaylara atıfta açtığının analiz ve organize veri yüksek boyutlu uzaylarda gibi düşük boyutlu ortamlarda meydana gelmez üç boyutlu fiziksel mekan gündelik deneyimin. Bu ifade, dinamik programlamadaki problemler göz önüne alındığında Richard E. Bellman tarafından yapılmıştır .

Sayısal analiz , örnekleme , kombinatorik , makine öğrenimi , veri madenciliği ve veri tabanları gibi alanlarda boyutsal olarak lanetli fenomenler meydana gelir . Bu problemlerin ortak teması, boyutsallık arttığında, uzayın hacminin o kadar hızlı artmasıdır ki, mevcut veriler seyrekleşir. Bu seyreklik, istatistiksel anlamlılık gerektiren herhangi bir yöntem için sorunludur . İstatistiksel olarak sağlam ve güvenilir bir sonuç elde etmek için, sonucu desteklemek için gereken veri miktarı genellikle boyutla birlikte katlanarak büyür. Ayrıca, verilerin düzenlenmesi ve aranması genellikle nesnelerin benzer özelliklere sahip gruplar oluşturduğu alanları tespit etmeye dayanır; ancak yüksek boyutlu verilerde, tüm nesneler seyrek ve birçok yönden farklı görünür, bu da ortak veri organizasyon stratejilerinin verimli olmasını engeller.

Etki Alanları

kombinatorik

Bazı problemlerde, her değişken birkaç ayrık değerden birini alabilir veya sonlu sayıda olasılık verecek şekilde olası değerler aralığı bölünebilir. Değişkenleri bir araya getirerek, çok sayıda değer kombinasyonu düşünülmelidir. Bu etki kombinatoryal patlama olarak da bilinir . En basit ikili değişken durumunda bile , olası kombinasyonların sayısı zaten boyutsallıkta üsteldir. Naif bir şekilde, her ek boyut, tüm kombinasyonları denemek için gereken çabayı ikiye katlar. ${\görüntüleme stili d}$${\ Displaystyle 2^{d}}$

Örnekleme

Matematiksel bir boşluğa fazladan boyutlar eklemekle ilişkili olarak hacimde üstel bir artış vardır . Örneğin, 10 ²  = 100 eşit aralıklı örnek noktası , noktalar arasında 10 ⁻² = 0,01'den fazla olmayan bir birim aralığı ("1 boyutlu küp") örneklemek için yeterlidir ; komşu noktalar arasında 10 ⁻² = 0,01 boşluk olan bir kafese sahip 10 boyutlu birim hiperküpün eşdeğer bir örneklemesi, 10 ²⁰ = [(10 ² ) ¹⁰ ] örnek noktası gerektirecektir. Genel olarak, 10, bir aralık mesafesi ile ^{- N} 10-boyutlu bir hiperküp 10 bir faktör olduğu görülmektedir ^{N (10-1)} = [(10 ⁿ ) ¹⁰ / (10 ⁿ )] "büyük" 1'den boyutlu birim aralığı olan hiperküp. Yukarıdaki örnekte n = 2: 0,01'lik bir örnekleme mesafesi kullanıldığında, 10 boyutlu hiperküp , birim aralığından 10 ¹⁸ "daha büyük" görünmektedir . Bu etki, yukarıdaki kombinatorik problemlerin ve aşağıda açıklanan mesafe fonksiyonu problemlerinin bir birleşimidir.

Optimizasyon

Dinamik optimizasyon problemlerini sayısal geriye dönük tümevarım ile çözerken , her bir değer kombinasyonu için amaç fonksiyonu hesaplanmalıdır. "Durum değişkeninin" boyutu büyük olduğunda bu önemli bir engeldir.

Makine öğrenme

Olarak makine öğrenme bir "state-of-doğa" yüksek-boyutlu bir veri örneklerinin sınırlı bir sayıda öğrenme ile ilgili problemlerin özelliği alan olası bir değer aralığı olan her bir özellik ile, tipik olarak, eğitim verileri büyük bir miktar sağlamak için gerekli olan her bir değer kombinasyonuna sahip birkaç örnek olduğunu.

Tipik bir pratik kural, temsilde her boyut için en az 5 eğitim örneği olması gerektiğidir. Olarak makine öğrenme ve tahmini performans söz konusu olduğu durumlarda, boyutluluk küfür ile birbirlerinin yerine kullanılır pik fenomeni olarak da bilinir, Hughes olgu . Bu fenomen, sabit sayıda eğitim örneğiyle, bir sınıflandırıcının veya regresörün ortalama (beklenen) tahmin gücünün, kullanılan boyutların veya özelliklerin sayısı arttıkça ilk olarak arttığını, ancak belirli bir boyutun ötesinde, istikrarlı bir şekilde gelişmek yerine bozulmaya başladığını belirtir.

Bununla birlikte, basit bir sınıflandırıcı bağlamında ( ortak bilinen bir kovaryans matrisi varsayımı altında çok değişkenli Gauss modelinde lineer diskriminant analizi ) Zollanvari ve ark. (zaten sınıflandırıcının bir parçası olan özelliklere göre) ek bir özellik setinin nispi kümülatif etkinliği, bu ek özellik setinin boyutundan daha büyük (veya daha az) olduğu sürece, beklenen hatanın hem analitik hem de ampirik olarak göstermiştir. bu ek özellikler kullanılarak oluşturulan sınıflandırıcı, bunlar olmadan oluşturulan sınıflandırıcının beklenen hatasından daha az (veya daha büyük) olacaktır. Başka bir deyişle, hem ek özelliklerin boyutu hem de bunların (göreli) kümülatif ayrımcı etkisi, ortalama tahmin gücünde bir azalma veya artış gözlemlenmesinde önemlidir.

Mesafe fonksiyonları

Öklid mesafesi gibi bir ölçü birçok koordinat kullanılarak tanımlandığında, farklı örnek çiftleri arasındaki mesafelerde çok az fark vardır.

Yüksek boyutlu Öklid uzayının "genişliğini" göstermenin bir yolu , yarıçapı ve boyutu olan yazılı bir hiperkürenin oranını, kenarları uzunlukları olan bir hiperküpünkiyle karşılaştırmaktır . Böyle bir kürenin hacmi , gama fonksiyonu nerede , küpün hacmi ise . Uzayın boyutu arttıkça, hiperküre, hiperküpün hacmine göre önemsiz bir hacim haline gelir. Bu , boyut sonsuza giderken oranlar karşılaştırılarak açıkça görülebilir : ${\görüntüleme stili r}$${\görüntüleme stili d}$${\ Displaystyle 2r.}$${\displaystyle {\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}}$${\görüntüleme stili \Gama }$${\görüntüleme stili (2r)^{d}}$${\görüntüleme stili d}$${\görüntüleme stili d}$

${\displaystyle {\frac {V_{\mathrm {hipersfer}}}{V_{\mathrm {hiperküp}}}}={\frac {\pi ^{d/2}}{d2^{d-1}\ Gama (d/2)}}\rightarrow 0}$olarak .${\displaystyle d\sağ ok \infty }$

Ayrıca, sabit r için sınır olmaksızın artan merkez ve köşeler arasındaki mesafe 'dir. Bu anlamda, yüksek boyutlu uzayın neredeyse tamamı merkezden "uzaktır". Yüksek boyutlarda, d -boyutlu hiperküp biriminin hacmi ( köşelerin koordinatlarıyla birlikte ), büyük boyut d için yarıçaplı bir kürenin yakınında yoğunlaşır . Gerçekten de, her koordinat için küpün ortalama değeri ${\displaystyle r{\sqrt {d}}}$${\görüntüleme stili \pm 1}$${\displaystyle {\sqrt {d}}/{\sqrt {3}}}$${\displaystyle x_{i}}$${\displaystyle x_{i}^{2}}$

${\displaystyle \langle x_{i}^{2}\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1} {3}}}$.

Küpte düzgün dağılımın varyansı ${\displaystyle x_{i}^{2}}$

${\displaystyle {\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\langle x_{i}^{2}\rangle ^{2}={\ frak {4}{45}}}$

Bu nedenle, orijinden uzaklığın karesi , ortalama d /3 değerine ve 4 d /45 varyansına sahiptir . Büyük için d , dağılımı yakın normal dağılım ortalama 1/3 ve standart sapma göre merkezi limit teoremi . Böylece, yüksek boyutlarda, hiperküpün hem "ortası" hem de köşeler boştur ve tüm hacim "ara" yarıçaplı bir kürenin yakınında yoğunlaşmıştır . ${\displaystyle r^{2}=\sum _{i}x_{i}^{2}}$${\görüntüleme stili r^{2}/d}$${\displaystyle {\frac {2}{\sqrt {45d}}}}$${\ Displaystyle {\sqrt {d/3}}}$

Bu aynı zamanda ki-kare dağılımının anlaşılmasına da yardımcı olur . Gerçekten de, [-1, 1] aralığındaki rastgele bir noktayla ilişkili (merkezi olmayan) ki-kare dağılımı , d- küpünde rastgele bir noktanın uzunluk-kare dağılımıyla aynıdır. Büyük sayılar yasasına göre, bu dağılım kendisini orijinal türevin standart sapma karesinin (σ ² ) d katı civarında dar bir bantta toplar . Bu, ki-kare dağılımını aydınlatır ve ayrıca d- küp hacminin çoğunun bir yarıçap küresinin yüzeyine yakın yoğunlaştığını gösterir . ${\displaystyle \sigma {\sqrt {d}}}$

Bu fenomenin bir başka gelişimi aşağıdaki gibidir. Gerçek sayılar üzerindeki herhangi bir sabit dağılım, ℝ ^d' deki noktalarda bir çarpım dağılımına neden olur . Herhangi bir sabit n için , rastgele bir referans noktası Q ile bir n rastgele veri noktası listesi arasındaki minimum ve maksimum mesafenin P ₁ ,..., P _n minimum mesafeye kıyasla ayırt edilemez hale geldiği ortaya çıktı:

${\displaystyle \lim _{d\to \infty}E\left({\frac {\operatöradı {dist} _{\max }(d)-\operatöradı {dist} _{\min }(d)}{ \operatöradı {dist} _{\min }(d)}}\sağ)\to 0}$.

Bu genellikle, yüksek boyutlarda (örneğin, özellik karşılaştırma algoritmalarındaki en yakın komşu kriteri için) kullanışlılığını kaybeden uzaklık fonksiyonları olarak belirtilir. Bununla birlikte, son araştırmalar bunun yalnızca tek boyutlu dağılımlar ℝ bağımsız ve aynı şekilde dağıtıldığında yapay senaryoda geçerli olduğunu göstermiştir . Öznitelikler ilişkilendirildiğinde, veriler daha kolay hale gelebilir ve daha yüksek mesafe kontrastı sağlayabilir ve sinyal-gürültü oranının önemli bir rol oynadığı bulunmuştur, bu nedenle özellik seçimi kullanılmalıdır.

En yakın komşu araması

Etki , yüksek boyutlu uzayda en yakın komşu aramasını karmaşıklaştırır . Tüm boyutlara dayalı bir mesafe için bir koordinattaki farkı alt sınır olarak kullanarak adayları hızlı bir şekilde reddetmek mümkün değildir.

Bununla birlikte, son zamanlarda, ilgili ek boyutların kontrastı da artırabileceğinden, yalnızca boyutların sayısının mutlaka zorluklarla sonuçlanmadığı gözlemlenmiştir . Ek olarak, elde edilen sıralama için yakın ve uzak komşuları ayırt etmek faydalı olmaya devam etmektedir. Bununla birlikte, alakasız ("gürültü") boyutlar, kontrastı yukarıda açıklanan şekilde azaltır. Olarak zaman serisi analizi verileri doğal olarak yüksek boyutlu olan, mesafe işlevleri de güvenilir bir sürece işe sinyal-gürültü oranı yeterince yüksek olduğu.

k -en yakın komşu sınıflandırması

Uzaklık fonksiyonu endişeleri yüksek boyutluluk diğer bir etkisi de k -nearest komşu ( k -NN) grafikler bir inşa veri kümesi bir mesafe fonksiyonu kullanılarak gerçekleştirilebilir. Boyut arttıkça, alıcılık dağılımı k -NN digraf olur çarpık çünkü orantısız sayıda ortaya çıkması sağında bir zirve ile hub olduğunu, çok daha fazla görünür veri noktaları k diğerinin -NN listeleri ortalamadan daha fazla veri noktası. Bu fenomen, çeşitli sınıflandırma teknikleri ( k- NN sınıflandırıcı dahil ), yarı denetimli öğrenme ve kümeleme üzerinde önemli bir etkiye sahip olabilir ve ayrıca bilgi alımını da etkiler .

Anomali tespiti

2012 yılında yapılan bir ankette, Zimek ve ark. yüksek boyutlu verilerde anormallikleri ararken aşağıdaki sorunları tespit etti :

1. Puanların ve mesafelerin konsantrasyonu: mesafeler gibi türetilmiş değerler sayısal olarak benzer hale gelir
2. Alakasız nitelikler: yüksek boyutlu verilerde, önemli sayıda nitelik alakasız olabilir
3. Referans kümelerinin tanımı: yerel yöntemler için referans kümeleri genellikle en yakın komşu tabanlıdır.
4. Farklı boyutlar için kıyaslanamaz puanlar: farklı altuzaylar kıyaslanamaz puanlar üretir
5. Puanların yorumlanabilirliği: puanlar genellikle artık anlamsal bir anlam ifade etmez
6. Üstel arama alanı: arama alanı artık sistematik olarak taranamaz
7. Veri gözetleme yanlılığı: geniş arama alanı göz önüne alındığında, istenen her önem için bir hipotez bulunabilir
8. Hubness: Bazı nesneler komşu listelerinde diğerlerinden daha sık görülür.

Analiz edilen özel yöntemlerin çoğu, bu sorunlardan birini veya diğerini ele alıyor, ancak birçok açık araştırma sorusu var.

Boyutsallığın kutsanması

Şaşırtıcı bir şekilde ve beklenen "boyutluluğun laneti" zorluklarına rağmen, en basit yöntemlere dayanan sağduyulu buluşsal yöntemler, yüksek boyutlu problemler için "neredeyse kesinlikle optimal olan sonuçlar verebilir". "Boyutluluğun kutsanması" terimi 1990'ların sonlarında tanıtıldı. Donoho , "Millennium manifestosu"nda, "boyutluluğun kutsaması"nın neden gelecekteki veri madenciliğinin temelini oluşturacağını açıkça açıkladı. Boyutsallığın kutsanmasının etkileri birçok uygulamada keşfedildi ve temellerini ölçü fenomeninin konsantrasyonunda buldu . Boyutsallık fenomeninin bir örneği, rastgele bir noktanın büyük bir sonlu rastgele kümeden yüksek olasılıkla doğrusal olarak ayrılabilirliğidir, bu küme üstel olarak büyük olsa bile: bu rastgele kümedeki öğelerin sayısı boyutla birlikte katlanarak büyüyebilir. Ayrıca, bu lineer fonksiyonel, en basit lineer Fisher diskriminantı şeklinde seçilebilir . Bu ayrılabilirlik teoremi, geniş bir olasılık dağılımları sınıfı için kanıtlanmıştır: genel tekdüze log-içbükey dağılımlar, bir küpteki çarpım dağılımları ve diğer birçok aile (son zamanlarda gözden geçirilmiştir).

"Boyutluluğun kutsaması ve boyutluluğun laneti aynı madalyonun iki yüzüdür." Örneğin, yüksek boyutlu bir uzayda esasen yüksek boyutlu olasılık dağılımlarının tipik özelliği şudur: Rastgele noktaların seçilen bir noktaya olan uzaklığının karesi, yüksek olasılıkla, ortalama (veya medyan) kare uzaklığına yakındır. Bu özellik, beklenen veri geometrisini ve yüksek boyutlu verilerin indekslenmesini (kutsama) önemli ölçüde basitleştirir, ancak aynı zamanda yüksek boyutlarda benzerlik aramasını zor ve hatta işe yaramaz (lanet) yapar.

Zimek et al. boyutsallık lanetinin tipik biçimselleştirmelerinin iid verilerini etkilediğini , her bir nitelik içinde ayrılmış verilere sahip olmanın yüksek boyutlarda bile daha kolay hale geldiğini kaydetti ve sinyal-gürültü oranının önemli olduğunu savundu : veri, eklenen her nitelik ile daha kolay hale geliyor. sinyal ve verilere yalnızca gürültü (alakasız hata) ekleyen niteliklerle daha zor. Özellikle denetimsiz veri analizi için bu etki bataklık olarak bilinir.

Ayrıca bakınız

Referanslar