ML概率相关的几个名词

25 Feb 2019 Category: 算法

概率中的各种概率名词,统一整理。

先验概率: 事件X发生的概率P(X)叫做先验概率。一般通过统计获得

条件概率: 事件X在条件Y的情况下发生的概率P(X Y)叫做条件Y下X的条件概率,又叫似然概率,一般通过统计获得
后验概率: 事件X发生的条件下Y发生的概率P(Y X)叫做X的后验概率。事件发生后求的反向条件概率

贝叶斯公式:

P(X Y) = P(X,Y)/P(Y)
P(Y X) = P(X,Y)/P(X)
P(Y X) = P(X Y)P(Y)/P(X)
贝叶斯决策: 若Y是Y样本X的分类标签,P(Y X)最大的类别作为判别结果。P(Y X)=P(X Y)P(Y)/P(X)
一般的,先验概率可以通过统计得到。条件概率P(X Y)由于条件组合多,一般无法使用统计获取。解决的办法就是,把估计完全未知的条件概率分布转化为估计参数。这里就将概率密度估计问题转化为参数估计问题,极大似然估计就是一种参数估计方法。

最大似然估计的目的就是:利用已知的样本结果,反推最有可能(最大概率)导致这样结果的参数值。

对于函数:P(x θ)

输入有两个:x表示某一个具体的数据;θ表示模型的参数。

如果θ是已知确定的,x是变量,这个函数叫做概率函数(probability function),它描述对于不同的样本点x,其出现概率是多少。

如果xx是已知确定的,θ是变量,这个函数叫做似然函数(likelihood function), 它描述对于不同的模型参数,出现x这个样本点的概率是多少。

最大似然估计(MLE)

给定一堆数据,假如我们知道它是从某一种分布中随机取出来的,可是我们并不知道这个分布具体的参,即“模型已定,参数未知”。例如,我们知道这个分布是正态分布,但是不知道均值和方差;MLE的目标是找出一组参数,使得模型产生出观测数据的概率最大:

其中$p(X;\mu)$叫做似然函数,表示在参数$\mu$下出现观测数据的概率.

为了计算方便,一般取对数似然:

对对数似然函数求导,使得导数为0,求出参数$\mu$

最大后验概率估计(MAP)

最大似然估计是求参数$\mu$, 使似然函数$p(X;\mu)$最大。最大后验概率估计则是想求$\mu$使$ p(X \mu)p(\mu) $最大。求得的$\mu$不单单让似然函数大,$\mu$自己出现的先验概率也得大。
实际上,最大后验概率是求$p(\mu X)=\frac{p(X \mu)p(\mu)} {p(X)} $最大,由于$p(x)$是常数,因此最大后验概率估计在于求$ p(X \mu)p(\mu) $最大。

随着我们观测到越来越多的数据,MAP估计逐步逼近MLE。当我们观测到的数据越来越多的时候,我们从数据中获取的信息的置信度是越高的。

贝叶斯参数估计

在估计参数之前对参数已经有了了解称为参数的先验知识。贝叶斯估计即在估计过程中将先验知识也考虑了进去。先验知识可以是一个具体的值,也可以是取值范围(函数)。实际应用中,通常会将参数的先验知识视作一个分布。

贝叶斯估计的目的是结合参数的先验知识,使得估计出来的参数能令贝叶斯风险达到最小。简单说就是最小化贝叶斯风险。

贝叶斯风险是风险函数在θ上的期望

查看更多

ML生成模型与判别模型

24 Feb 2019 Category: 算法

监督学习的任务是对给定的输入预测相应的输出。模型的形式一般是一个判别函数或者一个条件概率分布。

监督学习模型可分为生成模型与判别模型。

判别方法:由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y X)作为预测的模型,即判别模型。基本思想是有限样本条件下建立判别函数,不考虑样本的产生模型,直接研究预测模型。
生成方法:由数据学习联合概率密度分布P(X,Y),然后求出条件概率分布P(Y X)作为预测的模型,即生成模型:P(Y X)= P(X,Y)/ P(X)。基本思想是首先建立样本的联合概率概率密度模型P(X,Y),然后再得到后验概率P(Y X),再利用它进行分类。

区别和联系

