Deep Learning Basement

There are some basic important concepts in deep learning.

Backpropagation Network

BP Network is a special case of Feedforward networks, constituted by nonlinear continuous transformation units, and adjusted by error back propagation algorithm. The BP algorithm can be divided into two phases: propagation and weight update.

Also, some techniques are used to improve BP algorithm. For instance, gentic algorithm (supervised) and RBM (unsupervised), Auto-decoder (Deep Learning) can be in order to search for good weights before training.

Distributed Representations

In contrast to the “atomic” or “localist” representations employed in traditional cognitive science, a distributed representation is one in which “each entity is represented by a pattern of activity distributed over many computing elements, and each computing element is involved in representing many different entities.”

Yoshua Bengio gave a vivid analogy between “local” and “distributed” in his given talk, Learning to Represent Semantics.

Deep Learning Motivation for Semantics

In Language Model, given a probability for a longer word sequence, , we then predict P(next word|context). And in traditional n-gram Language Model, we use counts and smoothing to calculate the conditional probability.

However, the traditional n-gram LM fails with Curse of dimensionality: a word sequence on which the model will be tested is likely to be different from all the word sequences seen during training.

For example, the training sentence:

The cat is walking in the bedroom.

The Test sentence:

A dog was running in a room.

Under the sparsity/curse of dim. problem, we seek for a similar representations for semantically similar phrases.

Word Embedding for Representing Words

Word Embedding gives a low dimension (usually 50) distributed representation (Hinton, 1986) for each word. Thus similar words have similar representations. This distributed continuous-valued vector for each word can be learned from raw text (Colobert & Weston, 2008).

Composing Words with NN

The Word Embedding is only the representation for each word, we should learn how to compose words into phrases and semantic relations. And Theorems on advantage of depth (Hastad et al 86 & 91, Bengio et al 2007, Bengio & Delalleau 2011, Braverman 2011) proves that deep architectures are more expressive and sharing components exponentially strengthens the advantage.

Neural Network Language Model

Training the word embedding and the neural network at the same time, there are two types of system: Neural network language model and the others. The former type consists of (1)input: context; (2)output: distribution of next word, nodes. And the latter type (1)input: entire sequence; (2)output: score, 1 node.

Probabilistic Neural Language Model

Back to the problem, predict P(next word context). To calcute the conditional probability:
  • Traiditional N-gram Languge Model uses counts and smoothing.
  • Probabilistic Neural Language Model uses word embedding and neural network.

After building the language model, compute word vectors during this process:

This structure is Bengio’s groundbreaking work. It has a linear projection layer, a nonlinear hidden layer and a softmax output layer. The sparse history h is projected into some continuous low-dimensional space, where similar histories get clustered. Moreover, the model is more robust: less parameters have to be estimated from the training data.

But the model has limitation below:

  • Complexity:
  • New words fails
  • Long term context ignored
  • Lack priori knowledge, such as POS, semantic information (WordNet)

Problems Remain

How to design a neural network? An art or a science? :P

References

Yoshua Bengio. Learning to Represent Semantics. Words2Actions Workshop, NAACL HLT 2012, Montreal

Hinton, G. E., McClelland, J. L., and Rumelhart, D. E. (1986). Distributed representations. In Rumelhart, D. E. and McClelland, J. L., editors, Parallel Distributed Processing: Explorations in the Microstructure of Cognition. Volume 1: Foundations, MIT Press, Cambridge, MA.

R. Collobert and J. Weston. A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning. In International Conference on Machine Learning, ICML, 2008.

Morin and Bengio. Hierarchical Probabilistic Neural Network Language Model. AISTATS 2005.

Mnih and Hinton. A Scalable Hierarchical Distributed Language Model. NIPS 2008.

为什么会有overfitting,为什么regularization有效

对于某一个给定的 ,根据大数定理,当 n 趋向于无穷时,经验风险泛函是(依概率)收敛于风险泛函的。 但是机器学习是在一个给定的函数空间 中搜索一个最优的(使得风险泛函最小的)函数,因此为了保证这个搜索过程是合理的,需要保证对于整个空间 中的所有函数能一致收敛。 于是,当n趋于无穷时表现好并不是就代表 n 有限的时候同样好,即在 n 有限时,直接去最小化经验风险泛函并不一定是最优的,会造成 overfitting 等问题。所以,要分析在n 有限时,给出一个 之间的差别的 bound ,这个 bound 不仅依赖于 n 的大小,还依赖于我们所用的目标函数空间的“大小”——比如用 VC 维之类的东西来刻画。因此,在最小化经验风险泛函的同时,通过正则化的方法同时去最小化目标函数空间的“大小”——即“结构风险最小化”。

Regularization带来什么

这部分是看《Learning From Data》的slides里讲到的。

