习题原文链接:minfanphd
1. 集合
1.1 朴素的定义
Definition 1. A set is a collection of elements, and an element is an object in a set.
集合的两种表示法: a) 列举法,如: = ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) , , , , , , , , ,![\small 9](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%209) ; b) 谓词法,如: = ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) ∣ mod = ![\small 1](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%201) .
习题1:{0,1,{0,1},{1,2}}有几个元素?机器学习中,这类形式的集合有什么优点和缺点?
上述集合有4个元素,分别是0、1、{0,1}、{1,2} ,其中元素{0,1}为一个集合,它的元素为0、1,元素{1,2}也为一个集合,它的元素为1、2。优点:集合中的元素是确定的,且集合可以容纳多种类型的数据。缺点:判断一个对象是否为指定集合的元素需一一对比;不同的维度出现重复的数据,可能意味着同一对象的重复表达,给问题的解决增添复杂。
1.2 基数
集合 的基数,即其元素的个数,记为 | |,读的时候,需读成“the cardinality of A”.
习题2:∅ 的基数是多少? {∅} 呢?
∅ 是没有元素的集合,因此∅的基数为0。{∅} 不是空集,该集合里有一个∅元素,因此{∅} 的基数为1。
1.3 笛卡尔积
Definition 2. The Cartesian product of is = ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) ![\small \(](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%28) ![\small x_n](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20x_n) ![\small A_n](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20A_n) . 笛卡尔积不满足结合律,如 ={ }, = { }, = { }.那么 = {(![\small a](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20a) )}, ( ) = ((![\small a](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20a) ) ), 同理 ( ) = (![\small a](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20a) (![\small b](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20b) )).
数据集的两种表示法: a) 矩阵表示法:记 = ![\small \(](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%28) ![\small x_1](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20x_1) , ![\small x_n](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20x_n) ,则 , 可支持矩阵的相乘,易于表示加权等操作; b) 集合与向量混合法:记 = {![\small x_1](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20x_1) , },其中 ,元素可随意交换顺序,但不允许两个元素相同。
1.4 幂集
Definition 2. The power set of is given by = {![\small B](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20B) ![\small |](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7C) }. 例: = {1,2,3}, = { ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.幂集里的每个元素都是一个集合,另外,![\small |](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7C) ![\small 2^A](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%202%5EA) = = = 8.
2. 二元关系
Definition 3. Let and be two sets. Any ![\small R](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20R) is a binray relation. 例如二元关系![\small :=](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%3A%3D) ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) ![\small x=y](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20x%3Dy) .
3. 函数
Definition 4. Let ![\small V_1](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20V_1) be the domain of conditional attribute , respectively, and be the set of classes. A classifier is a function ![\small V_m](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20V_m) ![\small \rightarrow](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Crightarrow) . 需注意:函数的定义域、值域都是集合;对于函数定义域上的每个点,均在值域中有一个唯一的点与之对之,反之不然。因此,函数的逆函数不一定存在,若逆函数存在,就是一一映射。
习题 5: 多标签学习中, 输出为一个向量,相应的学习器算不算函数呢?
算函数。在多标签学习的学习器中,输入数据形式一定(如图像、音频),输出数据为向量,映射关系是一定的,符合函数的性质:定义域上的每个点,均在值域中有一个唯一的点与之对之的关系。
4. 元组
需注意:元组用 ;向量既可用 , 也可用 ;集合用![\small {}](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7B%7D) .
元组的各个部分,既可以是个集合,也可以是一个基本元素。图 (Graph) 就是最经典的二元组,因为一个图由两个元素确定,即顶点 和边 . a) 定义有向图: A directed graph is a tuple = , where ![\small V=](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20V%3D) ![\small {}](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7B%7D) ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) is the set of nodes, and is the set of edges.
b) 定义无向图: An undirected graph is a tuple = , where ![\small V=](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20V%3D) ![\small {}](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7B%7D) ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) is the set of nodes, is the set of edges, and ![\small v_j](https://latex.csdn.net/eq?%5Csmall%20v_j) iff ![\small v_i](https://latex.csdn.net/eq?%5Csmall%20v_i) (iff 为if and only if).
c) 定义带权有向图: A weighted directed graph is a tuple , where ![\small V=](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20V%3D) ![\small {}](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%7B%7D) ![\small \{](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B) is the set of nodes, and ![\small \{0](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B0) is the edge weight function. 表示正实数, 不包括 0, 所以只有把 0 加进来, 表示非负实数;若限定 只能取0或1,即 ,带权有向图就退化为有向图。
习题 6: 元组只能表达对象的数据部分, 还是可以完整地表达? 用一个具体的程序来说明.
可以完整的表达一个对象。在Python中,有多种方式表示对象,元组只是其中的一个。
# 对象属性为name、age、height
>>> student=('jack',18,170.0)
>>> student
('jack', 18, 170.0)
>>> student[1]
18
# tuple不能修改
>>> student[2]=175.0
TypeError: 'tuple' object does not support item assignment
5. 字母表、二叉树、树
5.1 字母表
Definition 11. An alphabet is a set of characters. 常见的字母表包括: = {0,1}, = {a,...,z}.
字母表的正闭包定义如下: Definition 12. The positive closure of alphabet is given by = .若 ={0,1}, 那么 = {0,1,00,01,10,11,000, }, 若 = { , }, 那么 = { , , , , , , , }.
字母表的克林闭包(考虑空串 )定义如下: Definition 13. The Cling closure of alphabet is given by = = { } .字母表克林闭包的元素,就称为字符串.
5.2 二叉树
习题 7: 定义二叉树.
参照闵老师的定义:https://blog.csdn.net/minfanphd/article/details/116245485?spm=1001.2014.3001.5501初始版本:Let = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \mathrm{r}](https://latex.csdn.net/eq?%5Csmall%20%5Cmathrm%7Br%7D) be the alphbet and be a null node. A binary tree is a triple = ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) , where = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes, is the root, and c ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \phi](https://latex.csdn.net/eq?%5Csmall%20%5Cphi) ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \phi](https://latex.csdn.net/eq?%5Csmall%20%5Cphi) satisfying a) ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ![\small \mathrm{l}](https://latex.csdn.net/eq?%5Csmall%20%5Cmathrm%7Bl%7D) = ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ; b) ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small r](https://latex.csdn.net/eq?%5Csmall%20r) , st. ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ; c) ![\small \forall_v\in V,](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Cforall_v%5Cin%20V%2C) 打磨版本:Let = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \mathrm{r}](https://latex.csdn.net/eq?%5Csmall%20%5Cmathrm%7Br%7D) be the alphbet and be a null node. A binary tree is a triple = ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) , where = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes, is the root, and c ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \phi](https://latex.csdn.net/eq?%5Csmall%20%5Cphi) ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \phi](https://latex.csdn.net/eq?%5Csmall%20%5Cphi) satisfying , st. ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ; 若仅保留初始版本中的 b), 会出现 bug. 反例: = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \mathrm{r}](https://latex.csdn.net/eq?%5Csmall%20%5Cmathrm%7Br%7D) , ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = , ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = .![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = , 即从 读入空串到自己.
习题 8: 定义带权无向图.
A weighted undirected graph is a tuple = ![\small (](https://latex.csdn.net/eq?%5Csmall%20%28) ![\small w](https://latex.csdn.net/eq?%5Csmall%20w) , where = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes, ![\small \subseteq](https://latex.csdn.net/eq?%5Csmall%20%5Csubseteq) is the set of edges, ![\small \{0](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5C%7B0) is the edge weight function, and ![\small v_j](https://latex.csdn.net/eq?%5Csmall%20v_j) iff ![\small v_i](https://latex.csdn.net/eq?%5Csmall%20v_i) .
5.3 树
习题 9. 考虑 ∅, 重新写 Definition 7 以解决其存在的问题, 见其讨论 d).
Definition 7. A tree is a triple = ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ![\small p](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20p) , where = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes, is the root, and ![p:](https://latex.csdn.net/eq?p%3A) ![\{r\}](https://latex.csdn.net/eq?%5C%7Br%5C%7D) ![\rightarrow](https://latex.csdn.net/eq?%5Crightarrow) satisfying a) , ![\small \forall](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Cforall) , ; b) ![\small \forall](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Cforall) , , st. = ; c) , . 此定义与 Amaris-Bunny讨论、交流完成,如有错误,还请指正!
6. 自动机描述
确定的有穷状态自动机定义如下: A deterministic finite state automata (DFA) is a 5-tuple = ![\small (](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%28) ![\small f](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20f) , where a) is the alphabet; b) is the set of states; c) is the start state; d) is the set of terminal states; e) ![\small \Sigma^*](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5CSigma%5E*) ![\small \rightarrow](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Crightarrow) is the transition function. Any is accepted by the automata iff ![\small f](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20f) .
说明: a) DFA 的开始状态只有一个, 因此为 的元素; b) DFA 的终止状态可以有多个, 因此为 的子集; c) DFA 的基础目标是看状态 是否合法 (被接受).
6.1 二叉树的自动机描述
如果将二叉树看作是一个自动机, 它包括如下几个方面: a) 有一个字母表, 即![(](https://latex.csdn.net/eq?%28) ![\mathrm{r}](https://latex.csdn.net/eq?%5Cmathrm%7Br%7D) ; b) 有一个状态集合, 包括所有节点与空节点; c) 有一个开始状态, 即根节点 ; d) 有一个终止状态, 即空节点 ; e) 从任一状态读入任一字母, 确定地转移到下一状态 (可以是自己), 这个用状态转移函数来描述. 通过分析可以看出, 二叉树在其中 4 点都与自动机完全契合, 唯一有问题的是终止状态. 二叉树本身没有一个“判断字符串是否合法”的目标,因此不存在终止状态. 但它又有一个特殊的状态, 即 .
习题 3.1 模仿自动机的样子来重新定义二叉树.
A binary tree is a 6-tuple = ![\small (](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%28) ![\small f](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20f) , where a) = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small \mathrm{r}](https://latex.csdn.net/eq?%5Csmall%20%5Cmathrm%7Br%7D) is the alphabet; b) = ![V](https://latex.csdn.net/eq?V) ![\small \cup](https://latex.csdn.net/eq?%5Csmall%20%5Ccup) is the set of states,and is a null node; c) = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes; d) is the start state(root); e) is the special terminal states; f) ![\small \Sigma^*](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5CSigma%5E*) is the transition function, satisfying , st. ![\small c](https://latex.csdn.net/eq?%5Csmall%20c) ![\small \(](https://latex.csdn.net/eq?%5Csmall%20%5C%28) ) = ;
6.2 树的自动机描述
如果将树看作是一个自动机, 它包括如下几个方面: a) 有一个状态集合, 包括所有节点与空节点; b) 有多个开始状态, 即 ; c) 有一个终止状态, 即 ; d) 树中所有节点有0或多个后继,,即父节点的分支数目不确定,无法通过父节点准确的找到相应的子节点,而每个子节点有且只有唯一的一条路径到达父节点.
习题3.2 模仿自动机的样子来重新定义树.
A tree is a 5-tuple = ![\small (](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%28) ![p](https://latex.csdn.net/eq?p) , where a) = ![V](https://latex.csdn.net/eq?V) ![\small \cup](https://latex.csdn.net/eq?%5Csmall%20%5Ccup) is the set of states,and is a null node; a) = ![\small \{](https://latex.csdn.net/eq?%5Csmall%20%5C%7B) ![\small v_n](https://latex.csdn.net/eq?%5Csmall%20v_n) is the set of nodes, and is the set of start states; b) is the terminal state; c) is a special state; d) ![\small \Sigma^*](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5CSigma%5E*) is the transition function, satisfying![\small \forall](https://latex.csdn.net/eq?%5Cbg_white%20%5Csmall%20%5Cforall) , , st. = ;
如有错误,还请指正!
|