[無母] K Nearest neighbour estimator

這是最近寫論文用到的東西。

冰島的火山坑(我當下其實看不出來那是什麼)

首先直接看公式

$\hat{p}\left(x_{i}\right)=\frac{1}{n-1}\frac{k}{c_{d}\ \epsilon_{k}\left(i\right)^{d}}$

其中$d$是維度，$\epsilon$則是該點的與第$k$個鄰居的距離，並且

$c_{d}=\frac{\pi^{d/2}}{\Gamma\left(d/2 + 1\right)}$

如果單獨把第二個component的分母拿出來看，其實$c_{d}\ \epsilon_{k}\left(i\right)^{d}$就是半徑為$\epsilon_{k}\left(i\right)$球體的體積，若簡寫為$V\left(i\right)$，則上式可寫成

$\frac{k}{n-1}\frac{1}{V\left(i\right)}$

整個基本概念就很清楚了，可以把這個estimator想成你在這個資料點畫出一個半徑為$\epsilon_{k}\left(i\right)$的球，並且觀察有多少點落在球內。如果你讓半徑是距離第$k$個點的距離，那麼落在球內的點當然就是$k$個。

[無關程式] 說書(1) Data and Social Good

最近網路上似乎刮起了一陣說書炫風，於是乎我也想來跟風一下。

波里(Pori), 芬蘭

緣起是之前在電子郵箱裡收到一封O'Reilly的廣告信，說只要註冊還幹嘛的就可以下載免費的電子書看，因著歐巴桑心態當然是要下載一下啦。

這本書很好玩，叫做Data and Social Good，內容是關於資料科學在社會公益上的應用。這本書沒有太多的硬知識，當做消遣的讀物蠻適合的，並且相較於目前大部分討論資料科學應用的書，因為較著重在社會公益上，這本書的內容算是蠻清流的，銅臭味比較沒那麼重。

書很薄，只有19頁，可能比多數的paper還短。內容主要是實際案例，以下列出幾個我覺得比較有趣的。

1. DataKind and Simpa Networks 

DataKind是一間非營利公司，主要工作是媒合資料科學家和社會企業或公益組織，Simpa Networks就是一個有趣的案例。

Simpa Networks是一間致力於提供印度鄉村地區太陽能發電設備的公司。能源問題在印度是一個相當嚴重的問題，將近七千五百萬個家庭沒有電力供應，或者必須使用煤油等燃料，造成許多健康問題，如眼睛疾病等。

DataKind和Simpa Networks合作，追蹤並且分析客戶的交易歷史資料，幫助Simpa Networks有效挑選新的合作客戶。

2. DataKind and CTL (Crisis Text Line)

CTL是一個提供心理支持的非營利組織，當人們在遇到重大危機的時候，往往面臨不知所措的景況，這時就可以發簡訊給CTL，受過訓練的專員透過回發簡訊提供支持、安慰或是轉介的服務。

CTL遇到的問題是，因為許多人重複的寄發簡訊，義工們花了將近34%的時間在處理3%的使用者的簡訊。DataKind和CTL合作，幫助CTL建立一套篩選出即興需求的機制，已將資源花在真正的刀口上。經過努力後，原本的34%有效將至8%，因此幫助CTL拯救了更多人的生命。

3. New York City Department of Health and Mental Hygiene (DOHMH), Yelp.com and Columbia University 

紐約市健康與心理衛生局(New York City Department of Health and Mental Hygiene, DOHMH)發現，餐廳評論網Yelp上的文章可以做為食物傳染疾病的重要資料。

因此DOHMH找上了Yelp.com和Columbia University的資料科學家，建立了一套機制，利用文字探勘工具(Text Mining Tools)篩選出有可能有問題的餐廳並介入調查。

其實書裡面提到的案例還很多，有興趣的自己去看吧！(爛尾)

[貝氏] Paper digest (4) 煩死人的Variational Bayes續集 -- Blackbox Variational Inference

這篇接著很久很久寫的煩死人的 Variational Bayes 初探往下寫的。如果用食記部落客的語法，應該改成「再訪！煩死人的Variational Bayes」(超無聊)。