Regularization 其实是 constrain 了搜索空间,比如 constrain 了最小二乘的 weight 大小。 带来的结果是 bias 有可能增加(side-effect),但 variance 降低(这是期望带来的)。

L0, L1, L2都带来什么

L0应该就是SRM,结构风险最小化。据说可以用来筛掉指数级别的不相关feature,但是不可求解。

(1)

L1也是NP-hard问题(本质因为可以和L0对等),是个菱形,最初用于所谓的compressed sensing。

(2)

L2是个球形,保持旋转不变性。

(3)

L1和L2的话,L1可以作为特征选择(本质也是因为对等到L0,而L0中是非零分量个数的正则),但是比较难求解(难是说需要用优化算法求解,比如Bregman Iteration);L2求解方便,不会引入很高的复杂度。

关于L1和L0优化的等价问题可以参考 Candes,Donoho 等人的 Compressed sensing 理论。

当然还有什么L1/2之类的,是 non-convex 的。先不说了。

江申在《DSP中的算法初探》中提到了一个 Covariate Shift 的问题,第一次听说,查了一下,发现是一个非常重要的问题。

在 DSP 中,这个问题叫做 Bid Adjustment:

在线上生产环境进行实际竞价时,通常需要对竞价模型的参数做调整。

原因:1)线上的数据分布与线下用的训练数据的分布不一样,需要对参数做调整; 2)线上的环境是动态变化的,得让参数也随之变化。

Covariate Shift 就是说, training and test data were so different,我们在 training 过程中 sampling 假设的 distribution 和实际真实的 distribution 差异太大了导致我们最后的training 是 waste。

解决办法是通过两步:

  • Step 1: 得到真实分布 q 和假设的分布 p 之间的 ratio
  • Step 2: reweight training set

Step 1就需要考虑如何去衡量两个分布之间的差异。直观的方法是:训练一个 LR 模型,数据为“训练+待预测”数据,Label 为是否属于训练集。分得准,差异大。分不准,差异小。 理论上这里 用 任意learning方法出来的 classifier 都是可以的(见 paper: Discriminative Learning Under Covariate Shift conclusion 的部分)。

特别的,如果用LR的话,简单的推导见 Alex Smola 的一篇 blog

  • Step 2 学到了这个 ratio 就可以做 reweight。

re-weight each instance by the ratio of probabilities that it would have been drawn from the correct distribution, that is, we need to reweight things by p(xi)q(xi). This is the ratio of how frequently the instances would have occurred in the correct set vs. how frequently it occurred with the sampling distribution q.

很多 Transfer Learning 的方法都和这个类似。

There are several types of problems one may meet when loading data in R. I solved some of them and taken down the notes below.

tough garbage CN characters in R

中文乱码的问题在很多情况下都遇到了。内因是R是用本地码(通常是GBK)来解释unicode。 目测整体解决办法有几种:

  • Encodings

这个办法我只成功解决过一次。

source(file,encoding="utf-8") 
  • 改R的环境

    很奇怪的是在英文环境下都反而有时候不乱码。

  • 操作系统的系统编码问题

    Windows是 gbk 编码,且不可改!(所以只能 Encodings 改了);Linux 是 utf-8 。可以用 sessioninfo() 来查看 locale 的编码,然后改掉。一般有时候比如 mysql 也乱码的时候这个方法很好用,应该是个通用性很高的方法。

    Windows 一般是gbk的编码,读取utf-8的文件时,需要声明读取编码就OK了。

      source(file,encoding="utf-8") 
    

    Linux的情况复杂一些

    • locale要设置成zh_CN
    • 要安装中文字符集,或者从window下复制过去
    • R读取,统一用utf-8的。

    最复杂的情况是DB连接

    • 有时候DB的字符集是gb2312, gbk, utf8等
    • 在DB读取的时候,DBI包,要设置DB的字符编码
    • 当把数据读到R中时,要跟R的环境的编码要统一
    • linux/win两套环境,编码部分要是区别写的。

    Ref

  • 强大的iconv()

    Usage

      iconv(x, from = "", to = "", sub = NA, mark = TRUE) 
      iconvlist()  
    

    除此以外还可以用于除掉一些乱码,比如 Removing non-ASCII characters. Ref

  • 强大的iconv()也失效时

    • 更多更好的去理解网页编码 Ref

        url= htmlParse(url,encoding="UTF-8")  
      
    • embedded null characters (‘\0’) in strings

    这个似乎也是个 devils 在 inferno 的书里有写,下次再开坑吧。 Ref

missing values

大概是 missing value 要仔细处理。

