Logistic Regression模型推导整理

Logistic Regression模型的假设函数定义如下:
$$
\begin{align}
h_{\theta}(x) & = \frac{1}{1+e^{-\theta^T x}} \\
& = \frac{e^{\theta^T x}}{1+e^{\theta^T x}} \\
\end{align}
$$
其中,\(\theta\)为参数,\(x\)为样本的特征,\(\theta\)和\(x\)均为列向量,假设函数可以认为是将该样本标记为正例的概率,即:
$$
\begin{align}
P(Y=1 \mid x) & = h_{\theta}(x) = \frac{e^{\theta^T x}}{1+e^{\theta^T x}} \\
P(Y=0 \mid x) & = 1 – h_{\theta}(x) = \frac{1}{1+e^{\theta^T x}}
\end{align}
$$
对于给定训练集(m个样本),应用Logistic Regression模型学习时,我们可以用极大似然估计模型参数\(\theta\)。似然函数为
$$
\prod_{i=1}^{m}P(Y=1 \mid x^{(i)})^{y^{(i)}} P(Y=0 \mid x^{(i)})^{1-y^{(i)}}
$$

$$
\prod_{i=1}^{m}h_{\theta}(x^{(i)})^{y^{(i)}}(1-h_{\theta}(x^{(i)}))^{1-y^{(i)}}
$$
其对数似然函数为
$$
\begin{align}
L(\theta) & = \sum_{i=1}^{m}[y^{(i)}\log h_{\theta}(x^{(i)}) + (1-y^{(i)})\log(1-h_{\theta}(x^{(i)}))] \\
& = \sum_{i=1}^{m}[y^{(i)}(\theta^T x^{(i)}) – \log (1+e^{\theta^T x^{(i)}})] \\
\end{align}
$$
Cost Function可定义为
$$
\begin{align}
J(\theta) & =\ – L(\theta) \\
& =\ – \sum_{i=1}^{m}[y^{(i)}(\theta^T x^{(i)}) – \log (1+e^{\theta^T x^{(i)}})] \\
\end{align}
$$
那么我们现在的目标是求极大似然,也就是最小化\(J(\theta)\),可以利用梯度下降。计算梯度的方法是对\(\theta_j\)求偏导
$$
\begin{align}
\frac{\partial}{\partial \theta_j}J(\theta) & =\ – \sum_{i=1}^{m}[y^{(i)}x_{j}^{(i)} – \frac{x_{j}^{(i)}e^{\theta^T x^{(i)}}}{1+e^{\theta^T x^{(i)}}}] \\
& = \sum_{i=1}^{m} x_{j}^{(i)}(\frac{e^{\theta^T x^{(i)}}}{1+e^{\theta^T x^{(i)}}} – y^{(i)}) \\
& = \sum_{i=1}^{m} x_{j}^{(i)}(h_{\theta}(x^{(i)}) – y^{(i)}) \\
\end{align}
$$

$$
\nabla_{\theta}J(\theta) = \sum_{i=1}^{m}x^{(i)}(h_{\theta}(x^{(i)}) – y^{(i)})
$$

参考资料:
[1].统计学习方法/李航著. ——北京:清华大学出版社,2012.
[2].http://ufldl.stanford.edu/tutorial/supervised/LogisticRegression/
[3].https://www.coursera.org/learn/machine-learning

解决Linux操作系统下Mysql中文乱码的真正方法

网上各种方法基本都是假的!

1.进入mysql后输入以下命令 set names utf8;

2.每次建表时在最后加上 DEFAULT CHARSET=utf8 ,例如:

 

2015年武汉科技大学“蓝桥杯”校内选拔赛题解

题目地址:2015年武汉科技大学“蓝桥杯”校内选拔赛

1001 Wavio序列
最长上升子序列(LIS)模板题,正向一遍LIS,反向一遍LIS,求个最大值即可。复杂度O(nlogn)。

1002 大正整数的加法
其实题目讲的很明白了,做小学生加法即可,注意除了最高位其他都要控制4位。

1003 到底有多少个三角形
暂缺。

