浅谈机器学习(1)－Self-Information(自信息), Entropy(熵), Information Gain(信息增益)

说到Self-Information, Entropy, information gain, 我们不得不谈一谈20世纪最伟大的科学家之一，克劳德·香农(Claude Elwood Shannon)，当代信息论的奠基人。他一生中提出过很多伟大的理论，其中信息论的提出，解决了通信理论的很多难题，在次基础上很多不同的应用也被建立起来。

香农理论中，最重要的部分就是entropy的概念。Entropy曾经是波尔兹曼在热力学第二定律引入的概念，用来衡量一个系统的能量有多少被用来作为有用功，有多少可能转化为无效的热量。从分子运动论的观点看，作功是大量分子的有规则运动，而热运动则是大量分子的无规则运动，因此entropy也可以理解为分子运动的混乱程度。在信息论中，entropy被引申用来衡量随机变量的不确定程度。

众所周知，物体的重量可以用天平来衡量，物体的热量也可以用焦耳等单位来测量。可是对于文字，声音和视频，这些乘载信息的媒介，可不可以用一种统一的方式来衡量这些媒介的信息量。香农entropy的作用就是用来衡量一段媒介中所包含信息量的平均大小。例如，中文entropy是9.65比特，英文entropy是4.03比特。这表明中文的复杂程度高于英文，反映了中文词义丰富、行文简练，但处理难度也大。同时，香农entropy也代表了一段信息能够被无损压缩的上限值。

香农定义了一个独立随机变量的Entropy \(H\),
\[H(X)=E(I(X))\]其中，\(E\)是\(I\)的期望，\(I\)是X的自信息量,也就是所谓的self-information。

衡量一个自信息量self-information的大小必须满足以下几个条件:
1.一个随机变量\(x_{i}\)的信息量只依赖于这个随机变量\(x_{i}\)的概率\(p_{i}\)，与它本身的内容是没有关系的,其中:
\[\sum_{i=1}p_{i}=1\]
2.Self-information是一个\(p_{i}\)的连续函数。
3.Self-information是一个\(p_{i}\)的减函数。
4.如果\(p_{i}=p_{i,1}*p_{i,2}\),那么\(I(x_{i})=I(x_{i,1})+I(x_{i,2}).\)
符合以上条件的只有“logarithmic”函数，因此self-information可以定义为:
\[I(x_{i})=-log(P_{i})\]
因此Entropy可以定义为:
\[H(X)=\sum_{i=1}^{n}p(x_{i})I(x_{i})=-\sum_{i=1}^{n}p(x_{i})log_{b}p(x_{i})\]
其中，b是对数logarithm的底。当\(P(x_{i})=0\)的时候，\(0log_{b}0\)被定义为等于0,与其极限条件一致:
\[ lim_{p \rightarrow 0+}
plog_{b}p = 0\]

如果对数log以2为底，计算出来的Entropy就是以bit为单位。而在计算机和数字通信领域，也都是以2进制作为基本单位，所以Entropy的概念可以被广泛的应用到计算机和通信领域。Self-information(信息量)可以被定义为随机不确定程度的减少，换句话说，信息是用来减少随机不定性的变量，也就是信息是确定性的增加。

假设一个独立随机变量X有四个可能的值\({A, B, C, D}\), 它们的分布为:
\[P(X=A)=1/4, P(X=B)=1/4, P(X=C)=1/4, P(X=D)=1/4\]
一个字符序列:BAACBADCDADDDA..符合上面的分布:
我们要把这段字符用二进制的通道传输出去，可以把这四个字符分别编码为(A=00, B=01, C=10, D=11)。
0100001001001110110011111100...
平均每个字符需要2bits来传输

如果这四个值的概率分布不是一样的，新的分布如下:
\[P(X=A)=1/2, P(X=B)=1/4, P(X=C)=1/8, P(X=D)=1/8\]
如果我们把编码变成(A=0, B=10, C=110, D=111),
每个字符的平均长度会变成: 1/2*1+1/4*2+1/8*3+1/8*3=1.75bits

如果给定的一个随机变量\(X={V_{1}, V_{2}, ..., V_{m}}\)的分布,
\[P(X=V_{1})=p_{1}, P(X=V_{2})=p_{2}, ..., P(X=V_{m})=p_{m}\]
基于X的分布，每个字符需要编码成最小的比特数是什么？答案就是随机变量Entropy的大小。
\[H(X)=-p_{1}log_{2}P_{1}-p_{2}log_{2}P_{2}-..-p_{m}log_{2}P_{m}=-\sum_{j=1}^{m}p_{j}log_{2}p_{j}\]

如果随机变量\(X\)的Entropy的值越大，说明这个随机变量\(X\)不确定程度越大，需要把它编码成二进制代码量也越大。从上面的例子可以看出如果随机变量的分布越是不对称，其Entropy值也越小，也意味着这个随机变量可预测性也相对来说较高。

