機器學習基石 - PLA算法初步

什么是PLA算法

PLA = Perceptrons Learning Alogrithm

WikiPedia上有一个大概的历史背景介绍。

感知机(英语:Perceptron)是Frank Rosenblatt在1957年就职于Cornell航空实验室(Cornell Aeronautical Laboratory)时所发明的一种人工神经网络。它可以被视为一种最简单形式的前馈式人工神经网络,是一种二元线性分类器。

PLA算法的原理

感知机示意图

对于每种输入值(1 - D),我们计算一个权重。当前神经元的总激发值(a)就等于每种输入值(x)乘以权重(w)之和。

由此我们就可以推导出公式如下。

neuron sum

我们可以为这个“神经元”的激发值设定一个阈值threshold

如果 a > threshold,则判定输入为正例。 如果 a < threshold,则判定输入为负例。 对于 a == threshold的情况,认为是特殊情况,不予考虑。

所以,我们的感知器分类器就可以得到以下式子 …

more ...

Linux内核中的少锁链表

前言

最近在stackexchange上看到一个问答,讨论我们常用的数据结构与算法在实际工程中的应用。(戳我)

我打算借助这个问答中的内容,以我比较熟悉的数据结构与算法为索引来阅读开源代码。

正文

Talk is cheap

Lock-less NULL terminated single linked list

linux-2.6/include/linux/llist.h

linux-2.6/lib/llist.c

知识准备

volatile

volatile关键字声明的变量或对象通常拥有和优化和(或)多线程相关的特殊属性。

通常,volatile关键字用来阻止(伪)编译器对那些它认为变量的值不能“被代码本身”改变的代码上执行任何优化。

如果不使用volatile关键字,编译器将假设当前程序是系统中唯一能改变这个值部分。 为了阻止编译器像上面那样优化代码,需要使用volatile关键字。

From: http://zh.wikipedia.org/wiki/Volatile%E5 …

more ...

Codeforces Round #215 (Div. 2)不完全不正确题解

A. Sereja and Coat Rack

傻逼才错的题。不幸中枪。

没什么可说的。直接看代码就好。

B. Sereja and Suffixes

关键思想在于统计A[i...n-1]中有多少互不相同的数。

使用离线思想,把查询按greater<int>排序,然后使用Hash表进行统计,简单题。

C. Sereja and Algorithm

思路题。

我们容易想到如果可以交换相邻两个字母的位置,我们就可以获得这个字符串所有的排列。

所以我们只需要统计出A[i...j]中x, y, z的个数。

然后进行排列。

我们可以推出,稳定的排列(即可以使算法停下来的排列)只有如下几种情况。

zy[xzy][xzy]...
xz[yxz][yxz]...
yx[zyx …
more ...

CSE351 - Lab 1: Manipulating Bits Using C

今天做了CSE351 - Lab1,深深的感觉国外的计算机教学爆了我校一条街。

以上是前言。


bitAnd & bitOr

德摩根定理的应用

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
  return ~(~x | ~y);
/* 
 * bitOr - x|y using only ~ and & 
 *   Example: bitOr(6, 5) = 7
 *   Legal ops: ~ &
 *   Max ops: 8 …
more ...

CSE 351 - Hardware/Software Interface

开一门公开课,Washington University的Hardware/Software Interface。

传说是很不错的计算机科学公开课。使用深入理解计算机系统做教材,正好是我要读的书,所以顺便听听课。

豆瓣上有人写了推荐,观点是这课虽然不错,但是比较浅。根据我现在的理解来说,确实比较浅,如果有不错的高级语言编程基础(C/C++/Java/Pascal等,脚本就算了),很多东西可以速推。

接下来的一些日志会是这门课的作业、实验和感想。现在先挖个坑。慢慢填上。


课程视频:戳我

课程主页:戳我

more ...

使用pip和virtuanenv

让我们从一个无聊的小段子开始。

"What’s pip?"

"A python package manager"

"How do I install it?"

"easy_install pip"

"What’s easy_install?"

"A python package manager"

pip和easy_install都是python的包管理工具,类似于ruby的gem以及nodejs的npm。

而pip是easy_install的升级版,在这个页面中提到了pip对于easy_install的升级。其中提到了一点非常重要。

pip is complementary with virtualenv, and it is encouraged that you use virtualenv to isolate your installation.

如果有同学不熟悉virtualenv,这里是一个小小的介绍。(以下翻译来自:戳我 …

more ...