【机器学习第二课】P12例2

反复看了两遍,似懂非懂。似乎确实只有这一种合理解释。但为什么就能够这样估计呢?是最大似然估计?

Eric_Jiang - 我是小象的搬运工!!!

赞同来自: liangrx06 fish sunyue

你是指为什么概率是2^-k是么? 我的理解是,对于一个字符串hash为正整数,存在k个可能被hash后得到的数,所以对于任意k个数中的一个,有两种情况,能够得到hash的映射,或者no.因此可能出现的所有情况为2^k,hash(<string>)=k只有一种出现可能,因此概率为2^-k

liangrx06

赞同来自:

我一直没有太想明白的有两点: 一是你说的为什么概率是2^-k的问题,也就是猜不到hash函数是如何映射的(虽然这个题没有必要知道如何映射,只要关心概率,但知道了我才更明白这个题的合理性); 二是PPT中给出的解答有点最大似然函数取最值的意思,但我总觉得这样做怪怪的,换句话说能不能更清楚的解释下为什么可以这样处理?有哪些理论基础? 先谢谢Eric_Jiang

Eric_Jiang - 我是小象的搬运工!!!

赞同来自:

@liangrx06 你的第二个问题是指问题为什么转化成正整数10出现过一次是么?先转化为整数10曾经出现过,因为整数10是最大的,而且是正整数,所以我确定了出现正整数的范围1 -10 。这是为了确定所有可能出现的形况。 由于不确定出现正整数次数,需要进一步简化问题,在高数极限中涉及到函数增减速率的问题,对于10 出现的次数假定为n, 所有可能的形况为2^10, 后者增长的速率远远大于前者,近似为0的。也就是在n足够大的情况下lim n/(2^n) =0。在这里整数10 出现多次(并不会太多,10是最大的,肯定远离均值,也就是出现10的概率不会太大。)所以 n/2^10 与1/2^10是近似的。但后者简化了问题。

邹博 - 计算机科学博士,深谙机器学习算法原理

赞同来自:

大家的讨论已经非常棒了。 这个解法的确跟最大似然估计没有关系,只是二项分布而已。我举这个题目的意思更多的是为了展示逐步把实际问题转化成常见分布的过程,另外,这个解析是我个人给出的解法,虽然我是尽我所能做的解析,但不肯定100%正确。如果有疑问,希望继续提问。   此外,题目中“将任一字符串非均匀映射到正整数k,概率为2^(-k)”仅仅是题目的描述,事实上,这个表述里面的“任意字符串”就是混淆视听的。如果非要纠结这个Hash函数是如果构造的,一种可行的办法是:在实际构造中,直接以概率2^(-k)返回k即可。

liangrx06

赞同来自:

嗯,尽管不完全接受二位的解释,但理解起来好了一些,谢谢   但是:原题中:现有字符串集合S,其元素经映射后,得到的最大整数为10。 映射是确定的,而这个确定的集合S难道不应该看成hash函数定义域的一个样本?而hash函数的定义域才应该看成总体? 特意搜了一下样本的定义:研究中实际观测或调查的一部分个体称为样本(sample),研究对象的全部称为总体。   又翻开课件看了一下最大似然的定义应用,确实与这个题目不一样。最大似然估计是根据样本求概率,而这个题目概率已知,求得是集合的元素数量。那么我现在就无可救药的理解成了这个题就是根据概率反过来求(或者说猜想)样本的个数。 请把我拍醒吧!!

雁字回时

赞同来自:

我理解这里和实际的字符串没有任何关系,10出现一次,实际s里元素的个数可能是1个,可能是10000个,只是10出现的概率是1/1024,所以最有可能的情况是s的个数是1024.

要回复问题请先登录注册