1004 封闭曲线
显然公式是个多项式,求个方程即可。
目测多项式不会超过3次,不妨设\(f(x) = ax^3 + bx^2 + cx + d\),然后求解以下方程组算出系数:\(\begin{cases}
f(1) = 2 \\
f(2) = 4 \\
f(3) = 8 \\
f(4) = 14 \\
\end{cases}\)

1005 黑色星期五
日期瞎搞下就行了,打个巨表二分一下即可,代码太丑就不放出来了。

1006 木棒切割
POJ原题,暑假集训浩浩讲过,14级没做出来的自己拿着键盘到南3-513跪着去。
代码:https://github.com/fcbruce/ACM-ICPC/blob/master/code/POJ/1011_Sticks.cc

1007 能否找到正确答案
搜索,暂缺。

1008 素因子
签到题,先预处理出每个数的素因子即可。

1009 药丸
典型的卡特兰数,要使用高精度。

1010 最大异或值
暂缺。

1011 最优序列
dp随便搞下,维护下即可。

1012 做加法求和
题意是假的,其实是个哈夫曼编码,然后用stl中的优先队列会T,我手写堆+优化过的,好像可以线性搞过。

Linux下caffe框架的搭建

最近在研究深度学习,这是一种能模拟人脑进行分析学习的神经网络,其中卷积神经网络是近年飞速发展的一项技术,在图像处理等方面有广泛应用。

caffe是Berkeley Vision and Learning Center(BVLC)推出的一款基于卷积神经网络的框架。caffe使用C++开发,执行效率高,同时支持CPU和GPU运算,使用非常方便。下面来介绍下在Linux操作系统下caffe环境的搭建。

系统:Kali Linux 2.0(基于Debian 8.0)

