sin(x)

Category: 读书笔记

机器学习:习题笔记(一)

现在好像什么研究方向都会用到机器学习,所以在大四养老期间学习一下周志华老师的《机器学习》,把不太难的题目写一下。

第1章 绪论

  • 1.1 表 1.1 中若只包含编号为 1 和 4 的两个样例,试给出相应的版本空间。

由于训练数据更少,所以版本空间会更大。

(色泽=青绿;根蒂=*;敲声=*)
(色泽=*;根蒂=蜷缩;敲声=*)
(色泽=*;根蒂=*;敲声=浊响)
(色泽=青绿;根蒂=蜷缩;敲声=*)
(色泽=青绿;根蒂=*;敲声=浊响)
(色泽=*;根蒂=蜷缩;敲声=浊响)
(色泽=青绿;根蒂=蜷缩;敲声=浊响)

Continue reading

统计学习方法:习题笔记

花了一些时间刷了一遍李航博士的《统计学习方法》,于是就有了一篇课后习题解答。由于自己的智商又低数学又差,很多难度较大的习题实在没有能力完成了。

第1章 统计学习方法概论

  • 1.1 说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为0与1的随机变昼上的概率分布。假设观测到伯努利模型n次独立的数据生成结果,其中k次的结果为1,这时可以用极大似然估计或贝叶斯估计来估计结果为1的概率。

Continue reading

算法笔记:后缀自动机

本文改编自MAXimal :: algo :: Суффиксный автомат. Построение и применения的Google机翻版(什么玩意儿)

后缀自动机是一个处理字符串相关问题很有用的工具,例如检查一个字符串在另外一个字符串中是否出现过,计算一个字符串中不同子串的数量——它们都可以在线性时间内被解决。

从直观上看,后缀自动机保存着所有子串的信息,对于长度为n的字符串来说,它的后缀自动机只需要的空间,同时构造它的时间复杂度为

Continue reading

算法笔记:后缀数组

本文改编自斯坦福大学CS 97SI: Introduction to Programming Contests的教学材料Suffix arrays – a programming contest approach

在算法竞赛中经常会遇到很多有关字符串子串的问题,或者是字符串后缀的问题,因此也就需要一种高效的数据结构及算法来处理这个问题。

什么是后缀数组?

为了更好地理解后缀数组,我们先来了解一种特殊的trie——后缀trie。一棵trie树是用来储存字符串的数据结构,其中每一个节点有和字母表大小一样多的孩子节点。本文的例子中只考虑小写字母,那么每个节点也就至多有26个孩子节点。每一条从父节点到孩子节点标注上一个字符,从根节点到叶子节点路径上标注的字符组合起来就是trie中保存着的一个字符串。显然地,在trie中查找一个字符串只需要时间复杂度(m是字符串长度),叟搜索时间和其中的字符串数量无关,这是一个实现字典的绝佳数据结构。

Continue reading

算法导论:计算几何

对于几何相关的计算,中学的数学已经涉及了一部分。对于两个有向线段a和b,如何判断线段a在线段b的顺时针方向还是逆时针方向,两个线段是否相交。我们可以通过计算两个线段的斜率来判断它们之间的相对方向,使用方程组来求解两个线段是否有交点。这些方法计算机也可以使用,但是计算机计算很大的特点就是精度有限,计算斜率和解方程组都会有除法运算,这样的方法是不够好的。

除了中学接触的几何问题,还有线段集合的相交判断,以及寻找凸包等问题。完整代码以及测试代码位于Gist

Continue reading

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