好，會寫這篇的原因是因為最近拜讀了一篇由大神David Blei團隊所寫的這篇文章，順便邊讀邊寫，吸收快又好。題目叫做Blackbox Variational Inference，你沒看錯Variaional Bayes也有黑箱版的，這篇文章刊出的時間是2014年，那年台灣高中生也剛好在反黑箱課綱，真的蠻潮的。

這個方法的賣點是不需要手動計算複雜的積分也可以做Variational Inference。

先複習一下，Variational Bayes的精神就是找一個替代的替身 $q(\theta)$ 並且讓它和posterior $p(\theta, x)$ 越像越好，也就是盡全力把 $KL[q(\theta), p(\theta, x)]$ 變得很小就對了！接下來，

$KL \left[q \left( \theta \right),p \left( \theta \right|x) \right] $

$=\int q \left( \theta \right) \log \frac{q \left( \theta \right)}{p \left( \theta,x \right)} d \theta- \int q \left( \theta \right) \log p \left(x\right) d\theta$

$=\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta-\log p\left(x\right)$

$=E_{q}[q(\theta)] - E_{q}[\log p(\theta, x)]-C$

上式的$ E_{q}[q(\theta)] - E_{q}[\log p(\theta, x)]$取負號以後叫做 ELBO (Evidence lower bound)，也就是

$ ELBO = E_{q}[\log p(\theta, x)]-E_{q}[q(\theta)]$

只要不斷讓ELBO越來越大，  $KL[q(\theta), p(\theta, x)]$ 就會越來越小。

好現在假設我們的其中一個替身叫做$q(\theta|\lambda)$，最佳化 $\lambda$ 的梯度(gradient)就是

$\nabla_{\lambda}\int (\log p(\theta, x)-\log q(\theta|\lambda))q(\theta|\lambda)d\theta$

$=\int \nabla_{\lambda}(\log p(\theta, x)-\log q(\theta|\lambda))q(\theta|\lambda)d\theta$

$+\int \nabla_{\lambda}q(\theta|\lambda)(\log p(\theta, x)-\log q(\theta|\lambda))d\theta$

其中，

$\int \nabla_{\lambda}(\log p(\theta, x)-\log q(\theta|\lambda))q(\theta|\lambda)d\theta$

$=-E_{q}[\nabla_{\lambda}\log q(\theta|\lambda)]=0$

剩下另外一個，因為

$\nabla_{\lambda}q(\theta|\lambda)=q(\theta|\lambda) \nabla_{\lambda}\log q(\theta|\lambda)$

就可以寫成

$\int \nabla_{\lambda}\log q(\theta|\lambda)(\log p(\theta, x)-\log q(\theta|\lambda))q(\theta|\lambda)d\theta$

$=E_{q}[ \nabla_{\lambda}\log q(\theta|\lambda)(\log p(\theta, x)-\log q(\theta|\lambda))]$

這個東西是可以用Monte Carlo integration估計的，只要從 $q$ 中抽樣就可以了。

因此說了一堆，黑箱版本的好處其實就是不需要手動計算複雜的積分(再次強調)也可以找出梯度，然後一次做最佳化就可以了。

[機器學習] Paper digest (3) Computational rationality: A converging paradigm for intelligence in brains, minds, and machines

原文連結在這裡，一篇登在Science上的review。好久沒寫blog，發現中文整個退化到不行，連帶我原本就不好的英文，真的要變文盲了。

先來個風景照(芬蘭・坦佩雷)



這篇回顧了computational rationality在人工智慧，認知科學及神經科學上的發展。

先稍微整理一下所謂computational rationality：

首先，最終的desicion必須要有最大的expected utility，這樣的概念首先由von Neumann等人[1]提出，即所謂的MEU(maximize expected utility) principle。至於為什麼是expected utility呢？原因是因為我們所身處的世界充滿了不確定性(uncertainty)，也就是凡事皆機率的意思，因此需引入期望值(expected value)的概念。

通常現實世界所處理的問題都頗複雜或是大尺度的(large scale)，因此在計算expected utility時，就經常需要動用逼近(appriximation)等計算技巧。

而appriximation本身也是決策的一環，因為計算需花上可觀的時間及資源，而這也是computational rationality的核心。在最大化expected utility的同時也要將計算所可投注有限資源及時間納入考慮。

至於computational rationality的模型則是建立於：

1. Infernece under uncertainty.

2. The feasibility and implications of actions.

3. Bounded computation power.

4. Multilevel, or multireasoning.