在介绍Information Gain之前，必须先介绍以下Canditional Entropy(条件熵)\(H(Y|X=v)\)的概念。
先看一下，下面的例子，X＝College Major, Y= Likes

College Major	Likes
Math	Yes
History	No
CS	Yes
Math	No
Math	No
CS	Yes
History	No
Math	Yes

从这个表格中，可以得出：
\(H(X)=-1/2log_{2}1/2-1/4log_{2}1/4-1/4log_{2}1/4=1.5\)
\(H(Y)=-1/2log_{2}1/2-1/2log_{2}1/2=1\)
Conditional Entropy可以被定义为:
\(H(Y|X=v)\)在随机变量\(X\)已经给定值\(v\)的情况下，\(Y\)的Entropy大小,也可以解释为当两边通信端都已经了解\(X\)的值为\(v\)的时候，传输\(Y\)的时候，平均需要多少比特。所以，\(H(Y|X)\)可以被定义为:
\[H(Y|X)=\sum_{j}Prob(X=v_{j}H(Y|X=v_{j}))\]
从上面的例子可以看出:
\(H(Y|X=Math)=-1/2log_{2}1/2-1/2log_{2}1/2=1\)
\(H(Y|X=History)=0\)
\(H(Y|X=CS)=0\)
\(P(X=Math)=0.5\)
\(P(X=History)=0.25\)
\(P(X=CS)=0.25\)
\(H(Y|X)=0.5*1+0.25*0+0.25*0=0.5\)

下面我们就可以介绍一下Information Gain(信息增益)的概念。
Information Gain就是当通信两边都知道随机变量\(X\)的时候，平均每个字符可以省下多少比特。
\[IG(Y|X)=H(Y)-H(Y|X)\]
还是上面的例子:
\(H(Y)=1\)
\(H(Y|X)=0.5\)
所以，\(IG(Y|X)=1-0.5=0.5\)
Relative Information Gain (相对信息增益)就是当需要传输\(Y\)的时候，通信两边都知道随机变量\(X\)的时候，平均每个字符可以节省的比特数占总的Entropy的比例。
\[RIG(Y|X)=(H(Y)-H(Y|X))/H(Y)\]

Information Gain具体有什么用？最直接的用处就是，当有一系列输入属性(features or attributes)\({x_{1}, x_{2}, ..., x_{n}}\)与你的目标属性\(Y\)相关，可以用Information Gain来发掘哪一个输入属性，包含了较多的目标属性的信息量，也意味着这个属性可以更好的来预测目标属性。
举个例子来说，为了预测是否一个人可以活到80岁,从以往的历史数据看
\(IG(LongLife|HairColor)=0.01\)
\(IG(LongLife|Smoker) = 0.2\)
\(IG(LongLife| Gender) = 0.25\)
\(IG(LongLife| LastDigitOfSSN) = 0.00001\)
从这四个属性{HairColor, Smoker, Gender, LastDigitOfSSN的信息增益可以看出，Gender(性别)与长寿更相关。

从以上可以看出，Information Gain是一个很好的工具用来预测特定的目标，由此延伸出一个机器学习方法－Decision Tree(决策树）。


我们可以定义样本为:\((x,Y)=(x_{1},x_{2},x_{3},...,x_{k}, Y)\)，其中\(Y\) 是我们试图预测的目标属性，向量\(x\)是一系列不同的属性组合而成。而决策树的目标就是创造一个模型树根据输入属性预测目标属性的值。基本思想就是先计算所有不同属性的Information Gain，既\(IG(Y|x)\)。含有最大的Information Gain输入属性就可以作为Decision Tree的根，然后这样依此递归计算Information Gain,就可以得到一个Decision Tree，如上图所示，其中树的内部节点就是输入属性，树的边就是输入属性的可能值，数的叶子就是需要预测目标属性的值。

Regerence:
Entropy, wiki, 2011
Self-Informationlecture notes of R.Victor Jones, 2011
Decision Tree Learning, wiki, 2011
克劳德.香农， 百度百科，http://baike.baidu.com/view/63224.htm
Claude Elwood Shannon，wiki, 2011
Information Gain, Andrew's tutorials, 2011

MTX Operate System --- Introduction

本文的主要资料来自于Washington State University的操作系统课CS460和CS560.
参考资料：
《The Design of the UNIX Operating Systeem》 Maurice J. Bach, Prentice-Hall, Inc. 1986

这个笔记主要是为了自己复习和总结一下UNIX内核的知识，同时也想借此机会把国外优秀的课程介绍给国内的学生。

图1描述了UNIX系统的系统架构。

中间的硬件层(hardware)为操作系统提供了各种基本的服务。操作系统内核(kernel)把硬件层和应用层分离开来。这样做的好处使应用程序可以运行在不同的硬件上，所有与硬件有关的活动，都由操作系统来完成。各种应用程序如果需要硬件服务(读写文件 等)，则是通过系统调用(system call)告诉系统内核，然后系统内核操作硬件来完成服务。

图2 系统内核结构图

图2 主要展示了计算机系统的三层结构图: 用户层，内核层和 硬件层。用户层主要通过系统调用和库函数与内核交流。系统调用在内核里主要与文件子系统和进程控制子系统交互。

文件子系统主要负责管理文件，分配文件空间，控制文件访问权限，提取文件给用户。内核可以直接从硬盘读写数据，但是从硬盘读写数据要受到硬盘读写效率的限制。所以，系统内核需要对硬盘读写的频率进行优化，方法就是用一个缓冲区来存放经常被读写的数据。如果数据已经在缓冲区了，就不需要在到硬盘里去寻找了。

进程控制子系统主要负责进程同步，进程间互相通信，内存管理和进程调度。每一项都有很多细节要考虑和设计，以后的章节会详细介绍。

CASASviz: new version 1.0

The new version of our CASASviz has just been generated.

There are some major improvements:

1) Generate Main Visualizer by JavaScript Library Raphaël. We test our webpage on the PC and Iphone platform. There is no any delay. It works very well.

2) Use a web application model Comet to push the data from server to the browsers, without any request from the browsers.

