機器學(xué)習(xí)（西瓜書）第一章 緒論 課后習(xí)題

1.1 表1.1中若只包含編號為1和4的兩個樣例，試給出相應(yīng)的版本空間。

  • 題目詳細描述：表格如下所示
編號 色澤 根蒂 敲聲 好瓜
1 青綠 蜷縮 濁響 是
4 烏黑 稍蜷 沉悶 否
  • 思路：
    何為版本空間？

版本空間(version space)是概念學(xué)習(xí)中與已知數(shù)據(jù)集一致的所有假設(shè)(hypothesis)的子集集合。版本空間學(xué)習(xí)是機器學(xué)習(xí)的邏輯方法，特別是二分類（binary classification）。
版本空間學(xué)習(xí)算法搜索預(yù)定空間的假設(shè)，被視為一組邏輯語句。

對于二維空間中的“矩形”假設(shè)（下圖），綠色加號代表正類樣本，紅色小圈代表負類樣本。 GB 是最大泛化正假設(shè)邊界(maximally General positive hypothesis Boundary), SB 是最大精確正假設(shè)邊界(maximally Specific positive hypothesis Boundary). GB與SB所圍成的區(qū)域中的矩形即為版本空間中的假設(shè)，也即GB與SB圍成的區(qū)域就是版本空間。


版本空間圖示

+解答：根據(jù)緒論中的表示方法，根據(jù)編號1和4的兩個樣例可以得到以下7種不同的版本空間

題1.1版本空間圖示

1.2 與使用單個合取式來進行假設(shè)表示相比，使用“析合范式”將使得假設(shè)空間具有更強的表示能力。

例如

好瓜?

（（色澤=*）\wedge（根蒂=蜷縮）\wedge（敲聲=*） \bigvee （（色澤=烏黑）\wedge（根蒂=*）\wedge（敲聲=沉悶））

我們吧“（色澤=青綠）\wedge（根蒂=蜷縮）\wedge 敲聲=清脆）”以及“（（色澤=烏黑）\wedge（根蒂=硬挺）\wedge（敲聲=沉悶））”都分類為“好瓜”。

若使用最多包含k個合取式的析合范式來表達表1.1西瓜分類問題的假設(shè)空間，試估算共有多少種可能的假設(shè)。

  • 題目詳細描述：完整表1如下
編號 色澤 根蒂 敲聲 好瓜
1 青綠 蜷縮 濁響 是
2 烏黑 蜷縮 濁響 是
3 青綠 硬挺 清脆 否
4 烏黑 稍蜷 沉悶 否

+解答：

假設(shè)一個瓜的好或不好，由三個屬性確定。分別是色澤、根蒂、敲聲。
其中，色澤有青綠、烏黑，2種取值，根蒂有蜷縮、稍蜷、硬挺3種取值，敲聲有濁響、清脆、沉悶3種取值。
那么假設(shè)空間由形如 “(色澤=？) ∧ (根蒂=？) ∧ (敲聲=？)” 的所有假設(shè)組成。
除了考慮屬性色澤、根蒂、敲聲分別有2 、3、3種可能取值，還要考慮到一種屬性可能無論取什么值都合適（用通配符*表示），另外有一種情況就是好瓜這個概念根本不成立（用?表示），則假設(shè)空間大小為 （2 + 1）×（3 + 1）×（3 + 1）+ 1 = 49 。

因為最多包含k個合取式，因此使用0，1，2...,k個合取式表示假設(shè)空間均符合要求
故可能的假設(shè)一共有\sum_{n=0}^k C_{49}^n

根據(jù)二項式定理

二項式定理

令x=1，可得2^k=\sum_{n=0}^k C_{k}^n ，無法化簡。
網(wǎng)上大多數(shù)答案均為2^{49}，該答案當且僅當k只等于49時，能夠得到

1.3 若數(shù)據(jù)包含噪聲，則假設(shè)空間中有可能不存在與所有訓(xùn)練樣本，都一致的假設(shè)。在此情形下，試設(shè)計一種歸納偏好用于假設(shè)選擇。

噪音數(shù)據(jù)：是指數(shù)據(jù)中存在錯誤或異常的數(shù)據(jù)，即無用數(shù)據(jù)
歸納偏好: 對應(yīng)了學(xué)習(xí)算法本身所做出的關(guān)于“什么樣的模型更好”的假設(shè)，在具體的現(xiàn)實問題中，假設(shè)是否成立，即算法的歸納偏好是否與問題本身的匹配，大多數(shù)直接決定了算法能否取得好的性能。

