49. 两艘船在同一时刻驶离河的两岸,一艘船从 A 驶往 B,另一艘船从 B 驶往 A,其中一艘开的比另一艘快些,因此他们在距离较近的岸 5 公里处相遇,到达预定地点后,每艘船要停留 15 分钟。以便乘客上下船,然后他们又返航,这两艘船在距另一岸 1 公里处重新相遇,请问河宽 14 公里。

首先要确认的是 “每艘船要停留 15 分钟” 只是干扰项,可以直接忽略。

设从A开出的船快一些,河宽为 $d$

第一次相遇时 A、B 共走一个河宽,设耗时为 $t$

A -----------------------------------><~~~~~$5$~~~~ B

第二次相遇时 A、B 共走两个河宽,则耗时 $2t$

A ~~~~~~~~~$d-5$~~~~~~~<>----------------- B

A ~~ \(1\)~~><------------------------------------------ B

由上图易知 \(\frac{(d-5)+1}{2t}=\frac{5}{t}\) 则 $d=14$

50. 下列哪个不属于常用的文本分类的特征选择算法?( D )

A.卡方检验值 B.互信息 C.信息增益 D.主成分分析

51. N-Gram 语言模型可用于查询分类。实际能获取到的查询分类训练数据往往带有一定噪音。以下四种模型和训练数据的选择中,哪种能达到最好的实际使用效果?( C )

A. 二元和三元模型,正负例查询词各 2,000,精度 100%

B. 四元模型,正负例查询词各 10,000,精度 85%

C. 一元和二元模型,正负例查询词各 20,000,精度 80%

D. 二元模型,正负例查询词各 5,000,精度 95%

首先可以排除 AB,虽然常用的是一元和二元模型,但也不是说三四元不可用,而是 AB 中给出的数据集相对来说实在是太小了。

D 不如 C 是因为 5000 × 95% < 20000 × 80%

52. 语言模型的参数估计经常使用 MLE(最大似然估计)。面临的—个问题是没有出现的项概率为 0,这样会导致语言模型的效果不好。为了解决这个问题,需要使用:( A )

A.平滑 B.去噪 C.随机插值 D.增加白噪音

