1.1 表1.1中若只包含編號(hào)為1和4的兩個(gè)樣例囊咏，試給出相應(yīng)的版本空間。
解：對(duì)應(yīng)的樣本數(shù)據(jù)集如下
色澤有3（青綠，烏黑梅割，* ）種取值霜第，根蒂有3(蜷縮，稍蜷户辞，* ）種取值泌类，敲聲3（濁響，沉悶底燎，* ）種刃榨，那么假設(shè)規(guī)模一共有
（考慮空集)，28種
對(duì)應(yīng)的版本空間為7種
分別為
1.色澤=青綠 根蒂=蜷縮 敲聲=濁響
2.色澤=青綠 根蒂=蜷縮 敲聲= *
3.色澤=青綠 根蒂=* 敲聲= 濁響
4.色澤= * 根蒂= 蜷縮 敲聲= 濁響
5.色澤= * 根蒂= * 敲聲= 濁響
6.色澤= * 根蒂= 蜷縮 敲聲= *
7.色澤= 青綠 根蒂= * 敲聲= *
1.2 與使用單個(gè)合取式來進(jìn)行假設(shè)表示相比双仍，使用“析合范式”將使得假設(shè)空間具有更強(qiáng)的表示能力枢希。
例如：
好瓜←→（(色澤=)∧(根蒂=蜷縮)∧(敲聲=)）∨（(色澤=烏黑)∧(根蒂=*)∧(敲聲=沉悶)）會(huì)把“（(色澤=青綠)∧(根蒂=蜷縮)∧(敲聲=清脆)）”以及“（(色澤=烏黑)∧(根蒂=硬挺)∧(敲聲=沉悶)）”都分類為“好瓜”。若使用最多包含k個(gè)合取式的析合范式來表達(dá)表1.1西瓜分類問題的假設(shè)空間朱沃，試估算共有多少種可能的假設(shè)苞轿。
解：西瓜的三個(gè)不同屬性的特征分別記為(A1,A2),(B1,B2,B3),(C1,C2,C3)，這樣一共有2x3x3,18種不同的組合为流，如果將屬性泛化考慮 進(jìn)去呕屎，(A1,A2让簿，* ),(B1,B2,B3敬察，* ),(C1,C2,C3，* )那么一共就有3x4x4,48種不同的組合尔当。
48種情況分別包括
基本組合：18種
一個(gè)屬性泛化假設(shè)：2x3+3x3+2x3,21種
兩種屬性泛化假設(shè)：2+3+3莲祸，8種
三個(gè)屬性泛化假設(shè)：1種
如果不考慮冗余則一共有
但是書本中提醒了還要考慮冗余情況，情況就沒有那么簡單了椭迎。
首先我們可以很輕松確定k的上界锐帜，k的最大取值為18，能表達(dá)最小的假設(shè)空間為18種基本組合畜号，如果加入第19種的話缴阎，那么必然會(huì)產(chǎn)生表達(dá)冗余。因此k的取值范圍為【1简软，18】
考慮最極端也最簡單的情況蛮拔，當(dāng)k=1時(shí)，相當(dāng)于在48個(gè)種排列組合取一種痹升，必然不會(huì)有冗余的考慮即
k=1時(shí)建炫，有48種
k=18時(shí)，有1種
中間的2~17的取值范圍考慮起來會(huì)相當(dāng)復(fù)雜疼蛾，一種樸素的思想就算用計(jì)算機(jī)暴力迭代肛跌，遍歷所有的排列組合，然后判斷他們是否冗余。但是在計(jì)算機(jī)表達(dá)上也是有一定的轉(zhuǎn)換
一 衍慎、首先構(gòu)造一個(gè)18x48的矩陣來表達(dá)數(shù)據(jù)转唉，比如
100000000000000000 表示（青綠，蜷縮西饵，濁響）
111111111111111111 表示 （ * 酝掩， * ，*）
二眷柔、用itertools.combinations方法放回所有的排列組合迭代器
三期虾、將每一種迭代結(jié)果相加(析取運(yùn)算），存放在一個(gè)數(shù)組中驯嘱，該數(shù)組的作用相當(dāng)于一個(gè)set镶苞，不允許出現(xiàn)重復(fù)的元素
代碼
import itertools
import time
#將數(shù)存儲(chǔ)為數(shù)組
def method(value):
# 將字符串變成數(shù)字列表，使其具有數(shù)字加法運(yùn)算
result = []
for i in range(len(value)):
result.append(eval(value[i]))
return result
#用類表示編碼鞠评，并定義重載的運(yùn)算符 + 為析取
class WMcode:
val = ''
len = 0
def __init__(self, strv):
self.val = method(strv)
def __add__(self,other): #析取運(yùn)算
strv = []
for i in range(len(self.val)):
addr = self.val[i]+other.val[i]
if addr >= 2:
addr = 1
strv.append(str(addr))
return WMcode(strv)
#對(duì)48中假設(shè)進(jìn)行編碼
nodes = [WMcode('100000000000000000'),WMcode('010000000000000000'),WMcode('001000000000000000'),
WMcode('000100000000000000'),WMcode('000010000000000000'),WMcode('000001000000000000'),
WMcode('000000100000000000'),WMcode('000000010000000000'),WMcode('000000001000000000'),
WMcode('000000000100000000'),WMcode('000000000010000000'),WMcode('000000000001000000'),
WMcode('000000000000100000'),WMcode('000000000000010000'),WMcode('000000000000001000'),
WMcode('000000000000000100'),WMcode('000000000000000010'),WMcode('000000000000000001'),
WMcode('100000000100000000'),WMcode('010000000010000000'),WMcode('001000000001000000'),
WMcode('000100000000100000'),WMcode('000010000000010000'),WMcode('000001000000001000'),
WMcode('000000100000000100'),WMcode('000000010000000010'),WMcode('000000001000000001'),
WMcode('111000000000000000'),WMcode('000111000000000000'),WMcode('000000111000000000'),
WMcode('000000000111000000'),WMcode('000000000000111000'),WMcode('000000000000000111'),
WMcode('100100100000000000'),WMcode('010010010000000000'),WMcode('001001001000000000'),
WMcode('000000000100100100'),WMcode('000000000010010010'),WMcode('000000000001001001'),
WMcode('111000000111000000'),WMcode('000111000000111000'),WMcode('000000111000000111'),
WMcode('100100100100100100'),WMcode('010010010010010010'),WMcode('001001001001001001'),
WMcode('111111111000000000'),WMcode('000000000111111111'),WMcode('111111111111111111')]
# （青綠茂蚓，蜷縮，濁響） （青綠剃幌，稍蜷聋涨，濁響） （青綠，硬挺负乡，濁響）
# （青綠牍白，蜷縮，清脆） （青綠抖棘，稍蜷茂腥，清脆） （青綠，硬挺切省，清脆）
# （青綠最岗，蜷縮，沉悶） （青綠朝捆，稍蜷般渡，沉悶） （青綠，硬挺芙盘，沉悶）
# （烏黑驯用，蜷縮，濁響） （烏黑何陆，稍蜷晨汹，濁響） （烏黑，硬挺贷盲，濁響）
# （烏黑淘这，蜷縮剥扣，清脆） （烏黑，稍蜷铝穷，清脆） （烏黑钠怯，硬挺，清脆）
# （烏黑曙聂，蜷縮晦炊，沉悶） （烏黑，稍蜷宁脊，沉悶） （烏黑断国，硬挺，沉悶）
# （*榆苞，蜷縮稳衬，濁響） （*，稍蜷坐漏，濁響） （*薄疚，硬挺，濁響）
# （*赊琳，蜷縮街夭，清脆） （*，稍蜷躏筏，清脆） （*板丽，硬挺，清脆）
# （*寸士，蜷縮檐什，沉悶） （*碴卧，稍蜷弱卡，沉悶） （*，硬挺住册，沉悶）
# (青綠婶博，*，濁響) （青綠荧飞，*凡人，清脆） （青綠，*叹阔，沉悶）
# (烏黑挠轴，*，濁響) （烏黑耳幢，*岸晦，清脆） （烏黑欧啤，*，沉悶）
# (青綠启上，蜷縮邢隧，*) （青綠，稍蜷冈在，*） （青綠倒慧，硬挺，*）
# (烏黑包券，蜷縮纫谅，*) （烏黑，稍蜷溅固，*） （烏黑系宜，硬挺，*）
# (*,*,濁響) (*,*,清脆) (*,*,沉悶)
# (*,蜷縮发魄，*) (*,稍蜷,*) (*,硬挺,*)
# (青綠盹牧，*，*) （烏黑励幼，*汰寓，*） （*，*苹粟，*）
#合取式數(shù)量k
for k in [1,2,3,4]:
#存儲(chǔ)最終結(jié)果的集合A
A = []
time_start=time.time() #開始計(jì)時(shí)
comb = list(itertools.combinations(nodes,k))
for i in range(len(comb)):
WMadd = WMcode('000000000000000000')
for j in range(k):
WMadd = WMadd + comb[i][j]
for allval in A: #若A中已經(jīng)存在當(dāng)前假設(shè)有滑，則舍去，因?yàn)檫@是亢余
if WMadd.val == allval.val:
break
else:
A.append(WMadd)
time_end=time.time() #結(jié)束計(jì)時(shí)
print("K={},一共有{}組合".format(str(k),str(len(A))))
print('花費(fèi)時(shí)間',time_end-time_start)
最后由于這是一種規(guī)模是指數(shù)級(jí)的迭代嵌削，當(dāng)k規(guī)模大的時(shí)候就跑不動(dòng)了毛好，看圖，當(dāng)k的取值為4的時(shí)候就已經(jīng)需要10多分鐘了
1.3 若數(shù)據(jù)包含噪聲苛秕，則假設(shè)空間中有可能不存在與所有訓(xùn)練樣本都一致的假設(shè)肌访。在此情形下，試設(shè)計(jì)一種歸納偏好用于假設(shè)選擇艇劫。
解：歸納偏好以我個(gè)人的理解就是對(duì)于不同的算法而言吼驶，a算法的效果比b好，但是a的內(nèi)存開銷和時(shí)間開銷比b大店煞，如何評(píng)價(jià)對(duì)于同一個(gè)問題算法的好壞蟹演，就是看重視哪一方面，重視效果（準(zhǔn)確率）那么就認(rèn)為a好顷蟀，折中考慮效率就認(rèn)為b好酒请。因此歸納偏好在我理解就是最佳模型的基準(zhǔn)。
回到問題鸣个，對(duì)于此情況羞反，我認(rèn)為精度高的歸納偏好為假設(shè)選擇哮兰，即和訓(xùn)練樣本假設(shè)最接近的。
1.4 本章1.4節(jié)在論述“沒有免費(fèi)的午餐”定理時(shí)苟弛，默認(rèn)使用了“分類錯(cuò)誤率”作為性能度量來對(duì)分類器進(jìn)行評(píng)估喝滞。若換用其他性能度量l,試證明沒有免費(fèi)的午餐”定理仍成立。
解：證明：
在證明定理之前膏秫，先構(gòu)造一個(gè)引理：
引理1：在二分類問題下右遭，對(duì)任意性能度量指標(biāo)l，l(h(x)=f(x))+l(h(x)≠f(x))=A,Al(h(x)=f(x))+l(h(x)≠f(x))=A,A為某一常數(shù)缤削。
證：對(duì)于二分類問題窘哈，任意性能度量中的正確分類得分與錯(cuò)誤分類得分應(yīng)該是固定的。即：
l(0,0)=l(1,1),l(0,1)=l(1,0)
因此
l(0,0)+l(0,1)=l(1,1)+l(1,0)
設(shè)
l(0,0)+l(0,1)=l(1,1)+l(1,0)=A
即可得：
l(h(x)=f(x))+l(h(x)≠f(x))=A
證畢.
現(xiàn)在證明定理：
1.5 試述機(jī)器學(xué)習(xí)能在互聯(lián)網(wǎng)搜索的哪些環(huán)節(jié)起作用
解：機(jī)器學(xué)習(xí)對(duì)搜索引擎可進(jìn)行的優(yōu)化
1.搜索引擎直接給出搜索的答案：這里用到神經(jīng)網(wǎng)絡(luò)亭敢，它可以通過分析大量數(shù)據(jù)從而完成特定的任務(wù)滚婉，如從相關(guān)網(wǎng)頁中獲取長句子和段落，然后提出有關(guān)問題答案的信息帅刀。
2.直接進(jìn)行圖片让腹、視頻（等多元數(shù)據(jù)）的搜索：圖片的識(shí)別已經(jīng)是常見的技術(shù)了，那直接從視頻中提出信息呢扣溺？谷歌推出Video Intelligence API骇窍，不僅可以從視頻中提取特定的信息，還能總結(jié)視頻的脈絡(luò)锥余、記錄視頻中的場景腹纳，從而對(duì)視頻進(jìn)行準(zhǔn)確的分類。
3.更精準(zhǔn)的排序（也可成為「精準(zhǔn)營銷」的部分）：如使用神經(jīng)網(wǎng)絡(luò)驱犹、決策樹等為基礎(chǔ)的網(wǎng)頁排序算法：RankNet, LambdaRank 和LambdaMART嘲恍。2015年，谷歌推出RankBrain雄驹，它可以選擇最適合當(dāng)前搜索類型的結(jié)果佃牛，相當(dāng)于為每個(gè)搜索都提供個(gè)性化的算法組合。
4.對(duì)用戶行為進(jìn)行綜合分析（如歷史搜索數(shù)據(jù)荠医、點(diǎn)擊模式吁脱、身份信息等進(jìn)行結(jié)構(gòu)化信息整合）
5.對(duì)垃圾網(wǎng)站的篩選（模式識(shí)別）
參考文章：
https://zhuanlan.zhihu.com/p/27900874
https://blog.csdn.net/qq_26371477/article/details/102292685
https://blog.csdn.net/dicker6315/article/details/81265066
