強大的在線算法半方差

我要找的welford's algorithm等價的在線計算半方差（下行局部方差）。有誰知道一個很好的參考？這樣的算法是否存在？強大的在線算法半方差

編輯：其中所述半方差相帶到一個固定的目標的情況下是微不足道的。問題是計算關係半方差平均

來源

2011-12-14 eyaler

爲什麼welford的算法對您不夠好？它具有在線性質。 – 2011-12-14 08:13:05

@amiri：它與方差不涉及變異函數 – eyaler 2011-12-15 10:32:28

我相信答案是不存在的，我要去嘗試勾勒出爲什麼會是這樣一個證明。

考慮一個「uesful」在線算法由兩個標準來定義：

處理期間

它必須有固定的存儲器需求。
每次更新都需要一段固定的時間。

這比一個順序/增量/在線算法的字面定義更嚴格，它只需要一次傳遞數據。但是，考慮到如果1）或2）不正確，那麼在處理足夠多的元素之後，運行該算法所需的內存或時間最終將變得不可行。通常，使用在線算法的原因之一是它們可以連續使用，而不用擔心性能會逐漸變差。此外，請注意，有用於計算均值和方差的在線算法，它們都滿足兩個要求，我認爲這就是我們的目標。

現在提出的問題。在處理過程中，平均值會隨着每一點新數據而改變。這反過來意味着低於均值的一組觀測值將會改變。當發生這種情況時，我們需要根據設置的「delta」來調整我們的運行半方差，定義爲不在舊平均值以下的元素集合和新平均值以下的元素集合之間的聯合元素。在新數據存在的情況下，我們必須在將舊半變量調整爲新半變量的過程中計算這個增量。

現在讓我們考慮計算這套三角洲的複雜性。我們需要找到所有落在舊平均值和新平均值之間的元素。我們將始終跟蹤舊的均值，而新的均值可以在固定時間內遞增計算，因此它們不構成問題。然而，要計算三角洲本身，除了要求我們跟蹤我們集合中的所有以前的元素之外，沒有辦法做到這一點。這立即打破了在線算法的記憶狀態。其次，即使我們將先前的元素保留在我們的集合中，我們能夠找到的舊平均值和新平均值之間的最佳速度爲O（log（元素數）），這比固定值要差。因此，最終，如果有足夠的元素，在線算法不僅需要比我們更多的內存，還需要更多時間。

來源

2011-12-15 00:16:52