机器学习问题解析与算法优化策略

table {
border-collapse: collapse;
width: 100%;
margin-bottom: 1rem;
}
th, td {
border: 1px solid #ddd;
padding: 8px;
text-align: left;
}
th {
background-color: #f2f2f2;
}
tr:nth-child(even) {
background-color: #f9f9f9;
}
pre {
background-color: #f8f8f8;
padding: 15px;
border-radius: 4px;
overflow-x: auto;
}

1、在滑块拼图游戏中，提出一个比‘计算每个方块到达最终位置所需移动的方格数之和’更好的评估函数。

一个更好的评估函数可以结合曼哈顿距离和线性冲突。

曼哈顿距离

：是每个方块当前位置到其目标位置在水平和垂直方向上的距离之和。

线性冲突

：是指在同一行或同一列中，两个方块都不在其目标行或目标列，且它们的目标位置在同一行或同一列时，它们之间存在冲突。

可以将

曼哈顿距离

与

线性冲突的数量

相加作为新的评估函数值。这样能更全面地评估当前状态与目标状态的差距，引导搜索朝着更优的方向进行。

2、在一个由十个布尔属性描述示例的领域中，实例空间的大小是多少？那么分类器空间有多大？

实例空间大小

：从n个布尔属性可创建2ⁿ个不同示例，当n = 10时，实例空间大小为2¹⁰。

分类器空间大小

：假设分类器由任意布尔函数定义，其假设空间大小为2的2ⁿ次方，当n = 10时，分类器空间大小为2的2¹⁰次方。

3、在“馅饼”领域中，你能想到哪些类型的噪声？这些噪声的来源是什么？还有哪些问题会使训练集不完美？

在“馅饼”领域中，可能存在属性值噪声和类别标签噪声。

属性值噪声的来源

：

信息源不可靠

测量设备不佳

打字错误

用户混淆等

类别标签噪声的来源

：

专家建议的标签记录不当

示例处于两类之间的“灰色区域”

医生诊断倾向

自动化过程出错等

其他使训练集不完美的问题包括：

存在无关属性

冗余属性

缺失关键属性

这些问题会导致训练集不一致。

4、一枚硬币抛了三次，分别出现正面、反面和反面。使用m = 3以及$ heta_{正面} = heta_{反面} = 0.5$，计算这些结果的m – 估计值。

本题可根据m – 估计值公式分别计算出现正面和反面的概率。已知m – 估计值公式为

Pheads=Nheads+m×θheadsNall+mPheads=Nheads+m×θheadsNall+m

其中

$N_{all}$ 是抛硬币的总次数

$N_{heads}$ 是出现正面的次数

$ heta_{heads}$ 是正面的先验期望

$m$ 是辅助参数

本题中：

$N_{all}=3$

$N_{heads}=1$

$m = 3$

$ heta_{heads}=0.5$

将这些值代入公式可得：

Pheads=1+3×0.53+3=1+1.56=2.56=512Pheads=1+3×0.53+3=1+1.56=2.56=512

因为抛硬币只有正面和反面两种结果，且

$ heta_{heads}+ heta_{tails}=1$

$N_{heads}+N_{tails}=N_{all}$

所以：

Ptails=1−Pheads=1−512=712Ptails=1−Pheads=1−512=712

综上，正面的m – 估计值为 $frac{5}{12}$，反面的m – 估计值为 $frac{7}{12}$。

5、提出关于最近邻原则的其他变体。提示如下：(a)引入替代的距离度量方法，这些距离度量方法需满足距离不能为负、两个相同向量之间的距离为零、从x到y的距离与从y到x的距离相同、满足三角不等式（即d(x, y) + d(y, z) ≥ d(x, z)）。(b)修改投票方案，假设一些示例是由知识渊博的“教师”创建的，而另一些是从数据库中获取的，没有考虑它们的代表性，要让教师给出的示例有更大的权重。

以下是关于最近邻原则的其他变体：