平滑估计公式: \(P(e)=\frac{N_e+f_e}{\sum_{e'\in E}(N_{e'}+f_{e'})}\)

简单平滑: $f_e=Constant$

Expected Likelihood Estimation (ELE): $f_e=0.5$

拉普拉斯平滑 Laplace Smoothing: $f_e=1$

Add-tiny Smoothing: \(f_e=1/\sum_{e'\in E}N_{e'}\)

Good-Turing平滑

53. 所有人口中,某癌症的患病率为 0.008。对有癌症的病人,医院的化验测试有 2% 的可能错判其无癌症。对无癌症的病人,有3%的可能错判其有癌症。问:现有一新病人,化验测试表明其有癌症,该病人实际患有癌症的概率是多少?(计算过程四舍五入保留 4 位小数)( C )

A.0.0078 B.00298 C.0.2074 D.0.98

由题知

$P(cancer)=0.008, P(\overline{positive}|cancer)=0.02, P(positive|\overline{cancer})=0.03$

\[\begin{aligned} P(cancer|positive)&=\frac{P(positive|cancer)P(cancer)}{P(positive|cancer)P(cancer)+P(positive|\overline{cancer})P(\overline{cancer})} \\ &\approx\frac{1}{1+\frac{0.0298}{0.0078}} \\ &=1/4.821 \\ &\approx0.2074 \end{aligned}\]

54. 在大规模的语料中,挖掘词的相关性是一个重要的问题。以下哪一个信息不能用于确定两个词的相关性。( B )

A.互信息 B.最大熵 C.卡方检验 D.最大似然比

55. 下列哪个不属于 CRF 模型对于 HMM 和 MEMM 模型的优势 ( B )

A.特征灵活 B.速度快 C.可容纳较多上下文信息 D.全局最优

56. 下列不是 SVM 核函数的是:( B )

A.多项式核函数 B.ogistic 核函数 C.径向基核函数 D.Sigmoid 核函数

57. 下列属于无监督学习的是:( A )

A.K-means B.SVM C.最大熵 D.CRF

58. 以下哪些方法不可以直接来对文本分类 ( A )

A.K-means B.决策树 C.支持向量机 D.KNN

59. 解决隐马模型中预测问题的算法是 ( D )

A.前向算法 B.后向算法 C.Baum-Welch 算法 D.维特比算法

60. 一个有偏的硬币,抛了 100 次,出现 1 次人头,99 次字。问用最大似然估计(ML)和最小均方误差(LSE)估计出现人头的概率哪个大 ( C )

A.ML=MSE B.ML>MSE C.ML<MSE

解一:

\[P(H)_{MLE}=\arg\max\limits_{\hat{\theta}} \hat{\theta}(1-\hat{\theta})^{99}\]

\(\dfrac{d }{d \hat{\theta}}\hat{\theta}(1-\hat{\theta})^{99}=(1-\hat{\theta})^{98}(1-100\hat{\theta})=0\)

则 $P(H)_{MLE}=\frac{1}{100}$

假设真实值 $P(H)=\theta$

那么 \(P(H)_{MMSE}=\arg\min\limits_{\hat{\theta}} \int_{0}^{1} (\hat{\theta}-\theta)^2 p(\theta|D) d \theta \)

\(P(\theta|D) \sim P(D|\theta)P(\theta)\) 而在没有其他信息的情况下,先验地认为 $\theta$ 在 \([0, 1]\) 区间上均匀分布,于是

\[\begin{aligned} P(H)_{MMSE}&=\arg\min\limits_{\hat{\theta}} \int_{0}^{1} (\hat{\theta}-\theta)^2 p(D|\theta) d \theta \\ &=\arg\min\limits_{\hat{\theta}} \int_{0}^{1} (\hat{\theta}-\theta)^2 \theta(1-\theta)^{99} d \theta \end{aligned}\]

令 $x=1-\theta$, \(P(H)_{MMSE}=\arg\min\limits_{\hat{\theta}} \int_{0}^{1} (\hat{\theta}+x-1)^2 (1-x)x^{99} d x\)

WolframAlpha

\[P(H)_{MMSE}=\arg\min\limits_{\hat{\theta}} (5253 \hat{\theta}^2 - 206 \hat{\theta} + constant)\]

\[P(H)_{MMSE}=\frac{1}{51}>P(H)_{MLE}=\frac{1}{100}\]

解二: 用直觉一点的方式,MLE 比较激进,“听风就是雨”,要是没看到人头,就会估计人头的出现概率为 0,而 MMSE 不会。MMSE 比较保守,所造成的效果就是总把估计往先验(在此为均匀分布)均值拉一拉,因此 MLE 估高的 MMSE 就会估小一点儿,MLE 估低 MMSE 就会估大一点儿。

61. a 和 b 两个人每天都会在 7 点 - 8 点之间到同一个车站乘坐公交车,a 坐 101 路公交车,每 5 分钟一班【 7:00, 7:05....】,b 坐 102 路公交车,每 10 分钟一班【 7:03, 7:13...】,问 a 和 b 碰面的概率是多少? ( C )

A. 1/8 B. 41/400 C. 143/1200 D. 199/1800 E. 431/3600

$\dfrac{a}{b} \text{┗━━━┳━┻━━━━━┻━━━┳━┻━━━━━┻┅┅┅┅┅┅┅━━━━━━┻━━━┳━┻━━━━━┛}$

上图表示 7 点 - 8 点之间的 60 分钟区间内,a、b 两人可用的乘车时间点(a 上 b 下)

可以看出每 10 分钟有一个最小循环,那么可以先就前 10 分钟的区间进行分析.

以 b 为主体,b 的时间可以被各时间点切成三份 $(3_{0-3},2_{3-5},5_{5-10})$,那么在这个区间里,两人相遇的概率是

\[\dfrac{3}{60}\times\dfrac{3_{0-3}}{60}+\dfrac{2}{60}\times\dfrac{13_{0-13}}{60}+\dfrac{5}{60}\times\dfrac{8_{5-13}}{60}=\dfrac{75}{3600}\]

需要注意的是后两项 “使用了” 下一个循环区间的时间,因此需要单独考虑最后 10 分钟的相遇概率

\[\dfrac{3}{60}\times\dfrac{3_{50-53}}{60}+\dfrac{2}{60}\times\dfrac{10_{50-60}}{60}+\dfrac{5}{60}\times\dfrac{5_{55-60}}{60}=\dfrac{54}{3600}\]

汇总的相遇概率为

\[\dfrac{75}{3600}\times 5+\dfrac{54}{3600}=\dfrac{143}{1200}\]

62. 假设某日是否有雨只和前一日是否有雨相关:今日有雨,则明日有雨的概率是 0.7;今日无雨,则明日有雨的概率是 0.5。如果周一有雨,求周三也有雨的概率 ( B )

A.0.5 B.0.64 C.0.72 D.0.81

转移矩阵为

\[A=\left(\begin{array}{cc}0.7&0.3\\0.5&0.5\end{array}\right)\]

\[P(\text{周三有雨}|\text{周一有雨})=\left[ (\begin{array}{cc} 1 & 0 \end{array}) A^2 \right]_{1,1}=\left[ (\begin{array}{cc} 0.7 & 0.3 \end{array}) \left(\begin{array}{cc}0.7&0.3\\0.5&0.5\end{array}\right)\right]_{1,1}=0.64\]

63. 在 large-scale 且 sparse 的数据分析中,knn 的 k 个最近邻应该如何选择 ( D )

A.随机选择 B.L1-norm 最近的 C.L2-norm 最近的 D.不用 knn