人工智慧

IBM Watson參加電視益智節目時，基本上Watson的計算時間(時間內要作答)和計算能力是被限制的，因此Watson基本上並沒有辦法『想』或是『窮舉』出所謂『完美無誤』的答案，而是要在『有限的時間及資源』下『猜』出『近乎完美』或『正確機率較高』的答案。

當然AI領域還有其他例子，像是Google自動駕駛汽車或是，Microsoft的個人秘書。


認知科學

心理學家發現，人類並非所謂「直覺的統計學家」(intuitive statisticians)。很多時候，人類的決策和所謂的「最佳決策」往往天差地遠。

Computational rationality可以提供一個架構來解釋這種現象。當腦在缺乏足夠資源的情況下被迫要做出決定時，所謂充滿缺陷的決策就會出現，但這些看似非理性的決策很有可能是考量了當下的計算資源所做出最理性的決策(哇勒好玄)。

文中提到抽樣貝氏推論(approximating Bayesian inference by sampling)，可以作為一個例子。基本上，所抽的樣本越多，所得到關於後驗機率分配(posterior distrubution)的資訊就越正確，但在時間及計算能力的限制下，往往只能得到一小部分的樣本，因此讓決策產生偏誤，計算生物學界就有學者此利用抽樣演算法作為模擬神經迴路的行為[2](看到嚇了一跳，有一種這樣也可以的感覺)。

神經科學

Computational rationality可以解釋分別屬於腦中不同的核區(cortex)的兩個系統：model-based system和model-free system的分工。

一般認為，model-based system較依賴經驗，需要較長時間(速度較慢)，卻比model-free system來得有彈性。在剛開始的學習階段，因為model-free system所做出的決策往往較不精準，model-based system通常有較好的效果而被採用。但經過一定時間的學習，model-free system的決策也可以優化到一定程度，這時model-based system反而會被放棄採用。

然而，學界也證實了大腦再選取兩者時，計算的消耗也被考慮在內[3][4]。


未來發展

文末，作者提到computational rationality是一個很有潛力的架構，並且應可以應用在更多不同的領域。然而更進一步的理論架構，以及更多的證實，或甚至是辯論都是學界可以繼續努力的方向。

[1] Von Neumann, J., & Morgenstern, O. (2007). Theory of games and economic behavior. Princeton university press.

[2] Buesing, L., Bill, J., Nessler, B., & Maass, W. (2011). Neural dynamics as sampling: a model for stochastic computation in recurrent networks of spiking neurons. PLoS Comput Biol, 7(11), e1002211.

[3] Daw, N. D., Gershman, S. J., Seymour, B., Dayan, P., & Dolan, R. J. (2011). Model-based influences on humans' choices and striatal prediction errors.Neuron, 69(6), 1204-1215.

[4] Keramati, M., Dezfouli, A., & Piray, P. (2011). Speed/accuracy trade-off between the habitual and the goal-directed processes. PLoS Comput Biol, 7(5), e1002055.

[無母] Kernel Density Estimation

很久以前就看過這個方法，但都沒有仔細研究過。

有許多方法可以用來估計機率分配，以前課本上教的就是先假設一個機率分配(常常是Normal)，然後用動差法(moment-method)或者是最大概似估計(most likelihood)把參數找到後帶入。

無母數的做法就比較不一樣，在操作的時候避免假設一個太硬性的框架，以期發現更多數據底層的結構，KDE (Kernel Density Estimation)就是其中之一。話說回來，其實Histogram就是一種無母數的機率分配估計方法，像是下圖：

其實就是在計算

