《机器学习》西瓜书习题 第 1 章

#习题

1.1

1.11.11.1 中若只包含编号为 111 和 444 的两个样例, 试给出相应的版本空间.

这应该不难理解吧,直接上表格.

编号 色泽 根蒂 敲声 好瓜
111 青绿 蜷缩 浊响
444 乌黑 稍蜷 沉闷

1.2

与使用单个合取式来进行假设表示相比, 使用 “析合范式” 将使得假设空间具有更强的表示能力. 例如((=)(=)(=))((=)(=)(=))好瓜 \leftrightarrow \big((色泽=*)\wedge(根蒂=蜷缩)\wedge(敲声=*)\big)\vee\big((色泽=乌黑)\wedge(根蒂=*)\wedge(敲声=沉闷)\big)好瓜↔((色泽=∗)∧(根蒂=蜷缩)∧(敲声=∗))∨((色泽=乌黑)∧(根蒂=∗)∧(敲声=沉闷))会把 “(=)(=)(=)(色泽=*)\wedge(根蒂=蜷缩)\wedge(敲声=*)(色泽=∗)∧(根蒂=蜷缩)∧(敲声=∗)” 以及 “(=)(=)(=)(色泽=乌黑)\wedge(根蒂=*)\wedge(敲声=沉闷)(色泽=乌黑)∧(根蒂=∗)∧(敲声=沉闷)” 都分类为 “好瓜” . 若使用最多包含 kkk 个合取式的析合范式来表达 1.11.11.1 西瓜分类问题的假设空间, 试估算共有多少种可能的假设.

一共有 333 个特征, 第一个特征有 333 种取值(算上 *∗ ), 第二, 三个都是 444 种取值.
  每个合取式我们分为三项:色泽, 根蒂, 敲声.这里要注意某个项其实是可以同时选择两种取值的, 比如色泽这一项可以是 ((=绿)(=))\big((色泽=青绿)\wedge(色泽=乌黑)\big)((色泽=青绿)∧(色泽=乌黑)) 而不是只能有一个取值.
  那么第一项只可能选择一个或两个取值, 取值是一个时有 333 种可能, 取值为两种时只有 111 种可能(即除了 *∗ 外的另两种一起取到), 其他项以此类推, 那么就有 4×7×7=1964\times7\times7=1964×7×7=196 种合取式, 因此 kmax=196k_{ma\boldsymbol{x}}=196kmax​=196.
  所以可能的假设总数为 i=1kmaxCkmaxi\sum^{k_{ma\boldsymbol{x}}}_{i=1}C_{k_{ma\boldsymbol{x}}}^i∑i=1kmax​​Ckmax​i​ , 即任意取 1kmax1\sim k_{ma\boldsymbol{x}}1∼kmax​个合取式然后组合成的析合范式的数量.
  当然我们这里不考虑冗余 (因为我懒) .

1.3

若数据包含噪声, 则假设空间中有可能不存在与所有训练样本都一致的假设. 在此情形下, 试设计一种归纳偏好用于假设选择.

当然是奥卡姆剃刀啦, “如无必要, 勿增实体”, 大概体现了一种哲学思想吧.

1.4*

本章 1.41.41.4 节在论述 “没有免费的午餐” 定理时, 默认使用了 “分类错误率” 作为性能度量来对分类器进行评估. 若换用其他性能度量 \ellℓ ,则将式(1.1)(1.1)(1.1)改为Eote(LaX,f)=hxXXP(x)(h(x),f(x))P(hX,La)E_{ote}(\mathfrak{L}_a\mid X,f)=\sum_h\sum_{\boldsymbol{\boldsymbol{x}}\in \mathfrak{X}-X}P(\boldsymbol{\boldsymbol{x}})\ell(h(\boldsymbol{\boldsymbol{x}}),f(\boldsymbol{\boldsymbol{x}}))P(h\mid X,\mathfrak{L}_a)Eote​(La​∣X,f)=h∑​x∈X−X∑​P(x)ℓ(h(x),f(x))P(h∣X,La​)试证明 “没有免费的午餐定理” 仍成立.

其实和原来的推导差不多. 对所有可能的 fff 按均匀发布对误差求和, 有
fEote(LaX,f)=fhxXXP(x)(h(x),f(x))P(hX,La)=xXXP(x)hp(hX,L)f(h(x),f(x))=xXXP(x)hp(hX,L)E()=E()xXXP(x)hp(hX,L)=E()xXXP(x)1=E()xXXP(x)\begin{aligned} \sum_fE_{ote}(\mathfrak{L}_a\mid X,f)&=\sum_f\sum_h\sum_{\boldsymbol{x}\in \mathfrak{X}-X}P(\boldsymbol{x})\ell(h(\boldsymbol{x}),f(\boldsymbol{x}))P(h\mid X,\mathfrak{L}_a)\\ &=\sum_{\boldsymbol{x}\in\mathfrak{X}-X}P(\boldsymbol{x})\sum_hp(h\mid X,\mathfrak{L})\sum_f\ell(h(\boldsymbol{x}),f(\boldsymbol{x}))\\ &=\sum_{\boldsymbol{x}\in\mathfrak{X}-X}P(\boldsymbol{x})\sum_hp(h\mid X,\mathfrak{L})E(\ell)\\ &=E(\ell)\sum_{\boldsymbol{x}\in\mathfrak{X}-X}P(\boldsymbol{x})\sum_hp(h\mid X,\mathfrak{L})\\ &=E(\ell)\sum_{\boldsymbol{x}\in\mathfrak{X}-X}P(\boldsymbol{x})\cdot1\\ &=E(\ell)\sum_{\boldsymbol{x}\in\mathfrak{X}-X}P(\boldsymbol{x}) \end{aligned}f∑​Eote​(La​∣X,f)​=f∑​h∑​x∈X−X∑​P(x)ℓ(h(x),f(x))P(h∣X,La​)=x∈X−X∑​P(x)h∑​p(h∣X,L)f∑​ℓ(h(x),f(x))=x∈X−X∑​P(x)h∑​p(h∣X,L)E(ℓ)=E(ℓ)x∈X−X∑​P(x)h∑​p(h∣X,L)=E(ℓ)x∈X−X∑​P(x)⋅1=E(ℓ)x∈X−X∑​P(x)​
  E()E(\ell)E(ℓ) 为 \ellℓ 的数学期望(就是 \ellℓ 这个函数所有可能输出的均值去乘 2X2^{|\mathcal{X}|}2∣X∣, 因为 fff 是任意的. 反正是个常数.).
  最终表达式与学习算法 L\mathfrak{L}L 无关, 于是fEate(LX,f)=fEate(LX,f)\sum_fE_{ate}(\mathfrak{L}\mid X,f)=\sum_fE_{ate}(\mathfrak{L}\mid X,f)f∑​Eate​(L∣X,f)=f∑​Eate​(L∣X,f)
  所以 “没有免费的午餐定理” 仍成立.

1.5

试述机器学习能在互联网搜索的哪些环节起什么作用.

这个就多了, 比如搜索引擎, 图片搜索, 智能化推荐, 还有很多很多. 当然你还可以用机器学习来破解反爬虫, 比如识别简单的验证码.

《机器学习》西瓜书习题 第 1 章《机器学习》西瓜书习题 第 1 章 C-loud 发布了7 篇原创文章 · 获赞 0 · 访问量 16 私信 关注
上一篇:Java初学之人机猜拳游戏


下一篇:c语言编写任意进制转换