和 missing value 有关的大概有4件事:

  • 如何填充 missing value
  • misquote 等等会引起 missing value
  • whitespace 可能丧失
  • extraneous fields 用 fill 解决或者用 count.fields 诊断

      x <- count.fields("UserProfile.tsv", sep = '\t') 
      table(x) 
      which(x != legal.length) // check where the illegal lines are 
    	
    	
      userlist <- read.table("UserProfile.tsv", sep = '\t', header = FALSE, stringAsFactors = FALSE, fill = TRUE) // "file" matters. 
    

其中填充 missing value 涉及到 na.strings()。这里牵扯到如果一个 string value 真的是 NA,要注意加quote。 Ref

再之, 对 NA 的问题又牵扯出 na.action.

group to summary

  • The ddply() function. It is the easiest to use, though it requires the plyr package. This is probably what you want to use.
  • The summarizeBy() function. It is easier to use, though it requires the doBy package.
  • The aggregate() function. It is more difficult to use but is included in the base install of R.

《学会提问——批判性思维指南》   

##步骤

1、 “谁关心这个话题” :你的时间是宝贵的,在你花费时间对某个问题进行批判性评价前,先问问who cares。

2、找出结论

   在找出结论之前我们无法做出批判性评价!

   结论就是演讲者或作者希望你接受的信息。

   没有支持的言论仅仅是一些观点而非结论。

3、确定理由是批判性思维的重要步骤

   要问“为什么”:要确定你是否发现了一条理由,最好的方式是你尽量扮演作者的角色。

   结论依赖于理由的价值。

4、寻找干扰性原因

   当你有充足的理由相信作者或演说者对某件事的因果解释的证据时,你就需要寻找干扰性原因。

   一旦你发现一个因果说明,一定要警惕干扰性原因存在的可能性。

5、被遗漏的信息    我们要特别强调下面这种被遗漏的信息,因为这种信息非常重要,但却常常被忽略,这就是:作者所提倡的行为可能产生的消极作用。   

##概念类

###两种思维——海绵式思维、淘金式思维

1、海绵式思维:吸收、获得

  优点1:吸收的越多,越能理解它的复杂性。

  优点2:相对被动,主要的心理加工就是注意和记忆。

  缺点1:始终相信其最后接收的信息

2、淘金式思维:与知识积极的互动

  优点1:评判所见所闻的价值

  优点2:回报巨大

  缺点1:艰辛、具有挑战性   

###强、弱批判性思维

1、弱——是用批判性思维维护你自己已有的观点

2、强——是运用相同的技能来评估所有的观点和信念,特别是评估自己的观点和信念

###论题的种类

1、描述性论题——针对有关过去、现在、未来的描述是否正确提出的问题。

2、说明性论题——针对我们应当怎样做及对与错、好与提出的问题。

###文章基本要素:论题、结论、理由

理由包括信念、证据、比喻、类推以及其他用来支持或证明这些结论的陈述。

###两种假设    1、描述性假设——关于世界是什么样子的观念

2、说明性或价值观假设——关于世界应当怎样的观念

###三个通常的谬误

1、提供了错误或不正确假设的推理

2、通过使信息看起来与结论相关而实际上不相关来转移我们的视线

3、需要使用已经被证实为真的结论来为结论提供支持

###书摘

  1、 人类的行为是如此的矛盾和复杂,因此我们对人类行为有问题的最好答案在本质上就带有不确定性。
  2、 旧答案和新答案之间的相互影响是我们成长的基础。
  3、 决定是否赞同某个观点的根本一步就是确定关键词或关键句的准确含义。   4、 政治性的语言常常附带有感情色彩,并有歧义。
  5、 请记住:你的听众不能长时间地专注于你说的话。如果你让某个听众感到困惑,那么你可能很快就会失去他;如果你不能重新吸引他的注意,你就是一个失败的传达者。   6、 在所有论证中,都存在一些作者所认同的思想,而这类思想的典型特征就是作者没有对它们进行清晰的陈述。   7、 在推理的结构中,这些思想是隐形的重要环节,是将全部论证整合在一起的黏合剂。   8、 事实上,只有当推理中加入价值观假设时,作者的理由才能在逻辑上支持结论。   9、 同一个价值观对不同的人来说,强烈程度是不同的。在回答一个说明性问题时,价值观的这种相对强度就会导致你得出与别人不同的答案。   10、 我们仅仅在某一个点上保持自己的价值观倾向。   11、 即使人们具有相同的价值观假设,也有可能得出不同的结论,因为人们对于每种结果产生的可能性及其影响程度有着不一致的看法。   12、 你要记住,由于诸多原因,权威的意见常常是错误的。   13、 记住:两事件相关并不能证明它们之间有因果关系!   14、 另外,“基本归因错误”是一种常见的偏见,即在解释他人的行为时,我们会过高地估计个人倾向性的作用,而降低了环境因素的作用。   15、 推理往往是不完整的。因此,如果你一遇到信息缺失就自动声明你无法得出结论,那么,你就永远无法形成任何观点。