分类目录归档:未分类

Something to Learn

记录一下自己需要看但是还没有看的论文、书籍、课程、notes,毕竟自己可能会忘记或者懒惰:)

Book

Learning from datawhy推荐的入门书籍,讲的貌似是Learning theory
The Study of Languagewhy推荐的语言学教材
西瓜书没什么好说的,肯定要翻翻
PRML要看
花书DL理论
Reinforcement Learning An IntroductionRL

Paper

Reinforced Mnemonic Reader for Machine Reading ComprehensionIJCAI 2018Machine Reading Comprehension、Reinforcement Learning、Reattention

蓄水池抽样

了解了一下蓄水池抽样。
它可以在O(n)的时间内对n个数据进行等概率的随机抽取k个样本,并且适用于n不断增长(就是n未知的情况下),或者n很大(不能放入内存的情况)。
算法的步骤就是:
假设要等概率的抽取样本数为k。那么首先把n个数列中的前k个元素放入到一个长度为k的数组中,称为蓄水池。然后对于之后的第k+1个元素到第n个元素中,第i个元素的时候,生成一个在[1,i]之间的随机数j,如果j小于k,就把蓄水池中的第j个元素换成第i个。
通过数学归纳法证明这样做可以让每个元素都有k/n的概率进入蓄水池。
首先,对于任意的 i,第 i 个元素进入蓄水池的概率为 k / i;而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。
那么假设在第(i-1)轮,任意一个元素进入蓄水池的概率均为k/(i-1)。那么在第i轮其被替换概率为1/i,那么继续留在蓄水池的概率为k/(i-1)*(1-1/i)=k/i。得证。
写了个做实验的代码,的确可以说是非常随机了.