Shannon–Hartley theorem

有噪信道编码定理只适用于离散的数字信道,若要将其应用于真实的物理信道还需要费一番功夫。当然其结果就是著名的香农极限。

对于某个物理信道,若:

  1. 其带宽为 $W$.
  2. 其噪声为功率谱密度为 $N_0$ 的高斯白噪声
  3. 信号的平均功率为 $P$.

则该信道的容量为 $C = W\log(1+\frac{P}{N_0W})$ 比特每秒。

The Noisy-Channel Coding Theorem

这在信息论中是一个非常重要的定理,之所以会想到回头学习信息论的相关知识,是因为这与概率推理有直接的联系,通信的本质就是根据接收到的信道输Y出来推理信道的输入X的过程。

Definitions & Notations

在正文开始之间先介绍一些定义和标识,顺便复习一下一些信息论中的基本结论。

  • 用 $X, Y, Z$ 来表示随机变量,$\mathcal{A}_{X}$ 表示变量的取值集合,$X^N$ 则表示将 $N$ 个独立的 $X$ 组成的整体作为一个随机变量
  • 信息熵: $H(X) = -\sum\limits_{p_i}\log{p_i}$
  • 条件信息熵: $H(X|Y) = \sum\limits_{y \in \mathcal{A}_Y} P(y) H(X|Y=y) = - \sum\limits_{xy \in \mathcal{A}_X\mathcal{A}_Y} P(x, y) \log{P(x|y)}$,满足:

$H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$

  • 互信息: $I(X; Y) \equiv H(X) - H(X|Y) = H(Y) - H(Y|X)$,度量了两个随机变量相互蕴含了多少关于对方的信息
  • 信道容量: $C \equiv \underset{\mathcal{P}_X}{\mathrm{max}}\ I(X;Y)$,表示输出变量 $Y$ 最多能够蕴含多少关于输入 $X$ 的信息

Fisher information and CRLB

Fisher Information

又来抄录 Wikipedia 了,Fisher information 这个词我在好多地方见过,一直是不求甚解地意会着,最近发现这影响到一些东西的理解,于是开始翻看百科。

言归正传,Fisher information 对于学统计的人应该很熟悉,用于描述可观测的变量 X 包含的对于决定它分布的参数 $\theta$ 的信息大小,直观地理解,如果 X 包含的关于 $\theta$ 的信息越多,后者就越确定,也就是其估计的方差越小。了解到这个信息就能得知,对于某些特定的分布模型,我们对于参数 $\theta$ 的极大似然估计 $\hat{\theta}_{ML}$ 的确信程度。

Style mod for GoodReader with vimperator

The Pain Point

Like I’ve mentioned in other posts, most of my reading is done with digital materials. And the application that I use most often for that purpose is named GoodReader(IOS platform). There certainly are better alternatives, nevertheless, I’m too lazy(poor) to alter.

The old fashioned UI design of the app seems a little bit complicated and confusing, however the front-end page for file transfer via a WLAN is too simple to be satisfying.

  • no design not all
  • multi-file uploading not allowed
  • progressing info is too inconspicuous

The hybrid Monte Carlo

Preface

作为一种先进的采样算法,在 PRML 11.5 中有较为详细的介绍,然而我反复细读了两遍才初窥门径,于是打算将其整理成文。

Goals of Sampling

我决定从 Metropolis 算法开始介绍 Markov Chain Monte Carlo,然后是 Gibbs 采样,最后到混合 Monte Carlo,顺便作为笔记以便日后翻阅。

不论是哪种算法,其目的都是一致的,即抽取出符合分布 $p(\mathbf{z})$ 的样本,同时,我们希望样本之间是无关的,即满足 i.i.d. 条件。

Hammersley Clifford Theorem

Preface

PRML 中 8.3.2 小节简单描述了 Markov Random Fields 的分解特性,其中最核心的部分就是 Hammersley Clifford Theorem, 然而它并没有证明这个定理,只是在末尾的时候提到了这个结论,导致我在阅读中间部分的时候一头雾水。好在我 google 到了一个优雅的证明,顺便翻译在此。

Quosi Newton Methods

Preface

最近在以蜗牛般的速度啃 PRML。第五章提到了拟牛顿法,这玩意我之前大致意会过,并作了一些笔记,然而我完全无法回忆起来,于是翻出之前的笔记重新意会了一遍,顺便更正了之前一些不太正确的理解,总结整理成下文。

Newton’s Method

考虑求自变量 X 为 N 维向量的函数 $f(X)$ 的极值点问题。我们知道高中数学中的牛顿法可以用于求解函数0点的:$X_{k+1} = X_n - [J_f(X_k)] ^{-1}f(X_k)$. 那么可导函数的极值问题其实就是求其导函数的0点问题,同样可以用牛顿法求解。

Add TOC indexes to PDF

PDF books without Indexes are like Planets with Individuals

I prefer e-books to paper books, actually I may have read only 1-2 paper books in recent 3 years, while e-books of a much larger amount. The pros of e-books are really obvious:

  1. portability
  2. context can be copied
  3. easy to manage
  4. easy to navigate

I don’t want to argue about the superiorities here. I just wanna to convey that the 4th feature is a crucial one, and it is mainly achieved via indexes, bookmarks, reference links, etc. There’s no doubt that among those approaches, indexes play the most significant role. So I say that e-books without indexes are like planets with individuals, i.e. huge gaps among separated pieces of text.

SVD++ Implementation in GraphX

Clarification

写完之后我突然发现这个标题看上去貌似有“以下实现是由本人完成的”这样的误导,所以特此澄清,下文出现的代码统统摘自
apache/spark.

SVD++ Intro

首先简单介绍 SVD++ 算法在协同过滤中的应用及其数学直觉。

SVD in CF

考虑 CF 中最为常见的用户给电影评分的场景,我们需要一个数学模型来模拟用户给电影打分的场景,i.e. 对评分进行预测。

一个 Naive 的方案可以是将评分矩阵看作是两个矩阵的乘积:

$$
U = \begin{bmatrix}
u_{11} & \cdots & u_{1k} \\
\vdots & \ddots & \vdots \\
u_{m1} & \cdots & u_{mk}
\end{bmatrix}
\begin{bmatrix}
i_{11} & \cdots & i_{1n} \\
\vdots & \ddots & \vdots \\
i_{k1} & \cdots & i_{kn}
\end{bmatrix}
$$.

CPS and Monads

Aha

最近搬了个地儿,离开了生活了近6年的合肥。呆在合肥的时候不觉得她有什么不好,现在想想空气质量是真不照;呆在合肥的时候不觉得她有什么好,现在想想吃饭是真便宜。

总之就是这段时间一堆烂事,导致前边挖下的坑没能及时填上。另外,随着研究方向的逐渐明确,也许不能再写这些“不务正业”的玩意了,也许会写点跟方向相关的内容,虽然我觉得这个方向上的工作纯忽悠,完全不值一提。我就是一个始终觉得别人研究的东西无比高大上,自己手上的东西都是crap的人。

Useful Monads with Interpretor

上一篇结尾提到的那篇论文总算是看完了。既然不能完全消化,吸收,然后拉出屎来;那么我就简单粗暴地吞下去,嚼一嚼,吐出来好了(美其名曰翻译+注释)。

论文很长,肯定不能逐字翻,我主要关心的是第三章,但是直接跳过前边又不行,所以先简单节选些第二章的内容。