解答：由于含有噪聲，故可對樣本空間放寬約束。對于那些只與極少數(shù)樣本不一致卻與極大多數(shù)樣本一致的假設(shè)，仍將其保留在版本空間中。（即當該假設(shè)的的樣本準確率足夠大時，也認為該假設(shè)有效）

1.4 本章1.4節(jié)在論述“沒有免費的午餐”定理時，默認使用了“分類錯誤率”作為性能度量來對分類器進行評估。若換用其他性能度量\ell,試證明沒有免費的午餐”定理仍成立

換用其他性能度量\ell,公式如下
E_{ote}(\varepsilon_a|X,f)=\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)

證明：

在證明定理之前，先構(gòu)造一個引理：
引理1：在二分類問題下，對任意性能度量指標\ell，\ell（h(x)=f(x)）+\ell（h(x)\neq f(x)）=A,A為一常數(shù)。
證：對于二分類問題，任意性能度量中的正確分類得分與錯誤分類得分應(yīng)該是固定的。即：
\ell（0,0）=\ell（1,1）,\ell（0,1）=\ell（1,0）
因此
\ell（0,0）+\ell（0,1）=\ell（1,1）+\ell（1,0）
設(shè)\ell（0,0）+\ell（0,1）=\ell（1,1）+\ell（1,0）=A，即可得：
\ell（h(x)=f(x)）+\ell（h(x)\neq f(x)）=A
證畢。

因為E_{ote}(\varepsilon_a|X,f)=\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)
因此\sum_fE_{ote}(\varepsilon_a|X,f)=\sum_f\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)
=\sum_{x\in(\chi-X)}P(x)\sum_hP(h|X,\varepsilon_a)\sum_f\ell(h(x),f(x))
=\sum_{x\in(\chi-X)}P(x)\sum_hP(h|X,\varepsilon_a)(\frac{1}{2}2^{|\chi|}\ell（h(x)=f(x)）+\frac{1}{2}2^{|\chi|}\ell（h(x)\neq f(x)）)
=2^{|\chi|-1}A\sum_{x\in(\chi-X)}P(x)\cdot1
上式說明度量結(jié)果與學(xué)習(xí)算法\varepsilon_a無關(guān)，“沒有免費的午餐定理”仍然成立。
證明完畢。

關(guān)于證明的補充說明：本文的引理沒有考慮第二章2.3節(jié)中的代價敏感錯誤。若本題中考慮代價敏感錯誤，則各種不同代價錯誤出現(xiàn)的概率也是滿足平均分布的，引理1仍然成立，但是證明過程會更加復(fù)雜。
思考： NFL定理證明過程中假設(shè)了f均勻分布，并且目標是學(xué)習(xí)所有的真實函數(shù)f?，F(xiàn)實生活中，具體的學(xué)習(xí)算法無需學(xué)習(xí)所有的真實函數(shù)，因為所有真實函數(shù)在現(xiàn)實中的映射即天底下所有問題都可以用相同的這一組特征來描述，這是不現(xiàn)實的。若用同一組特征來描述所有問題，那么分類結(jié)果必將雜亂無章沒有任何規(guī)律可言，這也是書中假設(shè)f滿足均勻分布的原因。真實情況下，也許沒有任何一種分布能夠描述其特征。因此NFL并不意味著好的學(xué)習(xí)算法沒有意義。

1.5 試述機器學(xué)習(xí)能在互聯(lián)網(wǎng)搜索的哪些環(huán)節(jié)起作用

以下答案來源
知乎| 機器學(xué)習(xí)能在互聯(lián)網(wǎng)搜索的哪些環(huán)節(jié)起什么作用

搜索引擎

我們先得明白搜索引擎都干了啥，然后看哪些部分可以用機器學(xué)習(xí)來提高用戶體驗的，下圖出自：第 1 章 搜索引擎是如何工作的

構(gòu)成搜索引擎的全部要素

1、文檔管理器：存儲作為檢索對象的文檔。當查詢到相匹配的文檔時，會取出該文檔的一部分作為摘要。
2、索引構(gòu)建器：從檢索對象的文本文檔中構(gòu)建文本的索引。
3、索引管理器：管理帶有索引結(jié)構(gòu)的數(shù)據(jù)，索引結(jié)構(gòu)是一種用于進行高速檢索的數(shù)據(jù)結(jié)構(gòu)。
4、索引檢索器：利用用戶的查詢進行文本檢索，并根據(jù)某種規(guī)則進行排序并將結(jié)果返回給應(yīng)用。