$p_{x}=\frac{\#of \ x_{i}\ is\ in\ the\ same\ bin\ with x}{bin\ width}$

所使用的參數就是bin的寬度和起始值(如上圖就是0)。

KDE也是類似的概念，要回答的問題是，當某個$x$並未被觀察到的時候，究竟背後的機率是多少？KDE回答問題的方式，就是去看$x$相進的點出現的情形，如果出現的多，表示其實$x$出現的機率很高，只是剛好by chance沒有被觀察到而已，反之則$x$本身出現的機率就是低的。

所以，當$x$出現機率的估計值就是

$p(x)=\frac{1}{nh}\sum_{i}kernel\left (\frac{x-x_{i}}{h}  \right )$

$h$是所謂的帶寬，$kernel$一般而言是以零為中心對稱的函數，並且所有值域的積分必須是$1$，像是Gaussian function

$k(u)=\frac{1}{\sqrt{2\pi}}\exp(\frac{u^{2}}{2})$

以下是我用不同$h$就產生上圖(Hitogram)的資料做的擬和

可以看出$h$的選擇很重要，太大的帶寬會導致under-fitting，太小的則導致over-fitting。帶寬的選擇又是另外一個很大的題目了。

[機器學習] Paper digest(1) On Multilabel Classification and Ranking with Bandit Feedback

這篇是在Journal of machine learning research上看到的
先附上原文位址

這篇文章提出一個機器學習方法在資訊不充足的情況下做出決策

所謂資訊不足指的是，我們所收集到的資料是未經排序的，但是我們要給的決策建議是卻是排序的。舉例而言，收集到的資料只有某些人的某些特質和他們各自看了哪些電影(partial feedback)，卻不知道這些人對這些電影的喜好程度，我們要如何給出一個排序過的推薦清單?

Loss function for partial information

這篇文章的作者發展的loss function：

$l_{a,c} \big(Y_{t}, \widehat{Y_{t}} \big) =a |Y_{t} \backslash \widehat{Y_{t}}|+\big(1-a\big) \sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big) $

其中$Y_{t}$是收集到的資料，$\widehat{Y_{t}}$是建議的決策，因此$Y_{t}$是沒有排序的，而$\widehat{Y_{t}}$是有排序的

$|Y_{t}, \widehat{Y_{t}}|$是指有多少$Y_{t}$裡的element沒有出現在$\widehat{Y_{t}}$裡面，概念上有點像是Hamming loss function；而$ \sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big)$則是考量了排序，$\widehat{Y_{t}}$中，沒有出現在$Y_{t}$的元素要是排得越前面，計分就越重

舉例來說，如果

$Y_{t}=\left \{ 1,3,8 \right \}$

$\widehat{Y_{t}} = \big(4,3,6\big)$

則

$|Y_{t}, \widehat{Y_{t}}| = 2$ ($Y_{t}$中的$1$, $3$不屬於$\widehat{Y_{t}}$)

$\sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big) = 3/3 + 1/3$  ($4$ 和 $6$的權重分別為$3/3$和$1/3$)

Multilabel classification

利用線性模型

$P_{t}(y_{1,t}, y_{2,t}, ...y_{k,t})=P_{t}(y_{1,t}, y_{2,t}, ...y_{k,t}|x_{t})$

$P_{t}(y_{i,t}=1) = \frac{g(-u_{i}^{T})}{g(u_{i}^{T}) + g(-u_{i}^{T})}$

最佳化上述的loss function找最好的決策，上述的loss function也可以寫成

$a \sum_{i=1}^{K}y_{i,t}+\big(1-a\big) \sum_{i \in\widehat{Y_{t}}}\big( c (j_{i}, |\widehat{Y_{t}}| ) - \big(\frac{a}{1-a} + c (j_{i}, |\widehat{Y_{t}}| ) \big)y_{i,t}\big)$

由於$\sum_{i=1}^{K}y_{i,t}$和$\widehat{Y_{t}}$基本上是無關的，所以在計算中只要最佳化

$E\left [l_{a,c} \big(Y_{t}, \widehat{Y_{t}} \big)   \right ]=\big(1-a\big) \sum_{i \in\widehat{Y_{t}}}\big( c (j_{i}, |\widehat{Y_{t}}| ) - \big(\frac{a}{1-a} + c (j_{i}, |\widehat{Y_{t}}| ) \big)p_{i,t}\big)$

就可以了

Others

作者也提出了另一個loss function：

$l_{p-rank, t}(Y, f)=\sum_{i,j\in \widehat{Y}_{t}:y_{i} <  y_{j}}\big(\left \{f_{i}(x_{t} ) < f_{j}(x_{t} )  \right \} + \frac{1}{2}\left \{ f_{i}(x_{t} ) = f_{j}(x_{t} ) \right \} \big)+ S_{t}|Y_{t}\backslash \widehat{Y}_{t}|$

$f$是ranking function而$ \left \{... \right \}$是indicator function，$S_{t}$則是$\widehat{Y}_{t}$的長度

作為評估排序表現的依據