判别模型 直接学习样本的条件概率分布或者判别函数。相当于找到样本之间的最优分隔平面。

生成模型则是学习样本之间的联合分布。得到联合分布之后再利用条件概率进行分类。

生成模型可以得到判别模型,因为判别模型的依据是条件概率分布。

特点

生成方法目的是画的样本的联合分布P(X,Y),找到样本数据的真实分布,生成方法不关心样本的分类边界。生成方法的学习收敛速度更快,当存在隐变量时,仍可以用生成方法学习。

判别方法的特点:判别方法直接学习的是决策函数Y=f(X)或者条件概率分布P(Y X)。不能反映训练数据本身的特性。但它寻找不同类别之间的最优分类面,反映的是异类数据之间的差异。直接面对预测,往往学习的准确率更高。

生成算法尝试刻画数据的真实分布,然后在分类。判别模型尝试区分数据之间的差异进行划分。

常见模型

判别模型,K 近邻、感知机(神经网络)、决策树、逻辑斯蒂回归、最大熵模型、SVM、提升方法、条件随机场

生成模型,朴素贝叶斯、隐马尔可夫模型、混合高斯模型、贝叶斯网络、马尔可夫随机场

查看更多

ML的方差与偏差

23 Feb 2019 Category: 算法

偏差-方差分解可以解释学习器的泛化性能。

偏差与方差分别是用于衡量一个模型泛化误差的两个方面;

  • 模型的偏差,指的是模型预测的期望值与真实值之间的差;

  • 模型的方差,指的是模型预测的期望值与预测值之间的差平方和;

在监督学习中,模型的泛化误差可分解为偏差、方差与噪声之和。

偏差用于描述模型的拟合能力方差用于描述模型的稳定性

导致偏差和方差的原因

当模型错误,特征不足,或者训练样本少的情况下,模型输出与实际输出有很大的偏差。此时方差比较小(因为不管怎么选择样本,输出结果都很大的偏离正确结果)

当特征选取太多,模型复杂度过度的时候,偏差较小,方差比较大。不同的测试数据,测试结果会有很大的波动。

如何权衡方差偏差,找到合适的模型

一般情况,偏差方差是相互冲突的。偏差和方差的关系和模型容量(模型复杂度)相关,不同的时候导致欠拟合,过拟合的结果。

可以通过绘制学习曲线,找到方差和偏差相对平衡的模型训练程度。

在使用cross-validation的时候,如果K值选取比较高,则会使得模型过度拟合测试集,bias比较低,但是var比较高。

Bagging与Boosting在方差偏差上的区别

Bagging:多个分类器,对原样本进行有放回的抽样训练,组成集成分类器,然后使用投票等算法得到最终结果。其代表算法为随机森林。

Boosting:使用一系列分类器,对每个子分类器输出的错误值增加权重,使得直到结束。其代表算法为AdaBoost、GBDT、XGBoost。

对于Bagging而言,使用了多个不同的分类器,降低整个集成分类器的方差。对于基分类器而言,其目的更多是降低偏差,会偏向于更加复杂的分类器。

对于Boosting而言,每次都会对错误结构增加权重,因此降低了整个集成分类器的偏差。对于基分类器而言,其目的是降低方差。因此会尽可能选择简单分类器。

因此,一般情况,随机森林的树的深度往往大于GBDT的树的深度。

查看更多

PHP strpos,strstr,strpbrk这几个函数有什么区别

22 Feb 2019 Category: php

确定一个字符串是否在另一个字符串中,在PHP中有很多方法实现。strpos,strstr,strpbrk这几个函数都可以实现。那么这几个函数有什么不同呢?

strstr

strstr — 查找字符串的首次出现,别名strchar

strstr ( string $haystack , mixed $needle [, bool $before_needle = FALSE ] ) : string

返回 haystack 字符串从 needle 第一次出现的位置开始到 haystack 结尾的字符串。

如果$before_needle=true则返回第一次出现的位置前面的字符。如果字符不存在,则返回false。

如果needle不是一个字符串,那么它将被转化为整型并且作为字符的序号来使用。