3) Implement Pattern Visualization. Now we can show all kinds of the patterns based on different algorithms.

4) More Intelligent Functions:
1) Location Detection: show current room
2) Activity Level: use sliding time window to show the level of the activity
3) Enter or Leave Home Detection: use special rule
4) Activity Recognition: We are trying to use real-time activity recognition algorithm

Next Steps:
1) Polish our webpage for PC and Iphone platforms
2) Interview the caregivers to get some valuable suggestions

函数将字符串中的字符'*'移到串的前部分， 前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。

如原始串为：ab**cd**e*12，
处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

这个题需要用到两个额外的下标而且要从后往前查找：第二个下标先找到第一个‘*’的位置，第一个下标，找到第一个'*'后面的字母，交换其中的字母；然后第二个下标指向下一个字符，第一个下标找到下一个字母，继续交换。
Time: O(n)

Common ancestor in a binary tree

From: http://zhedahht.blog.163.com/

第一变种是二叉树是一种特殊的二叉树：查找二叉树。也就是树是排序过的，位于左子树上的结点都比父结点小，而位于右子树的结点都比父结点大。我们只需要从根结点开始和两个结点进行比较。如果当前结点的值比两个结点都大，则最低的共同父结点一定在当前结点的左子树中。如果当前结点的值比两个结点都小，则最低的共同父结点一定在当前结点的右子树中。

第二个变种是树不一定是二叉树，每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表

现在我们回到这个问题本身。所谓共同的父结点，就是两个结点都出现在这个结点的子树中。因此我们可以定义一函数，来判断一个结点的子树中是不是包含了另外一个结点。这不是件很难的事，我们可以用递归的方法来实现：




我们可以从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点。基于这个思路，我们可以写出如下代码：



接着我们来分析一下这个方法的效率。函数HasNode的本质就是遍历一棵树，其时间复杂度是O(n)（n是树中结点的数目）。由于我们根结点开始，要对每个结点调用函数HasNode。因此总的时间复杂度是O(n2)。

我们仔细分析上述代码，不难发现我们判断以一个结点为根的树是否含有某个结点时，需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点，仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历，本方法在时间效率上肯定不是最好的。



由于这个路径是从跟结点开始的。最低的共同父结点就是路径中的最后一个共同结点：



有了前面两个子函数之后，求两个结点的最低共同父结点就很容易了。我们先求出从根结点出发到两个结点的两条路径，再求出两条路径的最后一个共同结点。代码如下：



这种思路的时间复杂度是O(n)，时间效率要比第一种方法好很多。但同时我们也要注意到，这种思路需要两个链表来保存路径，空间效率比不上第一个方法。

Convert Sorted List to Balanced Binary Search Tree (BST)

Things get a little more complicated when you have a singly linked list instead of an array. Please note that in linked list, you no longer have random access to an element in O(1) time.


Singly-linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.
Naive Solution:
A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).

Hint:
How about inserting nodes following the list’s order? If we can achieve this, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.

Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

Convert Sorted Array to Balanced Binary Search Tree (BST) 把已排序的数组转换成平衡二叉搜索树

A height-balanced tree is a tree whose subtrees differ in height by no more than one and the subtrees are height-balanced, too.

Solution:
If you would have to choose an array element to be the root of a balanced BST, which element would you pick? The root of a balanced BST should be the middle element from the sorted array.

You would pick the middle element from the sorted array in each iteration. You then create a node in the tree initialized with this element. After the element is chosen, what is left? Could you identify the sub-problems within the problem?

There are two arrays left — The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node’s left and right child.

The code below creates a balanced BST from the sorted array in O(N) time (N is the number of elements in the array). Compare how similar the code is to a binary search algorithm. Both are using the divide and conquer methodology.