(a) 替代的距离度量方法有很多，如：

极距离

明可夫斯基度量

马氏距离

不过，这些距离度量方法需要满足一些公理：

距离不能为负；

两个相同向量之间的距离为零；

从 $ x $ 到 $ y $ 的距离与从 $ y $ 到 $ x $ 的距离相同；

满足三角不等式，即 $ d(x, y) + d(y, z) geq d(x, z) $。

(b) 在修改投票方案时，对于由知识渊博的“教师”创建的示例和从数据库中获取的示例，可给前者分配更大的权重。例如，在加权 k-近邻分类器中，可根据示例来源设置不同的权重。

若教师给出的示例权重为 $ w_1 $，数据库获取的示例权重为 $ w_2 $，且 $ w_1 > w_2 $，在计算各类别得分时，教师示例的得分贡献更大，从而影响最终的分类结果。

6、设计一个使用爬山搜索来去除冗余示例的算法。提示：初始状态包含整个训练集，搜索操作每次移除一个训练示例（此移除操作不能影响性能）。

以下是使用爬山搜索来去除冗余示例的算法设计：

创建两个列表，

L
和

Lseen
。开始时，

L
仅包含初始状态（即整个训练集），

Lseen
为空。

令

n
为

L
的第一个元素。比较当前训练集

n
与一个基准性能（例如在验证集上的准确率）：

– 若性能未下降，继续下一步；

– 若性能下降，则将

n
从

L
移除并加入

Lseen
，然后返回第 2 步。

对

n
应用搜索操作，即每次移除一个训练示例，得到一组新的训练集。丢弃那些已存在于

Lseen
中的训练集。对于其余的训练集，使用评估函数（如验证集上的性能）对它们进行排序，并将它们放在

L
的前面。

将

n
从

L
转移到已研究状态的列表

Lseen
中。

如果

L
为空，停止并报告最终的训练集；否则，返回第 2 步。

评估函数

可以使用验证集上的性能指标（如准确率、召回率等）来评估每个训练集的质量。

搜索操作

每次从当前训练集中移除一个训练示例，生成新的训练集。

终止条件

当

L
为空或者达到最大迭代次数时停止。

7、描述一个使用爬山搜索来去除无关属性的算法。提示：保留一些训练示例，用于测试 1 – NN 分类器在不同属性子集上的性能。

以下是将给定文本内容调整为 Markdown 格式的结果：

可采用如下步骤构建算法：

首先，保留部分训练示例。

接着，以所有属性构成的集合作为初始状态。

每次使用搜索操作移除一个属性，形成新的属性子集。

然后，用保留的训练示例测试 1 – NN 分类器在这些不同属性子集上的性能。

根据性能评估函数对新状态进行排序，将排序后的新状态置于待探索列表前端。

把当前探索的属性集合转移到已探索列表。

若待探索列表为空，则停止并报告失败；否则，继续选择列表首个元素作为当前状态，重复上述操作，直至满足终止条件，即移除属性不再使 1 – NN 分类器性能提升。

8、写出线性分类器的方程以实现以下功能：1. 布尔属性x1, …, x5中至少有两个为真；2. 布尔属性x1, …, x6中至少有三个为真，且其中至少有一个为假。

对于布尔属性 $ x_1, dots, x_5 $ 中至少有两个为真的情况，线性分类器方程可以表示为：

x1+x2+x3+x4+x5≥2×1+x2+x3+x4+x5≥2

这里，将属性值为真设为 1，为假设为 0，当这个表达式的值大于等于 2 时，就表示至少有两个属性为真。

对于布尔属性 $ x_1, dots, x_6 $ 中至少有三个为真，且其中至少有一个为假的情况：

首先用不等式表示至少三个为真：

x1+x2+x3+x4+x5+x6≥3×1+x2+x3+x4+x5+x6≥3

再用不等式表示至少有一个为假：

x1+x2+x3+x4+x5+x6<6×1+x2+x3+x4+x5+x6<6

