1.1
表1.1的训练数据集对应的假设空间应该如下：
- 1 色泽＝＊，根蒂＝＊，敲声＝＊
- 2 色泽＝青绿，根蒂＝＊，敲声＝＊
- 3 色泽＝乌黑，根蒂＝＊，敲声＝＊
- 4 色泽＝＊，根蒂＝蜷缩，敲声＝＊
- 5 色泽＝＊，根蒂＝硬挺，敲声＝＊
- 6 色泽＝＊，根蒂＝稍蜷，敲声＝＊
- 7 色泽＝＊，根蒂＝＊，敲声＝浊响
- 8 色泽＝＊，根蒂＝＊，敲声＝清脆
- 9 色泽＝＊，根蒂＝＊，敲声＝沉闷
- 10 色泽＝青绿，根蒂＝蜷缩，敲声＝＊
- 11 色泽＝青绿，根蒂＝硬挺，敲声＝＊
- 12 色泽＝青绿，根蒂＝稍蜷，敲声＝＊
- 13 色泽＝乌黑，根蒂＝蜷缩，敲声＝＊
- 14 色泽＝乌黑，根蒂＝硬挺，敲声＝＊
- 15 色泽＝乌黑，根蒂＝稍蜷，敲声＝＊
- 16 色泽＝青绿，根蒂＝＊，敲声＝浊响
- 17 色泽＝青绿，根蒂＝＊，敲声＝清脆
- 18 色泽＝青绿，根蒂＝＊，敲声＝沉闷
- 19 色泽＝乌黑，根蒂＝＊，敲声＝浊响
- 20 色泽＝乌黑，根蒂＝＊，敲声＝清脆
- 21 色泽＝乌黑，根蒂＝＊，敲声＝沉闷
- 22 色泽＝＊，根蒂＝蜷缩，敲声＝浊响
- 23 色泽＝＊，根蒂＝蜷缩，敲声＝清脆
- 24 色泽＝＊，根蒂＝蜷缩，敲声＝沉闷
- 25 色泽＝＊，根蒂＝硬挺，敲声＝浊响
- 26 色泽＝＊，根蒂＝硬挺，敲声＝清脆
- 27 色泽＝＊，根蒂＝硬挺，敲声＝沉闷
- 28 色泽＝＊，根蒂＝稍蜷，敲声＝浊响
- 29 色泽＝＊，根蒂＝稍蜷，敲声＝清脆
- 30 色泽＝＊，根蒂＝稍蜷，敲声＝沉闷
- 31 色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
- 32 色泽＝青绿，根蒂＝蜷缩，敲声＝清脆
- 33 色泽＝青绿，根蒂＝蜷缩，敲声＝沉闷
- 34 色泽＝青绿，根蒂＝硬挺，敲声＝浊响
- 35 色泽＝青绿，根蒂＝硬挺，敲声＝清脆
- 36 色泽＝青绿，根蒂＝硬挺，敲声＝沉闷
- 37 色泽＝青绿，根蒂＝稍蜷，敲声＝浊响
- 38 色泽＝青绿，根蒂＝稍蜷，敲声＝清脆
- 39 色泽＝青绿，根蒂＝稍蜷，敲声＝沉闷
- 40 色泽＝乌黑，根蒂＝蜷缩，敲声＝浊响
- 41 色泽＝乌黑，根蒂＝蜷缩，敲声＝清脆
- 42 色泽＝乌黑，根蒂＝蜷缩，敲声＝沉闷
- 43 色泽＝乌黑，根蒂＝硬挺，敲声＝浊响
- 44 色泽＝乌黑，根蒂＝硬挺，敲声＝清脆
- 45 色泽＝乌黑，根蒂＝硬挺，敲声＝沉闷
- 46 色泽＝乌黑，根蒂＝稍蜷，敲声＝浊响
- 47 色泽＝乌黑，根蒂＝稍蜷，敲声＝清脆
- 48 色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷
- 49 Ø
加入 1 号数据，(色泽＝青绿、根蒂＝蜷缩、敲声＝浊响) 好瓜，剩下
- 1 色泽＝＊，根蒂＝＊，敲声＝＊
- 2 色泽＝青绿，根蒂＝＊，敲声＝＊
- 4 色泽＝＊，根蒂＝蜷缩，敲声＝＊
- 7 色泽＝＊，根蒂＝＊，敲声＝浊响
- 10 色泽＝青绿，根蒂＝蜷缩，敲声＝＊
- 16 色泽＝青绿，根蒂＝＊，敲声＝浊响
- 22 色泽＝＊，根蒂＝蜷缩，敲声＝浊响
- 31 色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
加入 4 号数据，(色泽＝乌黑、根蒂＝稍蜷、敲声＝沉闷) 坏瓜，剩下
- 2 色泽＝青绿，根蒂＝＊，敲声＝＊
- 4 色泽＝＊，根蒂＝蜷缩，敲声＝＊
- 7 色泽＝＊，根蒂＝＊，敲声＝浊响
- 10 色泽＝青绿，根蒂＝蜷缩，敲声＝＊
- 16 色泽＝青绿，根蒂＝＊，敲声＝浊响
- 22 色泽＝＊，根蒂＝蜷缩，敲声＝浊响
- 31 色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
成功构建版本空间
1.2
不会
- 48
从网上抄到一份代码(不过我觉得可以用动态规划试一试§(*￣▽￣*)§)
---------------------
import numpy as np
import itertools as it
def get_18_from_trible(trible): #把三维向量变为代表特征的18维向量
a = np.zeros([2,3,3])
a1 = trible[0]
a2 = trible[1]
a3 = trible[2]
if a1 == 3: #对于第一种属性为"*"的情况
a1 = [1,2]
else:
a1 = [a1]
if a2 == 4: #对于第二种属性为"*"的情况
a2 = [1,2,3]
else:
a2 = [a2]
if a3 == 4: #对于第三种属性为"*"的情况
a3 = [1,2,3]
else:
a3 = [a3]
#print (a1,a2,a3)
#print(a)
for m1 in a1:
for m2 in a2:
for m3 in a3:
a[m1-1][m2-1][m3-1] = 1
return a #得到了一个18维向量（0/1二值），代表18种特征情况
def turn_48_to_trible(num):
# num in [0,47]，把一个小于48的数字对应到一个三维数组中
for i in range(3):
for j in range(4):
for k in range(4):
if i*16 + j*4 + k == num:
return [i+1,j+1,k+1]
def from_48_to_18(num): #把0-47的某个数唯一对应到某个18维向量
a = turn_48_to_trible(num)
b = get_18_from_trible(a)
return b
def main(k):
rset=[]
for i in it.combinations(range(48),k):
#开始对48取k的组合数进行穷举，i是一个k元数组
subset=[]
for j in range(k):
p = from_48_to_18(i[j])
subset.append(p)
subset = np.array(subset)
subset = subset.any(axis=0) # 这是去除冗余操作！！！
subset = np.reshape(subset,[18])
subset = subset.tolist() #从array变为list方便接下来的操作
count = 0
for i in range(18):
count += 2 ** i *subset[i]
#这是简单的一一映射，18维二值向量可以一一对应到1~2^18的某个数
subset = count
length = len(rset)
rset.append(subset)
if len(rset) % 100000 == 0 :
print(len(rset)) #为了证明程序确实在运行hhh，这个可以注释掉
if len(rset) > 5000000:
rset = list(set(rset)) #set是集合，是对rset数组进行去重！
#设置500W上限为了防止set操作时数组长度太长导致程序崩掉
rset = list(set(rset)) #最终set操作一下得到最终结果
#rset = list(set(tuple(t) for t in rset))
print( "%d ： %d examples"%(k,len(rset)))
# main(k) 运行即得k个析取范式的结果。注：当k≥9时花费时间过长！目前没法解决！
1.3
- 少数服从多数，如果统计相同标签下分类数，取占比多的
1.4
前面忘了，中间忘了，总之成立
E_{\text {ote }}\left(\mathfrak{L}_{a} \mid X, f\right) &=& \sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \ell(h(\boldsymbol{x}), f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right)
\\
&=& \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h}P\left(h \mid X, \mathfrak{L}_{a}\right) \sum_{f} \ell(h(\boldsymbol{x}), f(\boldsymbol{x}))
\\
&=& \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h}P\left(h \mid X, \mathfrak{L}_{a}\right) A
1.5
- NLP，关键词检索
- 图像识别：以图搜图
- 爬虫后数据分析，网页排序
- 文字搜图
- 带歧义的搜索？