除了以上的組建除外，一個完整的搜索引擎還包括：爬蟲、搜索排序系統(tǒng)。

因為我們只是大致地了解一下機器學(xué)習(xí)在搜索引擎上的作用，所以關(guān)于搜索引擎的部分就先講到這，然后來看看哪些地方可以優(yōu)化。

機器學(xué)習(xí)對搜索引擎可進行哪些優(yōu)化

根據(jù)搜索引擎的結(jié)構(gòu)，我們可以進行以下的機器學(xué)習(xí)優(yōu)化

  1. 文檔管理器：生成更精準的摘要。本質(zhì)就是文檔摘要的自動生成，涉及深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、NLP
  2. 索引構(gòu)建器：索引構(gòu)建已很成熟，但我發(fā)現(xiàn)仍有學(xué)者將機器學(xué)習(xí)應(yīng)用于這部分，主要是用機器學(xué)習(xí)算法代替標準哈希函數(shù)，但效果還不太好[3]。
  3. 索引管理器：暫無。
  4. 索引檢索器：這里涉及查詢與文本間的匹配，以及搜索結(jié)果的排序，也是直接面向用戶的部分。

綜上分析，我們主要來看索引檢索器的部分，這部分可以有哪些優(yōu)化呢:

  1. 搜索引擎直接給出搜索的答案：這里用到神經(jīng)網(wǎng)絡(luò)，它可以通過分析大量數(shù)據(jù)從而完成特定的任務(wù)，如從相關(guān)網(wǎng)頁中獲取長句子和段落，然后提出有關(guān)問題答案的信息。
直接給出答案

  1. 直接進行圖片、視頻（等多元數(shù)據(jù)）的搜索：圖片的識別已經(jīng)是常見的技術(shù)了，那直接從視頻中提出信息呢？谷歌推出Video Intelligence API，不僅可以從視頻中提取特定的信息，還能總結(jié)視頻的脈絡(luò)、記錄視頻中的場景，從而對視頻進行準確的分類。

  2. 更精準的排序（也可成為「精準營銷」的部分）：如使用神經(jīng)網(wǎng)絡(luò)、決策樹等為基礎(chǔ)的網(wǎng)頁排序算法：RankNet, LambdaRank 和LambdaMART。2015年，谷歌推出RankBrain，它可以選擇最適合當前搜索類型的結(jié)果，相當于為每個搜索都提供個性化的算法組合。

  3. 對用戶行為進行綜合分析（如歷史搜索數(shù)據(jù)、點擊模式、身份信息等進行結(jié)構(gòu)化信息整合）：更多使用在電子商務(wù)的搜索系統(tǒng)中。這在電商網(wǎng)站中的使用，應(yīng)該是很盛行的，但具體沒有調(diào)研過。

  4. 對話式智能交互搜索：如Baidu的語音搜索、利用Siri進行搜索又或者是Google Assistant等。涉及自然語言處理、知識圖譜及神經(jīng)網(wǎng)絡(luò)等內(nèi)容。

小愛能夠回答的問題
  1. 對垃圾網(wǎng)站的篩選（模式識別）：這部分可以用Outlier的檢測來實現(xiàn)，尤其對以前的標題黨，或者以前針對算法進行SEO的網(wǎng)站進行甄別。

最理想的模型應(yīng)該是：搜索引擎成為一個具備不斷自我學(xué)習(xí)和改善的系統(tǒng)。也就是將機器學(xué)習(xí)應(yīng)用于搜索引擎的所有方面，一個全自動化的搜索引擎系統(tǒng)。

現(xiàn)在的難點有哪些呢？

  1. 搜索引擎是否真正第理解自然語言查詢詞及文檔的意義，還不得知。
  2. 仍需要大量的人工對相關(guān)數(shù)據(jù)進行標記，尤其需要大量的語言學(xué)家進行這方面的工作。
  3. 跨語的搜索精確度的問題，當然這部分也是機器學(xué)習(xí)能夠改善的部分。
  4. 其他的自然語言遇到的問題，例如歧義等，講到底還是語意的理解。

參考資料：

[1]:第 1 章 搜索引擎是如何工作的

[2]:深度學(xué)習(xí)之文本摘要自動生成 - CSDN博客

[3]:The Case For Learned Indexes (Google/MIT)

[4]:AI 再造搜索３招：谷歌如何用機器學(xué)習(xí)和深度學(xué)習(xí)直接給你答案

[5]:搜索引擎如何使用機器學(xué)習(xí):我們需要知道的9種方式 | ATYUN

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容