综合起来就是一个不等式组来实现该功能：

{x1+x2+x3+x4+x5+x6≥3 x1+x2+x3+x4+x5+x6<6{x1+x2+x3+x4+x5+x6≥3 x1+x2+x3+x4+x5+x6<6

9、再次进行相同的练习，这次使用 WINNOW 算法。为解决感知机中不能有负权重的问题，需要引入额外的“属性”。请说明如何处理属性并使用 WINNOW 算法完成练习。

在 WINNOW 中，为解决不能有负权重的问题，可将每个原始属性用一对“新”属性表示，一个复制原始属性的值，另一个取相反值。

例如原本有 $ n $ 个属性的领域，新表示法下属性总数变为 $ 2n $，第 $ n + i $ 个属性 $ x_{n+i} $ 的值是 $ x_i $ 的相反值。

如一个示例原本用三个属性值：

$ x_1 = 1 $

$ x_2 = 0 $

$ x_3 = 1 $

新表示法下用六个属性：

$ x_1 = 1 $

$ x_2 = 0 $

$ x_3 = 1 $

$ x_4 = 0 $

$ x_5 = 1 $

$ x_6 = 0 $

WINNOW 需为这些属性找到相应权重。

在进行练习时，应按此方法对属性进行转换，再使用 WINNOW 算法的权重更新规则：

当 $ c(x) = 1 $ 而 $ h(x) = 0 $ 时，$ w_i = alpha w_i $

当 $ c(x) = 0 $ 而 $ h(x) = 1 $ 时，$ w_i = frac{w_i}{alpha} $

当 $ c(x) = h(x) $ 时，不做处理

也可用统一公式：

wi=wi⋅αc(x)−h(x)wi=wi⋅αc(x)−h(x)

进行权重更新。

10、如何利用线性分类器的归纳来识别无关属性？提示：尝试在不同的属性子集上运行学习算法，然后观察固定轮数后的错误率。

可在不同的属性子集上运行学习算法，然后观察固定轮数后所达到的错误率，以此识别无关属性。

11、有时，由于类别标签噪声的存在，原本线性可分的领域会变得线性不可分。请想出一种能够去除这些噪声示例的技术。提示：你可以借鉴在 k – 近邻（k – NN）分类器领域已经遇到过的想法。

可以使用 k-NN 分类器中常用的方法，如基于距离的过滤。计算每个样本与其 k 个近邻的距离或相似度，如果某个样本与其近邻的类别差异较大，或者距离明显偏离正常范围，就可以将其视为噪声样本并去除。还可以通过统计样本周围近邻的类别分布，若样本的类别与多数近邻的类别不一致，也可考虑将其去除。

12、创建一个由20个示例组成的训练集，每个示例由五个二元属性x1, …, x5描述。若一个示例中至少有三个属性的值xi = 1，则将其标记为正例，其他示例标记为负例。以这个训练集作为输入，使用感知机学习算法诱导一个线性分类器。对不同的学习率α进行实验。绘制一个函数图像，横轴表示α，纵轴表示分类器正确分类所有训练示例所需的示例呈现次数。讨论实验结果。

首先，按照要求创建包含20个示例的训练集，根据至少三个属性值为1则标记为正例的规则进行标记。接着，使用感知机学习算法，在不同的学习率α下对训练集进行学习，记录每个α对应的分类器正确分类所有训练示例所需的示例呈现次数。然后，以α为横轴，示例呈现次数为纵轴绘制函数图像。

对于实验结果的讨论：

学习率α较小时，收敛速度慢，需要更多的示例呈现次数才能达到正确分类所有训练示例的效果。

学习率α较大时，可能会导致算法在最优解附近震荡，难以收敛，甚至可能错过最优解。

合适的学习率α能够使算法在较少的示例呈现次数内收敛到正确分类所有训练示例的状态。

13、考虑一组十个训练示例。假设有一个连续属性，其值如下：3.6、3.2、1.2、4.0、0.8、1.2、2.8、2.4、2、2、1.0。假设前五个示例以及最后一个示例为正例，其他所有示例为反例。该属性值范围的最佳二分划分是什么？

文本内容调整为markdown格式如下：

首先，将属性值按升序排序：

0.8
、

1.0
、

1.2
、

2
、

2.4
、

2.8
、

3.2
、

3.6
、

4.0
。

标记各值的类别，正例标记为

+
，反例标记为

-
，可得：

0.8(+)
、

1.0(+)
、

1.2(+)
、

2(-)
、

2.4(-)
、

2.8(-)
、

3.2(-)
、

3.6(+)
、

4.0(+)
。

根据规则，最佳阈值应位于不同类别标签的值之间，所以候选阈值为：

(1.2 + 2) / 2 = 1.6
、

(2.8 + 3.6) / 2 = 3.2
。

接下来，计算训练集的熵

H(T)
：

正例数量为

6
，反例数量为

5
，总数量为

11
。

H(T) = - (6 / 11) * log(6 / 11) - (5 / 11) * log(5 / 11)

然后分别计算两个候选阈值划分后的子集熵及平均熵和信息增益：

对于阈值

1.6
，计算：

H(x < 1.6)

H(x > 1.6)

H(T, 1.6)

I(T, 1.6)

对于阈值

3.2
，计算：

H(x < 3.2)

H(x > 3.2)

H(T, 3.2)

I(T, 3.2)

最后比较两个候选阈值的信息增益，信息增益最大的阈值即为最佳阈值，对应的二分划分就是最佳二分划分。

14、评估决策树的基线性能标准是错误率和树的大小（节点数量）。然而，这些标准在某些领域可能并不适用。请举例说明在哪些应用中，决策树的大小或错误率可能不太重要。提示：考虑错误决策的成本和获取属性值的成本。

以下两类应用中，决策树大小或错误率可能不太重要：

错误决策成本低的应用

如电影推荐系统，推荐不准确只会影响用户体验，不会造成重大损失，此时错误率不太重要；

获取属性值成本低的应用

如社交媒体数据挖掘，可轻易获取大量用户数据，树的大小对成本影响小，决策树大小不太重要。

15、在布尔属性合取的情况中，如果将所需的错误率从 ε = 0.2 更改为 ε = 0.05，在最坏情况下分析需要多使用多少个示例？相反，δ 的变化会如何影响所需训练集的大小？

根据公式

m>1ε(nln3+ln(1δ))m>1ε(nln⁡3+ln⁡(1δ))

当 $varepsilon$ 从 0.2 变为 0.05 时，所需示例数量变为原来的 4 倍，即需要多使用 3 倍原来数量的示例。

对于 $delta$：

– $delta$ 变小意味着对学习结果的置信度要求提高，$lnleft(frac{1}{delta}
ight)$ 会增大，从而使所需训练集大小 $m$ 增大；

– $delta$ 变大意味着对学习结果的置信度要求降低，$lnleft(frac{1}{delta}
ight)$ 会减小，所需训练集大小 $m$ 减小。

16、再次考虑所有属性均为布尔型，且分类器采用属性值合取形式的情况。如果合取式允许恰好涉及三个属性，那么假设空间的大小是多少？例如，以下是该类中的一个合取式：属性1为真且属性2为假且属性3为假

每个属性有两种取值（真或假），那么对于三个属性的合取，每个属性的取值组合有 (2 × 2 × 2 = 8) 种情况，所以假设空间的大小是 8。

17、我们已经知道，在没有偏差的情况下，分类器无法进行 PAC 学习。然而，偏差可能是未知的。请提出一种学习程序，在这种情况下诱导出布尔表达式形式的分类器。（提示：考虑两种或更多种替代偏差。）

可以尝试使用两种或更多种替代偏差来诱导布尔表达式形式的分类器。具体步骤如下：

基于不同的替代偏差对训练数据进行学习

，得到多个不同的分类器。

评估这些分类器在验证集上的性能

。

选择性能最优的分类器作为最终结果

。

18、过去，一些机器学习科学家考虑通过一种称为离散化的过程将连续属性转换为离散属性。他们的意思是将属性值的范围划分为区间，每个区间被视为一个布尔属性（给定的数值要么在给定区间内，要么不在）。假设你正在考虑两种划分范围 [0, 100] 的方法。第一种是划分为两个子区间 [0, 50] 和 [51, 100]，第二种是划分为十个等长子区间：[0, 10];… [91, 100]。从概率近似正确（PAC）可学习性的角度讨论这两种选择的优缺点。

两种划分方式各有优缺。

划分为两个子区间 [0, 50] 和 [51, 100]

优点

：

假设空间小，计算量低；

能更快找到合适假设；

数据少或特征简单时更易学习。

缺点

：

表达能力受限，可能无法准确描述复杂概念。

划分为十个等长子区间 [0, 10]、…、[91, 100]

优点

：

表达能力强，能更细致描述数据；

适合复杂数据分布。

缺点

：

假设空间大，计算成本高；

数据量不足时易过拟合；

难以找到合适假设。

19、假设实例空间由一些属性定义。如果分类器是属性值的合取，确定假设空间的大小。考虑两种情况：一种假设某些属性可能被视为无关（或冗余）而被忽略，另一种则要求所有属性都必须参与合取。

若某些属性可被视为无关或冗余而忽略，在逻辑合取中，每个属性有

真、假、无关

三种可能，若有

n
个属性，假设空间大小为

3ⁿ

。若要求所有属性都参与合取，每个属性有

真、假

两种可能，假设空间大小为

2ⁿ

。但由于未给出属性的具体数量

n
，无法得出具体数值。

20、假设你知道训练集中某些类别标签的正确性不确定。你是否建议将这些“不可靠”的示例从训练集中移除？在考虑时，不要忘记一些预分类的示例将用作测试示例，以评估所诱导分类器的分类性能。

是否移除“不可靠”示例的考量

是否移除“不可靠”示例需要综合考量。移除的好处是能避免不可靠标签误导分类器学习，提升分类器基于可靠数据学习的准确性，从而在测试集上有更好表现。

但移除也有弊端：

会减少训练数据量，可能导致分类器未充分学习数据特征，影响其泛化能力。

移除部分数据可能改变数据分布，影响测试集评估的有效性。

因此，是否移除应根据以下因素进行权衡决定：

不可靠示例的占比

对整体数据分布的影响

21、访问网络，查找一个关于美国50个州人口统计的网站。确定一个输出变量，如果其值高于美国平均水平，则视为正值，否则视为负值。每个州构成一个示例。根据网站提供的信息，确定描述这些示例的属性。从由此获得的数据中，归纳出一个分类器来预测输出变量的值。

本题可按以下步骤完成任务：

查找网站

：使用搜索引擎，输入相关关键词，如“美国50个州人口统计”，选择信息权威、数据全面的网站。

确定输出变量

：如选择“各州人均收入”作为输出变量，高于美国人均收入平均水平为正，反之为负。

确定描述示例的属性

：根据网站数据，可选取以下属性：

– 教育水平（如大学学历人口比例）

– 就业行业分布（如制造业、服务业占比）

– 年龄结构（如各年龄段人口比例）

数据获取与整理

：从网站提取每个州的输出变量值和各属性值，整理成数据集。

归纳分类器

：可使用机器学习算法，如决策树、逻辑回归等，利用整理好的数据集进行训练，得到能预测输出变量值的分类器。

22、假设八个分类器对一个示例进行了标记。返回正（pos）标签的分类器权重为[0.1, 0.8, 0.2]，返回负（neg）标签的分类器权重为[-0.1, 0.3, 0.3, 0.4, 0.9]。依赖加权多数投票的主分类器将返回什么标签？

首先计算支持正类的权重总和 $ W_{pos} $：

Wpos=0.1+0.8+0.2=1.1Wpos=0.1+0.8+0.2=1.1

再计算支持负类的权重总和 $ W_{neg} $：

Wneg=−0.1+0.3+0.3+0.4+0.9=1.8Wneg=−0.1+0.3+0.3+0.4+0.9=1.8

因为 $ W_{neg} > W_{pos} $，所以主分类器将把该示例标记为负类（neg）。

23、如何用最频繁的值替换数据集中的缺失值（用问号表示）？如何使用决策树来实现这一目的？

当属性为离散值时，用该属性最频繁出现的值替换问号；当属性为连续值时，用平均值替换问号。

使用决策树确定未知属性值的步骤如下：

创建新训练集 T₀，将有未知值的属性 aₜ 作为类标签，其余属性描述示例，原类标签视为普通属性；

从 T₀ 中移除 aₜ 值未知的示例；

从最终的 T₀ 中归纳出决策树；

使用归纳出的决策树确定 aₜ 在值未知示例中的值。

24、请举例说明一个领域，在该领域中精确率比召回率重要得多；反之，再举例说明一个领域，在该领域中召回率比精确率重要得多。

精确率比召回率重要的领域如信息检索，比如搜索引擎返回的搜索结果，用户更希望搜索出的信息是准确相关的，而不那么在意是否涵盖了所有相关信息。

召回率比精确率重要的领域如地震预警，预警系统应尽可能多地检测到可能发生地震的情况，即使可能存在一些误报，以保障人们的生命安全。

25、假设你使用 95% 置信区间测试分类器的性能。如果你改变主意，决定使用 99% 置信区间，会怎样呢？你会增加容差，但这样做的代价是什么？

增加置信水平到 99% 会使置信区间变长，虽然降低了

第一类错误

（错误拒绝正确声明）的风险，但会增加

第二类错误

（未能检测到错误声明）的风险，存在不可避免的权衡。

26、编写一个程序，使用5×2 – CV方法比较两种类别归纳技术，并使用t检验评估结果。假定已经有程序能将数据划分为使用5×2 – CV方法评估性能所需的5个“折”，且已经实现了至少两个类别归纳程序。

可按以下步骤编写程序：

利用已实现的程序，将数据随机划分为5对大小相等的子集，每对都包含两个子集。

对每对子集，分别用其中一个子集训练，另一个子集测试，然后交换进行。将此过程重复5次，总共得到10次学习/测试会话。

针对这10次会话，分别使用两种类别归纳程序进行训练和测试，记录每次会话所选性能标准的值。

对两种归纳技术的性能标准值进行t检验，比较它们之间是否存在显著差异。

以下是Python示例代码：


import numpy as np
from scipy import stats

# 假设data是已划分好的5对大小相等的子集
# 假设induction_technique_1和induction_technique_2是已实现的两个类别归纳程序

# 初始化存储性能标准值的列表
results_1 = []
results_2 = []

# 进行5x2 - CV过程
for i in range(5):
    # 第一次训练和测试
    train_1, test_1 = data[i][0], data[i][1]
    result_1_1 = induction_technique_1(train_1, test_1)
    result_2_1 = induction_technique_2(train_1, test_1)
    results_1.append(result_1_1)
    results_2.append(result_2_1)

    # 第二次训练和测试
    train_2, test_2 = data[i][1], data[i][0]
    result_1_2 = induction_technique_1(train_2, test_2)
    result_2_2 = induction_technique_2(train_2, test_2)
    results_1.append(result_1_2)
    results_2.append(result_2_2)

# 进行t检验
t_statistic, p_value = stats.ttest_ind(results_1, results_2)
print(f't统计量: {t_statistic}')
print(f'p值: {p_value}')

以上代码仅是示例，实际应用中需要根据具体的数据集和归纳程序进行调整。