維數災難

釋義

維數災難(Curse of Dmensionality):通常是指在涉及到向量的計算的問題中，隨著維數的增加，計算量呈指數倍增長的一種現象。維數災難在很多學科中都可以碰到，比如動態規劃，模式識別等。

舉例

1.動態規劃中的維數災難
動態規劃問題的維數即指的是各階段上狀態變數的維數。當狀態變數的維數增加時，動態規劃問題的計算量會呈指數倍增長，限制了人們用動態規劃研究問題和解決問題的能力。故人們把這種情形稱為“維數災難”。
解決動態規劃中的維數災難的思想：降維。即通過一些特殊技巧或算法把一個高維的動態規劃問題逐步分解為一些低維的動態規劃問題，以此來減輕維數災難。
2.模式識別中的維數災難
根據模式識別理論，低維空間線性不可分的模式通過非線性映射到高維特徵空間則可能實現線性可分，但是如果直接採用這種技術在高維空間進行分類或回歸，則存在確定非線性映射函式的形式和參數、特徵空間維數等問題，而最大的障礙則是在高維特徵空間運算時存在的“維數災難”。也即是維數越高，計算量越大。
解決方法：採用核函式技術可以有效地解決“維數災難”。