其实在官网(http://caffe.berkeleyvision.org/install_apt.html)上说的已经非常详细了,不过有些地方还是需要修改下。

首先安装依赖:

sudo apt-get install libprotobuf-dev libleveldb-dev libsnappy-dev libopencv-dev libhdf5-serial-dev protobuf-compiler

boost库因为网络原因我无法通过apt来安装,只能去下载源码编译安装,我用的版本是1.59的,可以去官网(http://www.boost.org/)查看下载最新的版本。
下载连接:http://sourceforge.net/projects/boost/files/boost/1.59.0/boost_1_59_0.tar.bz2/download
下载完过后首先解压解包:
bunzip2 boost_1_59_0.tar.bz2
tar xvf boost_1_59_0.tar

然后通过以下命令安装:
cd boost
./bootstrap.sh
sudo ./b2
sudo ./bjam install

继续安装其他依赖:
sudo apt-get install libatlas-base-dev
sudo apt-get install libgflags-dev libgoogle-glog-dev liblmdb-dev
sudo apt-get install cmake

依赖基本就安装完毕了,接下来我们要下载源码,源码可以在https://github.com/BVLC/caffe上面看到。
下载源码:git clone https://github.com/BVLC/caffe.git
然后可以按照官网上的教程(http://caffe.berkeleyvision.org/installation.html)进行编译。
进入caffe根目录,我们要设置下Makefile的配置信息:
cp Makefile.config.example Makefile.config
然后根据自己机器的情况对配置进行修改,因为我的机器没有GPU,要使用CPU_ONLY,所以要把Makefile.config中的 CPU_ONLY := 1 这一行取消注释。我的Makefile.config文件内容为:

接下来要对部分代码进行修改,以下文件里面的hdf5的头文件路径都需要修改:
include/caffe/util/hdf5.hpp
src/caffe/net.cpp
src/caffe/layers/hdf5_output_layer.cpp
include/caffe/layers/hdf5_output_layer.hpp
src/caffe/layers/hdf5_data_layer.cpp
include/caffe/layers/hdf5_data_layer.hpp
把对应的头文件分别改成以下两个:

可能有其他的文件也需要修改,可以根据make all的输出信息对相应的代码进行修改。

接下来就可以进行编译安装了:
mkdir build
cmake ..
make all
make runtest

至此,caffe框架我们就搭建完成了,接下来我们可以进行一下测试。caffe里面自带了一些example,我们选择使用mnist的数据进行训练测试。mnist是一套美国小学生的手写数字的数据集,我们可以在官网查看到关于该数据集的一些信息:http://yann.lecun.com/exdb/mnist/

caffe的官方文档中有告诉我们如何使用mnist训练集:http://caffe.berkeleyvision.org/gathered/examples/mnist.html

首先我们要准备数据集,进入caffe根目录,输入以下命令:
./data/mnist/get_mnist.sh
./examples/mnist/create_mnist.sh

然后根据机器修改相关配置文件:examples/mnist/lenet_solver.prototxt,使用CPU进行训练,我的solver定义如下:

最后在caffe根目录下输入以下命令即可训练mnist:
./examples/mnist/train_lenet.sh

在我的i7-3667U下,花了24分钟完成训练,效率还是非常高的。

浅谈计算几何学中向量的一些应用

The sacred geometry of chance.

—— Shape Of My Heart

计算几何学是一门非常有趣而神秘的学科,她既有数学中的严谨,又有算法艺术中的神秘。计算几何的应用广泛,在计算机图形学、计算机辅助设计(CAD)、分子建模、制造业等领域中均有重要应用。

计算几何学的出现,大大推进了工业的发展。而计算几何中计算的精髓在于向量。不仅是计算几何学,在数学、物理学中,向量的应用也推动了他们的发展。

本文将讨论二维平面中向量的一些简单应用。

向量的定义和表示

向量(Vector, 也称作矢量),由方向和长度两个因素组成。在二维平面中,向量和点的表示方法是一样的。例如,一个二维向量可以简单地表示为:

\(\vec{a}=(x, y)\)

向量的表示方法虽然和点一样,但是它们的意义是不同的。向量之间有一些运算,比如:向量+向量=向量,点+向量=点,向量-向量=点,点-点=向量,而点+点这个运算没有任何意义。

向量的线性运算

向量的线性运算包括向量的加法、减法和数乘三种运算,下面直接给出C++代码:

 

向量的点积

点积,又被称为内积、数量积。顾名思义两向量的点积结果是一个数量。设向量\(\vec{a}=(x_1, y_1)\)和向量\(\vec{b}=(x_2, y_2)\)在同一平面内,其数量积为:$$\vec{a}\vec{b}= x_1x_2 + y_1y_2$$
其C++代码实现为:

那么,点积有什么具体的应用呢?让我们考虑下如何判断两条直线是否垂直(给出过直线的两点)。一个比较简单的想法是求出两条直线的方程,然后判断系数是否成比例。这个方法显然有些复杂,计算量比较大,而且还要考虑直接与坐标轴平行的情况。

不妨假设这两条直线分别为AB和CD。这时候我们再考察一下向量\(\vec{AB}\)和向量\(\vec{CD}\),这两向量正是两线段的方向向量,如果这两向量的数量积为零,那么这两条直线垂直。这种方法的具体实现和计算量都非常小,只要计算向量的点积,而且精度误差也较小。

向量的叉积

叉积,又被称为外积、向量积。显然和点积的结果不同,叉积的结果是一个向量,其方向需要用右手定则来确定。

首先给出二维计算几何中向量叉积的计算方法:

设向量\(\vec{a}=(x_1, y_1)\)和向量\(\vec{b}=(x_2, y_2)\)在同一平面内,则:$$\vec{a}\times \vec{b}=x_1y_2 – x_2y_1 = |\vec{a}||\vec{b}| \sin x$$
其C++代码实现为:

 

那么向量叉积具体有什么应用呢?让我们首先思考这样一个问题,已知平面上一三角形的三点(ABC)座标,如何计算这个三角形的面积。

首先一个简单的思路是取其中两点连起来作为底边,然后求另一点到底边的距离(高),然后根据 \(面积=\frac{底\times高}{2}\) 来计算三角形的面积。这个方法似乎很简单,但求高似乎是一个比较麻烦的问题。

其次一个简单粗暴的思路是利用海伦公式,直接求解三角形面积。这个方法比上一个思路简单很多了,但是其中有一个开平方的操作,这样带来的精度误差就比较大了。

还有一个求三角形面积的公式是\(S = \frac{|a||b|\sin C}{2}\)。这个公式比海伦公式更加简洁了,唯一的麻烦在于\(\sin C\)。这时候我们不妨回过头来看一下向量叉积的定义式,显然,求三角形的面积便可以用以下公式进行求解:
$$S = \frac{|\vec{a} \times \vec{b}|}{2}$$
利用上述公式,我们只需要减法、乘法、除法操作便能求出三角形的面积,不仅简单粗暴,而且精度损失也是非常小的。

事实上,叉积求的便是对应平行四边形的有向面积。

有了三角形面积的求解方法,让我们想一想多边形的面积该如何求解。这里的多边形按逆时针顺序给出其各个顶点的座标。

显然我们无法直接求解任意多边形的面积,不妨用化归转移的思想,我们把这个多边形剖成若干个三角形,我们只要求出各个三角形的面积,把它们加起来即可。由于用向量求出的是有向面积,我们只要按逆时针顺序直接做向量的叉积,而且也可以处理凹多边形。

上文笔者一直在强调有向,那么有向这个概念是如何体现的呢?我们不妨考虑一下这个问题:已知平面上一线段AB,问P点和AB的位置关系。P在有向线段\(\vec{AB}\)的左边?右边?还是所在直线上?

事实上我们只要求一次有向面积即可:计算\(\vec{AP} \times \vec{AB}\),如果结果为正,则在左边;结果为负,则在右边;如果结果为零,那么P位于AB所在直线上。

为什么呢,因为这里的方向其实是角度的方向:规定逆时针角度为正,顺时针角度为负。

这种判定,在计算几何学中通常被称为“to-left-test”,顾名思义就是判断点是否位于有向线段的左侧。

让我们不妨把问题扩展一下,如何判断点与三角形的关系?点位于三角形内部还是外部(为了简单起见,我们不考虑点位于三条边所在直线上)。

假设三角形三顶点为ABC,我们只要对点P与有向线段\(\vec{AB}\), \(\vec{BC}\), \(\vec{CA}\)做三次to-left-test,如果三次to-left-test的结果相同,那么就说明点P位于\(\triangle ABC\)的内部。

巧合的是,三次to-left-test一共有8种结果,而平面上三条直线能将一个平面分隔成7个部分,那么消失的那种情况在哪里呢?如果在曲面上,结果又是如何呢?

参考资料:
[1].算法导论(原书第3版)/(美)科尔曼(Cormen, T.H.)等著;殷建平等译;—北京:机械工业出版社,2013.
[2].算法竞赛入门经典——训练指南/刘汝佳,陈锋编著.—北京: 清华大学出版社,2012.
[3].计算几何/邓俊辉主讲.—学堂在线MOOC平台,2015.

大学毕业前要点的技能(不定期更新)

转眼就大三狗了,离明年3月的春招只剩半年不到了,发现在基本还是什么都不会,最后半年要垂死挣扎下。

技能:
英语。六级还没过,感觉想要去好点的外企还是好难。
数据结构与算法。虽然玩了两年的ACM,但感觉自己还是好弱,什么都不会,好多数据结构和算法都没有真正理解。
操作系统。面试必备,这学期好好学。
计算机网络。居然下学期才开课,只能靠自学了。
计算机组成原理。CSAPP到现在还没买。。。
编译原理。感觉大二学的那些根本不够啊,全忘光了,龙书还没翻几页。
正则表达式。这个不会有点对不起自己。
C/C++。感觉学了等于没学,好多细节都不知道,比如const在C和C++中的区别,指针什么的也一知半解,至于多态、继承、虚函数那些都是什么鬼。。。
Java。虽然天天黑Java,而且也看不起Java,但是面向对象还是很重要。用Java的都是傻逼。
markdown。
latex。
git。github上markdown引擎真是烂得像坨屎。
vim。用了一年整,还是只会一点点。
linux。至今用了一年半,还没到火候。
python。be more pythonic。
perl。
php。

书:
《程序员健康指南》。边看这个还边熬夜,其实挺讽刺的。
《算法导论》。到现在还没认真翻过几页,有点对不起自己。
《编译原理》。龙书。
《Effective C++》。代码习惯太差,根本不敢见人。
《深入理解计算机系统》。本科不看完CSAPP有点对不起这个专业。
《人月神话》。我好歹是软件工程科班出身。