if (Z_TYPE_P(needle) == IS_STRING) {
	if (!Z_STRLEN_P(needle)) {
		php_error_docref(NULL, E_WARNING, "Empty needle");
		RETURN_FALSE;
	}

	found = (char*)php_memnstr(ZSTR_VAL(haystack), Z_STRVAL_P(needle), Z_STRLEN_P(needle), ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
} else {
	if (php_needle_char(needle, needle_char) != SUCCESS) {
		RETURN_FALSE;
	}
	needle_char[1] = 0;

	found = (char*)php_memnstr(ZSTR_VAL(haystack), needle_char, 1, ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
}

if (found) {
	found_offset = found - ZSTR_VAL(haystack);
	if (part) {
		RETURN_STRINGL(ZSTR_VAL(haystack), found_offset);
	} else {
		RETURN_STRINGL(found, ZSTR_LEN(haystack) - found_offset);
	}
}

strpos

查找字符串首次出现的位置。


strpos ( string $haystack , mixed $needle [, int $offset = 0 ] ) : int

返回 needle 在 haystack 中首次出现的数字位置。查询从offset开始。offset不影响输出的数值。只用于跳过不查询的字符串。

官方文档的Note中:

如果你仅仅想确定 needle 是否存在于 haystack 中,请使用速度更快、耗费内存更少的 strpos() 函数。

以下是strpos 的源码


if (Z_TYPE_P(needle) == IS_STRING) {
	if (!Z_STRLEN_P(needle)) {
		php_error_docref(NULL, E_WARNING, "Empty needle");
		RETURN_FALSE;
	}

	found = (char*)php_memnstr(ZSTR_VAL(haystack) + offset,
		                Z_STRVAL_P(needle),
		                Z_STRLEN_P(needle),
		                ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
} else {
	if (php_needle_char(needle, needle_char) != SUCCESS) {
		RETURN_FALSE;
	}
	needle_char[1] = 0;

	found = (char*)php_memnstr(ZSTR_VAL(haystack) + offset,
						needle_char,
						1,
	                    ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
}
if (found) {
	RETURN_LONG(found - ZSTR_VAL(haystack));
} else {
	RETURN_FALSE;
}

对比两个函数的内部实现,除了offset之外,其实际差别在于strstr最后返回了字符串,strpos返回的是一个数。由于字符串返回的时候涉及到字符串复制的过程,因此会有速度和内存上的损耗。在性能上,strpos 会比strstr好一点点。

可以看一下网上的测试效果,测试效果地址

strpbrk

strpbrk — 在字符串中查找一组字符的任何一个字符。返回一个以找到的字符开始的子字符串。如果没有找到,则返回 FALSE。


strpbrk ( string $haystack , string $char_list ) : string

strpbrk() 函数在 haystack 字符串中查找 char_list 中的字符。


for (haystack_ptr = ZSTR_VAL(haystack); haystack_ptr < (ZSTR_VAL(haystack) + ZSTR_LEN(haystack)); ++haystack_ptr) {
	for (cl_ptr = ZSTR_VAL(char_list); cl_ptr < (ZSTR_VAL(char_list) + ZSTR_LEN(char_list)); ++cl_ptr) {
		if (*cl_ptr == *haystack_ptr) {
			RETURN_STRINGL(haystack_ptr, (ZSTR_VAL(haystack) + ZSTR_LEN(haystack) - haystack_ptr));
		}
	}
}

相对于上面两个函数,strpbrk相对粗暴些,直接两个循环,实现字符的查找。在性能上,应该是这三个函数垫底的了。

总结

以字符串ABCGCAC为例。

strpos 返回的是完整匹配查询字符串的第一次出现位置。strpos(‘ABCGCAC’,’CA’)返回结果是4。

strpbrk 返回的是字符列表中匹配的任意一个字符第一次出现之后的字符串。 strpbrk(‘ABCGCAC’,’CA’) 返回的内容是ABCGCAC,如果传入整数,会转成字符类型strpbrk(‘ABC13G2CAC’,’123’) 返回13G2CAC

strstr 返回的是完整匹配查询字符串第一次后出现后的字符串,strstr(‘ABCGCAC’,’CA’) 返回结果CAC

道路千万条,性能优化第一条,一点点的提升也是提升,只需要选择函数的时候合理选择。

字符串处理函数中,以下函数传入整数是当做ascii值去查找

1、strpos,stripos,strrpos,strripos 2、strstr,stristr,strrstr,strchar,strrchar

查看更多

PCA主成分分析

21 Feb 2019 Category: 算法

主成分分析(Principal components analysis,PCA) 是数据降维最重要的方法之一。主要通过找出数据的主要成分,替代原有数据。减少后续数据处理的维度。

PCA 主成分分析主要是找到一个超平面,使得原数据距离超平面尽可能的进,数据在超平面上的投影尽可能的远。如果找到这么一个超平面,则是有这个超平面坐标系表示原有数据。(变换后的维度一般提前给定,小于原有数据维度)

查看更多

SVD分解算法

20 Feb 2019 Category: 算法

奇异值分解(Singular Value Decomposition,以下简称SVD)之前接触还是在老师的课本里…。最近在看nlp相关概念知识,里面有写算法是基于svd分解的。因此重新查找资料学习svd分解。它不光可以用于降维算法中的特征分解,还可以用于推荐系统,以及自然语言处理等领域。是很多机器学习算法的基石。

特征值分解

如果 $A_{n \times n}x_{n \times 1}=\lambda x_{n \times 1}$ 则称 $\lambda$ 是矩阵 $A$的特征值,向量$x$叫做特征向量。

我们求出了矩阵A的n个特征值λ1≤λ2≤…≤λn,以及这n个特征值所对应的特征向量{w1,w2,…wn},,如果这n个特征向量线性无关,那么矩阵A就可以用下式的特征分解表示:

其中W是这n个特征向量所张成的n×n维矩阵,而Σ为这n个特征值为主对角线的n×n维矩阵

般我们会把W的这n个特征向量标准化,即满足$\parallel w_i \parallel_2=1$, 或者说$w_i^T w_i=1$,此时W的n个特征向量为标准正交基,满足$W^T W = I $,即$W^T=W^-1$, 也就是说$W$为酉矩阵。

特征值分解只能对方阵进行分解。那么对于非方阵则需要进行SVD分解。

svd分解

对于矩阵$A_{m \times n}$ ,则它的SVD分解定义为:

其中$U$是一个$m \times m$的矩阵,$\Sigma$是一个$m \times m$的矩阵,除了主对角线上的元素以外全为0,主对角线上的每个元素都称为奇异值,$V$是一个$n\times n$的矩阵。$U$和$V$都是酉矩阵,即满足$U^T U=I$,$V^T V=I$

所以$V$是$A_{m \times n}^T A_{m \times n}$的特征值分解矩阵

同理有$U$是$A_{m \times n} A_{m \times n}^T$的特征值分解矩阵

由于$\Sigma$只有主对角线非0,所以主对角线上的元素$\delta_i=\sqrt{\lambda_i}$ 其中$\lambda_i$是$A_{m \times n}^T A_{m \times n}$的特征值。

查看更多

PHP 字符串填充str_pad函数有什么不知道的

20 Feb 2019 Category: php

str_pad — 使用另一个字符串填充字符串为指定长度


str_pad ( string $input , int $pad_length [, string $pad_string = " " [, int $pad_type = STR_PAD_RIGHT ]] ) : string

该函数返回 input 被从左端、右端或者同时两端被填充到制定长度后的结果。

如果可选的 pad_string 参数没有被指定,input 将被空格字符填充,否则它将被 pad_string 填充到指定长度。

可选的 pad_type 参数的可能值为 STR_PAD_RIGHT,STR_PAD_LEFT 或 STR_PAD_BOTH。如果没有指定 pad_type,则假定它是 STR_PAD_RIGHT。

以上是文档上的说明。

那么对于以下这些情况,内部怎么处理,会得到什么样的结果呢?

1、input长度比pad_length长度大

2、pad_length给负数的时候,给0的时候呢

3、pad_string给空字符串的时候呢

4、可以填充的最大长度是什么,有没有限制

5、两边填充,给定pad_length,左边填充多少,右边填充多少

查看更多

PHP 字符串分割成数组函数explode,str_split 内部实现

15 Feb 2019 Category: php

将一个字符串分割成数组在日常开发中的应用应该是很多的。如果指定分割符,可以使用explode,如果没有分割符,可以使用split实现。 那么两个函数内部如何实现,有什么不同呢?

查看更多