Math
Fun Math
-
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
答：可以用二进制编码的思维来解决。先对 1000 个瓶子以二进制数的形式进行编号，则至少需要十位的二进制数进行表示。再用这10只小白鼠分别对应二进制数的 10 个数位，让每只小白鼠喝下编号对应数位值为 1 的瓶子。最后根据小白鼠的死亡情况得到一个十位二进制数，编号与其相等的瓶子里面有毒药。
-
1000 桶水，其中一桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
答：由于一只猪总共有五种状态，所以可以用五进制的方法解决，将 1000桶水表示成五进制至少需要 5 位，所以至少需要五头猪。
-
1000 桶水中两桶有毒，猪喝毒水后会在 15 分钟内死去，想用一个小时找到毒水，至少需要几只猪？如何实现？
答：从理论上来讲，1000 桶水两桶有毒，有 499500 种状态，而一头猪有 5 种状态，求解 5^l > 499500，求得 l > 8.15，所以 9 只猪就可以找到毒水：
a. 我们先把1000桶水分为10组，每只猪试验一组，一组空白；
b. 如果只有一只猪死，那么说明两桶毒水都在那 100 桶水中，再把这 100 桶水分为 10 组，剩下的 9 只猪试验 9 组，另外 10 桶不实验，这样问题可一步一步缩小；
c. 如果有两只猪死，则说明有两组 100 桶水各有一桶毒水，每组用 3 头猪即可实验。
-
一个村子里有很多户人家，每家都养了一条狗。现在发现村子里面出现了 n 只疯狗，村里规定，谁要是发现了自己的狗是疯狗，就要将自己的狗枪毙。但问题是，村子里面的人只能看出别人家的狗是不是疯狗，而不能看出自己的狗是不是疯的，如果看出别人家的狗是疯狗，也不能告诉别人。于是大家开始观察，第一天晚上，没有枪声，第二天晚上，没有枪声，直到第 n 天晚上，这 n 只狗才被同时枪毙，请问这是为什么？
答：具体分析流程如下：
a. 首先从只有一条疯狗分析起，如果只有一条疯狗，那么疯狗的主人在第 1 天就会发现其他家庭一只疯狗都没有，从而枪毙自己家的狗；
b. 如果有两条疯狗，那么拥有疯狗的家庭在第一天由于看到别人家有疯狗，就不会枪毙自己家的狗，但发现第一晚没人枪毙自己的狗后，他会知道村子里有两条疯狗，其中一条就是自己的。实际上，整个村子的人都会在第一晚没人枪毙自己的狗后，知道整个村子至少有两条疯狗；
c. 继续分析，如果第二晚还没有枪声，那说明拥有疯狗的人都看到了至少两条疯狗，所以他不会认为自己拥有疯狗，但经过没有枪声的第二晚后，全村人便达成了村子至少有三条疯狗的事实；
d. 同理可得，拥有疯狗的家庭由于能看到 n - 1 条狗，他需要 n 天才能判断村子里至少有 n 条疯狗，其中一条就是自己家的狗，从而在第 n 天晚上枪毙自己家的狗。
-
五个同事决定计算他们的平均工资，在大家互相不告诉薪水的情况下，如何才能做到这一点？
答：这道题的方法有很多，比如有：
a. 每个人把自己的工资随意拆成四个数的和，分别把四个数字告诉自己以外的四个人；每个人手里收到四个数字，加起来，报出；五个人的数字相加，即可得到五个人的总收入，除以5得到平均工资；
b. 找个计算器，叫第一个人输入一个巨大的不规则的数，然后把自己的收入加上去，之后依次传给其他人，每人都把自己的收入加上之前的数。最后传回第一个人。第一个人再把最后的总和减去他选中的那个不规则数，然后除以人数，即可得到大家的平均。
-
圆桌上有 1 到 1000 号，1 号右手边是 2 号，左手边是 1000 号。1 号开枪打死 2 号，把枪交给 3 号，3 号打死 4 号交给5号。。999 号打死 1000 号后把枪交给 1 号，继续循环。最后留下来的是几号？
答：约瑟夫环问题，套公式 \(f(n) = 2(n - 2^{log_2n}) + 1\) 直接得到结果为 977。
-
一幢 200 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从前 n-1 层扔鸡蛋都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。已知鸡蛋在 0 层扔不会碎。提出一个策略，要保证能测出鸡蛋恰好会碎的楼层，并使此策略在最坏情况下所扔次数最少？
答：这是一道非常经典的面试题，我们用两种方法来解决：
a. 分析法：对于每一次扔鸡蛋，都可以看作是一次决策，所以最终扔的方案应该是构成一棵决策树，问题就可以转换成求最矮决策树的高度。假设第一次扔的楼层是第 k 层楼，则碎子树的高度为 k - 1，如果第一次扔鸡蛋没碎，则设第二次扔的高度为 m，则对于 m 来讲，其碎子树高度为 m - k - 1，相对根节点高度则为 m - k。由于要尽可能保证子树的高度一致，所以得 m - k = k - 1，故可得第二次扔的高度要比前一次高 k - 1 层。从而得到方程 k(k + 1) / 2 = 200，从而解得高度为 14；
b. 动态规划法：这道题是很经典的动态规划问题，设楼层次数为 n，我们可以得到状态转移方程
f(n) = min(max(k-1, f(n - k))) + 1 (0 < k <= n)，如果我们再加入鸡蛋数目变量 m，则状态转移方程为f(n, m) = min(max(f(k - 1, m - 1), f(n - k, m))) + 1 (0 < k <= n)。 -
海盗博弈
-
五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？
答：链接
-
三个极度嫉妒的人分一个蛋糕，采用什么策略，能让三人都觉得公平？
答：链接
-
有 5 个直线排列的洞，兔子每天换一个相邻的洞，每天插一次，怎样做一定能找到兔子，次数不限。
答：第一天，守住第二个洞，没有的话，第二天还守住第二个洞，还没有的话，一二洞可排除，兔子前两天一定不会在一二两个洞，第三天检查第三个洞，如果没有，此时，兔子只可能在第二四五三个洞，第四天检查第四个洞，如果还没有，说明只可能在一三五三个洞，第五天还检查第四个洞，如果没有的话，说明兔子不可能在第四五个洞，也不可能在第一三个洞，只可能在第二个洞，第六天检查第三个洞，如果没有，第七天一定可以在第二个洞里抓到它的。
-
64 匹马，8 个赛道，找出跑得最快的 4 匹马，至少比赛几场？
答：链接
-
有 8 个台球，其中一个比其他的 7 个都要重一些。如果仅仅是使用天平而不称出具体的重量，请问最少几次能找出那个最重的台球？
答：2 次。把所有的球分成 3 组，其中 2 组是 3 个球，最后一组是两个球。首先，把 3 个球的两组放在天平上。如果其中一方比较重，把偏重的那一组球任意拿出来两个放在天平上。如果两组球一样重，那就把剩下的 2 个球放在天平上称重。
-
有 n 名球员参加比赛，第一轮抽签两两对决，如果 n 为奇数，则剩下一人轮空，后面的轮次采取类似做法。问总共有几场比赛？
答：因为总共要淘汰 n - 1 人，所以比赛场数为 n - 1 场。
-
一瓶可乐两元钱，喝完后两个空瓶可以换一瓶可乐，假设你有40块，请问你最多可以喝到几瓶汽水？
答：此题与上题类似，每一次换可乐之后都会损失一个瓶盖，所以 20 瓶可乐可以换到 19 瓶可乐，因此总共可以可以喝到 39 瓶可乐。如果开放借瓶盖的话，由于最后我们只剩一个瓶盖，所以最多只能借一个，而且只有当可乐数不是 2 的幂的时候借，因此，如果可以借的话总共可以喝 40 瓶可乐。
-
0， 6， 24，60， 120，（）?
答：0=0*1*2；6=1*2*3；24=2*3*4；60=3*4*5；120=4*5*6；210=5*6*7。
-
黑色硬币问题
答：链接
-
难铺的瓷砖
答：链接
-
共 10 瓶药丸。（1）其中一瓶每颗超重 10 毫克；（2）其中多瓶每颗超重 10 毫克。用最少称重数目给出错误的瓶号。
答：（1）从 1 到 10 瓶，每瓶拿出 1、2、3、…、10 颗；（2） 从 1 到 10 瓶，每瓶各拿出 1、2、4、…、1024 颗。
-
捡麦穗问题
答：链接
Statistics
-
为什么样本方差（sample variance）的分母（denominator）是 \(n - 1\)？
答：如果期望已知，分母就是 \(n\)，如果未知，分母是 \(n - 1\) 是为了保证方差的估计是无偏的（unbiased）。如果直接使用 \(n\) 为分母作为估计，那么会倾向于低估方差（可用数学方法证明），所以为了正确的估计方差，所以可以把原先的估计值稍微放大一点，即把分母 \(n\) 改为 \(n - 1\)。
这里也可以用自由度（随机变量中可以同时自由随机变化的变量数目，Degree of Freedom）的角度进行分析。对于 \(n\) 个样本，由于已经根据这些样本估计了样本均值，因此只剩下 \(n - 1\) 个样本的值是可以变化的。换句话说，样本中原有的 \(n\) 个自由度，有一个被分配给计算样本均值，剩下自由度即为 \(n - 1\)，所以用 \(n - 1\) 作为分母来计算样本方差。
-
给一枚硬币，但扔出正反的概率未知，如何得到等概率的二元随机数？
答：扔两次，00、11 时无输出重扔，01 输出 0，10 输出 1。
-
如何用一个骰子等概率地生成 1 到 7 的随机数？
答：将一个筛子扔两次可以得到 36 种组合，每五种组合代表一个数字，剩下的一种表示重扔。
-
抛的硬币直到连续出现两次正面为止，平均要扔多少次？
答：用马尔可夫链，可做图求解递归方程。
假定扔出正面 (H) 的概率为 p，扔出反面 (T) 的概率为 1 - p。我们需要扔出连续 2 个 H。在整个过程有这么几种状态：
a. 当前连续 0 个正面（0H）；
b. 当前连续 1 个正面（1H）；
c. 当前连续 2 个正面（2H）。
如果当前是 0H，那么 p 的概率，下一个状态是 1H；1 - p 的概率维持在 0H。
如果当前是 1H，那么 p 的概率，下一个状态为 2H（达到条件，任务完成）；1 - p 的概率回到 0H。
假设期望 x 次后，得到 2H，则有 \(x = (1 − p)(1 + x) + p^2 × 2 + p(1 − p)(2 + x)\)，可解得 x = 6。
-
假设有某种病毒，每个病毒每秒钟会以 1/3 的概率分裂成两个病毒，1/3 的概率不分裂（还是一个），1/3 的概率消亡（变成 0 个）。在最初时刻，玻璃罩中有一个病毒，那么最终玻璃罩内没有活着的病毒概率是多大？
答：链接
-
一米长的绳子，随机剪两刀，最长的一段有多长？
答：假设三段的长度从小到大依次为 a，a + b，a + b + c，并且满足 a + a + b + a + b + c = 3a + 2b + c = 1 以及 a > 0，b ≥ 0，c ≥ 0。
则可以得到 a ≤ 1/3，b ≤ 1/2，c ≤ 1，不妨可以认为 a ∼ U(0, 2k)，b ∼ U(0, 3k)，c∼U(0, 6k)。
绳子最长的一段的期望为 k + 1.5k + 3k = 5.5k，绳子长度的期望为 3k + 3k + 3k = 9k。因为 9k = 1，所以 5.5k = 11/18 = 0.61111。
-
一根绳子切成三段，组成三角形的几率是多少？
答：链接
-
给定一个 0 到 1 的均匀分布，如何近似地生成一个标准正态分布。即用 numpy.random.uniform() 这个函数， 得到 numpy.random.normal()？
答：本题考点为中心极限定理（Central Limit Theorems）和均匀分布。中心极限定理即一组相互独立的随机变量的均值符合正态分布。
np.random.uniform()生成的是 (0, 1) 之间均匀分布的随机数，则2 * np.random.uniform() - 1生成的是 (-1, 1) 之间均匀分布的随机数。已知 U(a, b) 方差是 (a - b)^2 / 12，则含有 n 个样本的样本均值的方差是 (a - b)^2 / 12 / n。代码如下：
import numpy as np normal_rv = 30 * np.mean(2 * np.random.uniform(size=300) - 1)具体步骤是先产生 300 个 (-1, 1) 随机变量，它们的均值的标准差是 1 / 30，要得到标准正态分布，所以要乘以 30。
-
假设一段公路上，1 小时内有汽车经过的概率为96%，那么，30分钟内有汽车经过的概率为？
答：一小时有车的概率 = 1 - 一小时没车的概率 = 1 - 两个半小时都没车的概率 = 1 - (1 - 半小时有车的概率)^2。
-
一枚不均匀硬币，抛了 100 次，有 70 次朝上，第 101 次朝上的概率是多少，公式是如何推导？
答：7/10。二项分布的极大似然估计，可参考此链接。
-
4个人，52张扑克牌，红桃 A 和黑桃 A 同时被一个人拿到的概率？
答：解法一：C(1,4) * C(11,50) / C(13,52)，C(1,4) = 从四个人中任选 1 人为红桃 A + 黑桃 A，C(11,50) = 从剩余 50 张牌中抽取 11 张给指定人，C(13,52) = 从 52 张牌中随机抽取 13 张；
解法二：对于抓到红桃 A 的人，再抓黑桃 A 的概率就是 12/51 = 4/17。
-
假设有一副被打乱的扑克牌，52 张，其中 13 张黑桃，一个人从这副牌里随机的抽牌，每次抽一张，并且不放回，假设在第X次抽牌的时候，第一次抽到黑桃。请问 X 的数学期望是多少?
答：链接
-
三个人告诉你深圳下雨了，每个人说谎概率是1/3，那么深圳下雨概率是多少?
答：8/9。
-
蒲丰投针问题
答：链接
-
中餐馆过程
答：链接
-
鹰鸽博弈
答：链接
-
两个人轮流抛硬币，规定第一个抛出正面的人可以吃到苹果，请问先抛的人能吃到苹果的概率多大？
答：先抛的人吃到苹果的概率：\(1/2 + 1/2^3 + 1/2^5 + ...\)，求得结果为 \(2/3\)。另一种解法是设先抛先吃的概率为 \(p_1\)， 后抛先吃的概率为 \(p_2\)，有：\(p_1 = 1/2 + 1/2 * p_2\) 且 \(p_1 + p_2 = 1\)，解方程可得，\(p_1 = 2/3\)。如果题目说是只抛一次的话，则概率为 \(1/2\)。
-
幼儿园 10 个小朋友排成一列，其中 3 个小朋友是女孩，求女孩排在一起的概率？
答：所有人排列是 10!，三个小女孩看做整体排列是 8!，三个小女孩排列是 3!，最后结果就是 (8! * 3!) / 10! = 1/15。
-
一个骰子，6 面，1 个面是 1， 2 个面是 2， 3 个面是 3， 问平均掷多少次能使 1、2、3 都至少出现一次？
答：链接
-
村长带着 4 对父子参加爸爸去哪儿第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走有个前年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么 4 对父子在圆桌上共有几种坐法？
答：链接
-
一个点用偶数步从原点出发回到原点有几种走法？
答：链接
-
什么是卡方检验？
答：卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度，实际观测值与理论推断值之间的偏离程度就决定卡方值的大小，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若两个值完全相等时，卡方值就为0，表明理论值完全符合。
-
什么是点估计，什么是区间估计？
答：点估计是预测参数的值，区间估计是预测参数所处的区间。
-
什么是置信区间，什么是置信水平/置信度？
答：置信区间是一个带着置信度的估计区间。若置信区间为 \([a, b]\)，则置信水平 Y% 表示 \(P(a < \mu < b) = Y%\)。常见的置信度为 95%（\(2\sigma\)），95% 置信度表示的是 100 次区间估计，其中约有 95 次区间估计得到的区间结果包含正确的参数值。
根据大数定律和中心极限定律，样本均值 \(M \sim N(\mu, \sigma^2/n)\)，其中 \(\mu\) 为抽样总体分布期望，\(\sigma^2\) 为抽样总体分布方差，\(n\) 为样本数目。
求置信区间的方式是先计算抽样样本的均值和方差，然后再根据设置的置信区间查表就可以得到置信区间的上下界。
-
频率派概率和贝叶斯概率有什么区别？
答：频率派概率是最大似然估计，贝叶斯概率是最大后验估计。频率派从自然角度出发，直接为事件建模，即事件 A 在独立重复试验中发生的频率趋于概率 p。贝叶斯派则认为概率是不确定的，需要结合先验概率和似然概率来得到后验概率。随着数据量的增加，参数分布会向数据靠拢，先验的影响越来越小。
-
先验概率是什么？后验概率是什么？
答：\(p(\theta \| x)=\frac{p(x \| \theta)p(\theta)}{p(x)}\)。\(x\) 为观察得到的数据（结果），\(\theta\) 为决定数据分布的参数（原因），\(p(\theta \| x)\) 为后验分布，\(p(\theta)\) 为先验分布，\(p(x \| \theta)\) 为似然。
Algorithm
-
有 10 个排好序的数据库，那么我要找整个的中位数，怎么找？
答：最简单的思路是合并数据库，然后再定位长度，时间复杂度为 O(n)，空间复杂度是 O(n)；但实际上只需要借鉴这个合并的过程，当合并到中位数的时候输出中位数即可，时间复杂度为 O(n)，空间复杂度是 O(1)。这思路十分简单，但并不是最佳算法，有序数组让我们想到的会是二分查找，因此我们可以利用二分查找来使复杂度降至 O(logn)，具体可参考：
a. https://www.douban.com/note/177571938/
b. https://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays
-
稳定排序？
答：稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序；
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
-
原地排序与非原地排序？
答：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。非原地排序就是要利用额外的数组。
-
数组最大最小值最优算法？
答：链接
-
无序整数数组中找第 k 大的数？
答：链接
-
在 n 个数中取最大的 k 个数，时间复杂度是？
答：nlogk。堆的大小为 k，总共要调整 n 次。
-
不用库函数求一个数的立方根？
答：链接
-
二进制中 1 的个数？
答：把一个整数减去 1，再和原整数做与运算，会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中有多少个 1，就可以进行多少次这样的操作。具体解题思路可参见《剑指 Offer》。
-
8 位二进制整型补码表示取值范围是？
答：-2^32 到 2^32 - 1。补码中正负 0 统一用正 0 表示，所以负数多出一个数。
-
数值的整数次方？
答：链接
-
有两个未知整数，你可以不断询问某个数与这两个数的大小关系（每次询问一个数），该如何查找这两个数？
答：链接
-
一群木板，一开始有一条线把它们固定在一条水平线上，现在抽掉这条线，有的木板往下掉落，有的木板位置上升，问怎么移动才能使移动距离最小，让它们继续在一条水平线上？
答：中位数。
-
给定两个数，求他们无限次相加中第 k 小的数？
答：链接
-
了解 Hamming 距离吗？
答：两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
-
如何求两个数的二进制表示的 Hamming 距离？
答：先求两个数的异或结果 res，再依次求 res 每一位与 1 与操作的结果，不为 0，则 Hamming 距离加一；每判断完一位，res 右移一位继续判断下一位。
-
汉诺塔时间复杂度？
答：假设移动 n 个圆盘需要 f(n) 次移动
首先考虑一个圆盘，只需一步就可以了 f(1) = 1 …… ①
现在考虑 n 个圆盘，假设开始圆盘在 A 柱，可以先把 A 柱的上面 n - 1个圆盘移到 B，再将 A 剩下的一个移到 C，最后将 B 的 n - 1 个移到 C。总共需要 f(n) = 2f(n- 1) + 1 …… ②
根据 ①② 两式，可求出 f(n) = 2^n - 1 所以 O(n) = 2^n
-
尾递归（Tail Call）有什么危害，如何避免？
答：栈溢出（Stack Overflow）。尾递归事实上和循环是等价的。
-
红黑树是什么？
答：红黑树性能要好于平衡二叉树。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
-
判断图存在环？
答：拓扑排序（Topological Sorting），深度遍历。
-
最短路径算法及复杂度？
Dijkstra 算法，时间复杂度为 O(V^2)，如果是稀疏图，可用堆进行优化，时间复杂度为 O((V + E) lgV)；Floyd 算法，时间复杂度为 O(V^3)。
-
最小生成树算法及复杂度？
Prim 算法，O(V^2)；Kruskal 算法，O(ElgE)。
-
农夫过河问题？
答：链接
-
Nim 问题?
答：必败态当且仅当所有堆硬币的数量都异或起来结果为 0。
-
Key Algorithms
Computer Science
Operating Systems
-
为什么要用时间复杂度来描述算法，而不是运行时间？
答：操作系统调度，所以运行时间不一定相同。
-
死锁的条件
答：a.互斥：某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。 b.占有且等待：一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源
c.不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。
d.循环等待：存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。
-
死锁避免方法
答：产生死锁需要四个条件，那么，只要这四个条件中至少有一个条件得不到满足，就不可能发生死锁了。
-
银行家算法
答：链接
Computer Networks
-
集线器和交换机有什么区别？
答：集线器在物理层，所有端口是一个冲突域，交换机在数据链路层，每个端口是一个冲突域。
-
三次握手是怎样的？
答：第一次握手：建立连接时，客户端发送 syn 包（syn = j）到服务器，并进入 SYN_SENT 状态，等服务器确认；
第二次握手：服务器收到 syn 包，必须确认客户的 SYN（ack = j + 1），同时自己也发送一个 SYN 包（syn = k），即 SYN + ACK 包，此时服务器进入 SYN_RECV 状态；
第三次握手：客户端收到服务器的 SYN + ACK 包，向服务器]发送确认包ACK (ack = k + 1），此包发送完毕，客户端和服务器进入 ESTABLISHED（TCP 连接成功）状态，完成三次握手。
-
四次挥手是怎样的？
答：TCP 客户端发送一个 FIN，用来关闭客户到服务器的数据传送。
服务器收到这个 FIN，它发回一个 ACK，确认序号为收到的序号加 1。和 SYN 一样，一个FIN 将占用一个序号。
服务器关闭客户端的连接，发送一个 FIN 给客户端。
客户端发回 ACK 报文确认，并将确认序号设置为收到序号加 1。
Database Systems
-
count(1)、count(*) 和 count(列名) 的区别？
答：链接
-
数据库的三级模式是什么？
答：数据库领域公认的标准结构是三级模式结构，包括外模式、概念模式、内模式。
用户级对应外模式。它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。
概念级对应概念模式（又称逻辑模式），反映了数据库的整体观。它是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图。
物理级对应内模式（又称存储模式），反映了数据库的存储观。它是数据库中全体数据的内部表示或底层描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库。
-
数据库三范式？
答：链接
Programming
C/C++
-
字节对齐？
答：先看以下程序：
struct A{ int a; char b; short c; }; struct B{ char b; int a; short c; };已知 32 位机器上各数据类型的长度为：char 为 1 字节、short 为 2 字节、int 为 4 字节、long 为 4 字节、float 为 4 字节、double 为 8 字节。那么上面两个结构体大小如何呢？
结果是：sizeof(strcut A) 值为 8；sizeof(struct B) 的值却是 12。
结构体 A 中包含一个 4 字节的 int 数据，一个 1 字节 char 数据和一个 2 字节 short 数据；B 也一样。按理说 A 和 B大小应该都是 7 字节。之所以出现上述结果，就是因为编译器要对数据成员在空间上进行对齐。
a.数据类型自身的对齐值：char 型数据自身对齐值为 1 字节，short 型数据为 2 字节，int / float 型为 4 字节，double 型为 8 字节。
b.结构体或类的自身对齐值：其成员中自身对齐值最大的那个值。
c.指定对齐值：#pragma pack (value) 时的指定对齐值 value。
d.数据成员、结构体和类的有效对齐值：自身对齐值和指定对齐值中较小者，即有效对齐值 = min{自身对齐值，当前指定的 pack 值}。
-
面对对象的三大特性是什么？
答：封装、继承和多态。
-
定义一个空类时，C++ 到底会默默为我们编写哪些函数？
答：4 个函数：一个 default 构造函数、一个析构函数、一个 copy 构造函数、一个等号 “=” 重构函数。
-
C++ 的构造函数可以是虚的嘛？析构函数呢？
答：构造函数不能为虚函数，而析构函数可以且常常是虚函数。
-
C++ 中的抽象类是什么？
答：定义了纯虚函数的类称为抽象类，抽象类不能被实例化，抽象方法只能声明于抽象类中，且不包含任何实现，派生类必须覆盖它们。抽象类也可派生自一个抽象类。
-
C++ 中的虚函数是什么？
答：C++ 的多态性是通过虚函数实现的，虚函数必须存在于继承环境下。虚函数是重载的一种表现形式。只有类的普通成员函数可以定义为虚函数，全局函数及静态成员函数（类拥有）不能声明为虚函数。
-
C++ 中的纯虚函数是什么？
答：virtual 函数类型 函数名（形参表列）= 0。抽象类中定义的，为了派生类中的使用而声明定义的。
-
C++ 中的抽象类和接口有什么区别？
答：一个类一次可以实现若干个接口，但是只能扩展一个父类。
-
C++ 中的 public、private 和 protected 是什么？
答：a. 公有（public）成员可以在类外访问。
b. 私有（private）成员只能被该类的成员函数访问。
c. 保护（protected）成员只能被该类的成员函数或派生类的成员函数访问。
Python
-
Python 中的 *args 和 **kwargs 是什么意思？
答：*args 表示可变参数（variadic arguments），它允许你传入 0 个或任意个无名参数，这些参数在函数调用时自动组装为一个 tuple； **kwargs 表示关键字参数（keyword arguments），它允许你传入 0 个或任意个含参数名的参数，这些关键字参数在函数内部自动组装为一个 dict。同时使用 *args 和 **kwargs 的时候，必须保证 *args 在 **kwargs 之前。 *args 是变量 list，**kwargs 是指针 list。
-
__new__ 了解吗？
答：__init__ 作用是类实例进行初始化，第一个参数为 self，代表对象本身，可以没有返回值。__new__ 则是返回一个新的类的实例，第一个参数是 cls 代表该类本身，必须有返回值。__new__ 先执行，然后再 __init__，实际上，只要 __new__ 返回的是类本身的实例，它会自动调用 __init__ 进行初始化。但是有例外，如果 __new__ 返回的是其他类的实例，则它不会调用当前类的 __init__。
-
__name__ 的值怎么确定？
答：链接
-
map() 返回的对象是什么？
答：map() 函数返回的是一个迭代器，并对返回结果使用了 yield，所以其返回结果只能使用一次，这样做在于节省内存。
-
[[1, 2], [3, 4], [5, 6]] 一行代码展开该列表，得出 [1, 2, 3, 4, 5, 6]
答：
[j for i in [[1,2],[3,4],[5,6]] for j in i] -
Python 中怎么转换 ascii 码和字符？
答：
chr(65)和ord('A')。 -
len('中文')和len('中文'.encode('utf-8'))的输出分别是多少？答：2 和 6，Python 默认是 Unicode 编码，转换成 UTF-8 编码，中文通常占用三个字符，英文一个。
-
一行代码将字符串 “->” 插入到 “abcdefg” 中每个字符的中间
答：
"->".join("abcdef") -
Python 的匿名函数是什么
答：就是 lambda 函数，一般用来实现简单的功能，如加法
(lambda x, y: x + y)(3, 4)。 -
@staticmethod 和 @classmethod 的作用与区别
答：链接
-
Python 的 getter 和 setter 是什么？
答：@property 和 @name.setter。
-
Python 参数传递
答：链接
-
Python 赋值、浅拷贝和深拷贝
答：链接
-
装饰器的意义和使用？
答：用来实现代码复用，增强代码可读性。
def deco(func): def warpper(*args, **kwargs): print('start') func(*args, **kwargs) print('end') return warpper @deco def myfunc(parameter): print("run with %s" % parameter) myfunc("something") -
解释一下多态？
答：多态的好处就是，当我们需要传入
Dog、Cat、Tortoise……时，我们只需要接收Animal类型就可以了，因为Dog、Cat、Tortoise都是Animal类型，然后，按照Animal类型进行操作即可。由于Animal类型有run()方法，因此，传入的任意类型，只要是Animal类或子类，就会自动调用实际类型的run()方法，这就是多态的意思：对于一个变量，我们只需要知道它是
Animal类型，无需确切地知道它的子类型，就可以放心地调用run()方法，而具体调用的run()方法是作用在Animal、Dog、Cat还是Tortoise对象上，由运行时该对象的确切类型决定，这就是多态真正的威力：调用方只管调用，不管细节，而当我们新增一种Animal的子类时，只要确保run()方法编写正确，不用管原来的代码是如何调用的。 -
鸭子类型是什么？
答：对于 Python 这样的动态语言，则不一定需要传入
Animal类型。我们只需要保证传入的对象有一个run()方法就可以了：这就是动态语言的“鸭子类型”，它并不要求严格的继承体系，一个对象只要“看起来像鸭子，走起路来像鸭子”，那它就可以被看做是鸭子。 -
Counter 与运算和或运算
答：与和或操作分别返回两个 Counter 各元素的最小值和最大值。得到的 Counter 对象将删除小于 1 的元素。
-
Python 多线程？
答：对于 CPU 密集型，由于全局解释器锁（访问 Python 虚拟机）的存在，所以线程是线性执行的；对于 I/O 密集型，由于全局解释器锁会被释放，所以这时多线程有体现作用。
Linux
-
程序如何后台运行？
答：链接
Machine Learning
Basic
-
解释一下奥卡姆剃刀原理？
答：如果两个模型的预测能力差不多，就选简单的。原因有二，简单模型往往解释性更好；复杂的模型更有可能过拟合。
-
解释一下没有免费的午餐原理？
答：A 算法在某些数据集或任务上表现比 B 算法好，则一定存在一些数据集或任务，B 算法表现比 A 算法好。这告诉我们具体问题具体分析。
-
L1 和 L2 的联系和区别？
答：都是正则化系数，L1（Lasso）得到稀疏的权值，用于特征选择，L2（Ridge）得到平滑的权值。
-
为什么 L1 更容易得到稀疏解？
答：因为损失函数的等高线易与 L1 正则的坐标轴上的点相切。第一象限与正方形相切的圆的中心只能是在第一象限正方形边的垂直区域内，而第一象限的圆都可以与中心点的圆相切。
The question can be answered in a geometric view. L1 loss can be represented as a diamond, while L2 loss can be represented as a circle. Therefore, the loss is likely to intersect with the diamond on only one point, which is in axises.
-
结构风险和经验风险分别是什么？
答：经验风险就是使所有训练样本的损失平均值最小，结构风险其实就是加多一个正则项。
-
什么是生成模型，什么是判别模型？
答：生成模型：学习得到联合概率分布 P(x, y)，即特征 x 和标记 y 共同出现的概率，然后求条件概率分布。能够学习到数据生成的机制。
判别模型：学习得到条件概率分布 P(y | x)，即在特征 x 出现的情况下标记 y 出现的概率。
数据要求：生成模型需要的数据量比较大，能够较好地估计概率密度；而判别模型对数据样本量的要求没有那么多。**
-
什么是参数模型，什么是非参数模型？
答：参数模型假设总体服从某分布，该分布由一些参数确定；非参数模型对于总体分布不做任何假设，只有在给定一些样本的条件下，能够依据非参数统计的方法进行推断。
-
拉普拉斯平滑是什么？
答：为了解决零概率问题：如果某个量 x，在训练集中没有出现过，会导致概率结果是 0。这是不合理的，不能因为一个事件没有观察到就武断的认为该事件的概率是 0。拉普拉斯平滑即加法平滑。假定训练样本很大时，每个分量 x 的计数加 1 造成的估计概率变化可以忽略不计，但可以方便有效的避免零概率问题。
-
bias 和 variance 的含义是什么？
答：bias 要求让 Error(train) 尽可能小，variance 要求让 Error(train) 尽可能等于 Error(test)。bias 体现了模型的精确度，variance 体现了模型的泛化能力。两个值都是希望越小越好。
-
map，mrr 是什么？
答：链接
-
宏平均 F1 和 微平均 F1 的区别？
答：宏平均 F1 对每个类求 F1 之后取平均，微平均 F1 针对整体求 F1。
Regression
-
手推 LR？
答：链接
-
逻辑斯特回归为什么不能用均方误差计算损失函数？
答：链接。另外也因为 LR 的极大似然等价于交叉熵。
-
为什么 LR 要用 sigmoid 函数？
答：链接
-
逻辑斯特回归为什么要对特征进行离散化？
答：模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。
a. 离散特征的增加和减少都很容易，易于模型的快速迭代；
b. 稀疏向量内积乘法运算速度快；
c. 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄 >30 是 1，否则 0。如果特征没有离散化，一个异常数据“年龄 300 岁”会给模型造成很大的干扰；
d. 变量离散化为相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；
e. 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20 - 30 作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；
f. 特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。
-
给一个有 m 个样本，n 维特征的数据集，如果用 LR 算法，那么梯度是几维？
答：n 维。
-
如何用机器学习算法计算特征重要性？
答：LR 后看系数。
-
线性回归中特征不小心重复会有影响吗？
答：会，导致矩阵不可逆。
-
最小二乘法为什么可以解决线性回归问题？
答：残差满足正态分布时，用最大似然估计法可以证明最小二乘法是合理的。
-
描述一下最小二乘法的几何意义？
答：最小二乘法中的几何意义是高维空间中的一个向量在低维子空间的投影。\(WX\) 实际上是当前样本形成的线性组合空间 \(S\)，最小化的过程是找到一个合适的 \(W\)，使得不在 \(S\) 上的 \(Y\) 到 \(S\) 的投影距离最小。
-
正规方程是什么？它有什么作用？
答：\((X^TX)^{-1}X^Ty\)。可以一次运算得出结果，但特征数目过多时不适用。
-
用最小二乘法实现线性回归
答：
import numpy as np # 1. 生成数据（y = 2x + 3 + noise） np.random.seed(42) X = np.random.rand(100, 1) # 100 个样本，1 个特征 y = 2 * X[:, 0] + 3 + np.random.randn(100) * 0.1 # 添加噪声 # 2. 添加偏置项 x0 = 1（扩展 X 为 [x, 1]） X_b = np.c_[X, np.ones((X.shape[0], 1))] # shape: [100, 2] # 3. 正规方程解：theta = (X^T X)^(-1) X^T y theta = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y print("权重和偏置（w, b）：", theta) -
用梯度下降实现线性回归
答：
# 初始化 w = np.random.randn() b = np.random.randn() lr = 0.1 for epoch in range(1000): y_pred = w * X[:, 0] + b error = y_pred - y loss = (error ** 2).mean() # 手动计算梯度 grad_w = 2 * (error * X[:, 0]).mean() grad_b = 2 * error.mean() # 更新参数 w -= lr * grad_w b -= lr * grad_b if epoch % 100 == 0: print(f"Epoch {epoch}: loss={loss:.4f}, w={w:.4f}, b={b:.4f}")
Classification
-
单层感知机为什么不能解决异或问题？
答：因为异或操作需要两条线来划分边界，而单层感知机可以理解为一个线性分类器，只能解决与、或、非问题。
-
如何对单层感知机进行改进，使其能够解决异或问题？
答：多层感知机，或在进入激活函数前加一个多项式模块，从而添加非线性成分。
-
怎么判断分类器是线性分类器还是非线性分类器？
答：根据决策面是否是线性的。
-
KNN 的训练损失是多少？
答：KNN 实际上不算训练，损失为 0。
-
KNN 算法的 k 值应该如何选择？
答：k 值太小，模型复杂度较高，容易过拟合；k 值太大，模型复杂度不够，较远的点也可能影响分类结果，分类模糊，导致分类结果不理想。当 k 取训练集大小时，分类结果都为训练集中最多的类。k 值一般选取较小的值，且要低于训练样本数的平方根，可以使用交叉验证法选取。
-
KNN 怎么更快地找到最近邻点？
答：KD 树和 ball 树，KD 树根据样本构建，但训练样例远大于特征维度时才适用。
-
KNN 算法可以根据距离加权吗？
答：可以用反函数或高斯函数进行距离加权，前者为近邻样本赋予较大权重，稍远的会衰减地很快，因此对噪声数据比较敏感，后者能解决这个问题，但比较复杂。
-
常见的距离度量方法有哪些？
答：\(L_p\) 距离 / Minkowski 距离 / 闵式距离是最常规的距离度量方式，其公式为 \((\|x-y\|^p)^{1/p}\)。当 \(p = 1\) 时为曼哈顿距离，\(p = 2\) 时为欧式距离，\(p\) 为无穷大时为各个坐标距离的最大值，即切比雪夫距离。
-
衡量相似度的方法？
答：欧式距离，Jaccard 相似度（两集合交集大小 / 并集大小），余弦相似度，皮尔逊相关系数（数值归一化后计算余弦相似度），汉明距离。
-
什么是支持向量机？
答：支持向量机就是构造一个的超平面，使得距离超平面最近的那些点，即支持向量与超平面之间的 margin 最大，从而将两个集合分开。
-
LR 和 SVM 的联系与区别？
答：链接
联系：都可以处理分类问题（一般为线性二分类）；都可以增加不同正则化项。两种算法性能接近；两个方法都增加对分类影响较大的数据点的权重，SVM 是只考虑 support vectors，LR 是通过非线性映射，减小了离分类平面较远的点的权重。
区别：LR 是参数模型，SVM 是非参数模型；从目标函数来看，LR 采用的是 log loss，SVM 采用的是 hinge loss。
-
当数据线性可分、接近线性可分以及线性不可分时，分别使用什么 SVM？
答：硬间隔最大化、软间隔最大化以及核技巧。
-
SVM 为什么采用间隔最大化？
答：当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。
-
手推 SVM
答：
超平面：\(y=w^TX+b\)；
样本点 \(P(x_i, y_i)\) 到超平面的几何距离：\(\frac{\|w^Tx_i+b\|}{\|w\|}\)；
样本点 \(P(x_i, y_i)\) 到超平面的几何间隔：\(y_i\frac{w^Tx_i+b}{\|w\|} \geq 0\)；
SVM 解决问题：\(\max_{w,b}{\min_{x_i}y_i\frac{w^Tx_i+b}{\|w\|}}\)；
由于 \(w, b\) 可缩放，所以令最近点满足 \(y_i(w^Tx_i+b)=1\)，问题转换为 \(\max_{w}{\frac{1}{\|w\|}} \ \ s.t. \ \ y_i(w^Tx_i + b) \geq 1\)；
定义拉格朗日函数：\(L(w, b, \alpha) = \frac{1}{2} \|w\|^2 + \sum_{i = 1}^m{\alpha_i(1 - y_i(w^Tx_i + b))}\)；
转换为拉格朗日的极小极大问题：\(\min_{w, b}\max_{\alpha}L(w, b, \alpha)\)，即先求拉格朗日的上界，再最小化上界；
可进一步转换为极大极小问题，即对偶问题：\(\max_{\alpha}\min_{w, b}L(w, b, \alpha)\)；
先求极小问题，对 \(w, b\) 求导，令导数为 0，求解 \(w = \sum_{i=1}^m{\alpha_iy_ix_i}, 0=\sum_{i=1}^m{\alpha_iy_i}\)；
代回拉格朗日函数，得对偶问题：\(\max_\alpha-{\frac{1}{2}\sum_{i=1}^m{\sum_{j=1}^m{\alpha_i\alpha_jy_iy_jx_i^Tx_j}} + \sum_{i=1}^m\alpha_i} \ \ s.t. \ \ \sum_{i=1}^m{\alpha_iy_i=0,\alpha_i \geq 0}\)；
求解问题，解出 \(\alpha\)，从而解得 \(w, b\)，\(\alpha_i > 0\) 对应的样本即为支持向量。
-
为什么要将求解 SVM 的原始问题转换为其对偶问题？
答：一是对偶问题往往更易求解。二是可以自然引入核函数，进而推广到非线性分类问题。
-
为什么 SVM 对缺失数据敏感？
答：缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对 SVM 的性能很重要。缺失特征数据将影响训练结果的好坏。
-
什么是几何间隔，什么是函数间隔？
答：几何间隔 \(y_i\frac{w^Tx_i+b}{\|w\|}\)，函数间隔 \(y_i(w^Tx_i+b)\)。函数间隔可以无限大，几何间隔不可以。
-
支持向量机的训练在本质上是在最优化哪个值？
答：w。w 得到 b 自然可以得到。
-
如何用支持向量机实现深度学习？
答：可以用支持向量机作为网络的最后一层，进行分类。
-
给一组数据，问决策树、LR、NB 以及 SVM 等算法学出来是什么样子的？
答：链接
-
什么是基于核的机器学习算法？
答：判别式模型需要把正负样本区分开，那势必会遇到区分不开的情形，这时要用到核函数，所以可认为判别式模型都要用核函数的。
-
SVM 有哪些核函数？
答：线性核和高斯核，即线性核与 RBF（径向基）核。 线性核：主要用于线性可分，参数少，速度快，对于一般数据，分类效果已经很理想了。 RBF 核：主要用于线性不可分，参数多，分类结果非常依赖于参数。 如果 Feature 数量跟样本数量差不多，应选用线性核的 SVM。 如果 Feature 数量比较小，样本数量一般，选用高斯核的 SVM。其他的核函数包括幂指数核、拉普拉斯核以及 Sigmoid 核等等。
-
高斯核为什么有效？
答：链接
-
支持向量机可以用来做回归吗？
答：支持向量机分类是使两类的点在各自的支持向量外，而支持向量机回归是把所有的点都看成一类，并要求在支持向量内。
-
SVM 和 softmax 的区别？
答：SVM 具有附加稳定性，当样例满足边界条件时，该样例不会影响损失函数；而 softmax 将考虑所有的样例。
-
感知机和 SVM 有什么区别？
答：链接
-
One-class SVM？
答：只要针对异常检测问题。
-
朴素贝叶斯为何如此朴素？
答：对条件概率分布作了条件独立性（conditional independence）的假设。
-
朴素贝叶斯中特征不小心重复会有影响吗？
答：会，破坏了原本的独立性假设。
-
用 numpy 实现 cross entropy loss
答：
import numpy as np def softmax(logits): """ 计算 softmax 概率，确保数值稳定。 logits: 形状为 (N, C)，N 是样本数，C 是类别数 """ shifted = logits - np.max(logits, axis=1, keepdims=True) exps = np.exp(shifted) return exps / np.sum(exps, axis=1, keepdims=True) def cross_entropy_loss(probs, labels): """ 计算平均交叉熵损失。 probs: softmax 后的概率，形状为 (N, C) labels: 每个样本的真实类别索引，形状为 (N,) """ N = probs.shape[0] # 取出每个样本对应真实类别的概率，防止 log(0) 加个小常数 log_likelihood = -np.log(probs[np.arange(N), labels] + 1e-15) return np.sum(log_likelihood) / N # 示例数据 logits = np.array([ [2.0, 1.0, 0.1], [0.5, 2.5, 0.3], [1.2, 0.7, 3.0] ]) labels = np.array([0, 1, 2]) # 每个样本的真实标签 # 计算 softmax 概率 probs = softmax(logits) # 计算交叉熵损失 loss = cross_entropy_loss(probs, labels) # 打印结果 print("Softmax probabilities:\n", probs) print("\nCross-entropy loss:", loss) -
You are given a data set on cancer detection. You’ve build a classification model and achieved an accuracy of 96%. Why shouldn’t you be happy with your model performance? What can you do about it?
Answer: If you have worked on enough data sets, you should deduce that cancer detection results in imbalanced data. In an imbalanced data set, accuracy should not be used as a measure of performance because 96% (as given) might only be predicting majority class correctly, but our class of interest is minority class (4%) which is the people who actually got diagnosed with cancer. Hence, in order to evaluate model performance, we should use Sensitivity (True Positive Rate), Specificity (True Negative Rate), F measure to determine class wise performance of the classifier. If the minority class performance is found to to be poor, we can undertake the following steps:
a. We can use undersampling, oversampling or SMOTE to make the data balanced.
b. We can alter the prediction threshold value by doing probability caliberation and finding a optimal threshold using AUC-ROC curve.
c. We can assign weight to classes such that the minority classes gets larger weight.
d. We can also use anomaly detection.
Know more: Imbalanced Classification
-
多分类问题如何转二分类方法？
答：a. 一对多法（one-versus-rest）。把某类样本归为一类，其他归为另一类，k 个类别的样本就构造出了 k 个 SVM；
b. 一对一法（one-versus-one）。在任意两类样本间设计一个 SVM，k 个类别需要 k(k - 1) / 2 个 SVM；
c. 层次支持向量机（H-SVMs）。先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环。
-
上溢（overflow）和下溢（underflow）是什么，softmax 函数会出现哪种情况，该怎么解决？
答：上溢即大量级的数被近似为正负无穷时，发生上溢。发生上溢后，这些数值会变为非数值。下溢即有些逼近零的数，如零除或者对零取对数时，得到负无穷，如果对负无穷进一步运算，则会得到非数字。softmax 函数中有指数运算，如果要运算的数过小或过大，则会下溢或上溢。解决上溢的方式是让每一个值都减去最大分量的值，由于这样做之后分母有一项为 1，所以不会出现下溢。同样对于取对数，可以让所有数都加 1。
Clustering
-
手撕 KMeans
答：``` import numpy as np
class KMeans: def init(self, n_clusters=3, max_iter=100, tol=1e-4, random_state=None): self.n_clusters = n_clusters self.max_iter = max_iter self.tol = tol self.random_state = random_state
def fit(self, X): np.random.seed(self.random_state) n_samples, _ = X.shape # Step 1: 初始化质心（随机选择 K 个样本） initial_idxs = np.random.choice(n_samples, self.n_clusters, replace=False) self.centroids = X[initial_idxs] for i in range(self.max_iter): # Step 2: 分配每个样本到最近的质心 distances = self._compute_distances(X) labels = np.argmin(distances, axis=1) # Step 3: 更新质心 new_centroids = np.array([ X[labels == j].mean(axis=0) if np.any(labels == j) else self.centroids[j] for j in range(self.n_clusters) ]) # Step 4: 判断收敛（质心移动小于 tol） shift = np.linalg.norm(new_centroids - self.centroids) self.centroids = new_centroids if shift < self.tol: break self.labels_ = labels # 保存训练标签 def predict(self, X): # 计算每个点到所有质心的距离，返回最近质心的索引 distances = self._compute_distances(X) return np.argmin(distances, axis=1) def _compute_distances(self, X): # 返回 (n_samples, n_clusters) 的距离矩阵 return np.linalg.norm(X[:, np.newaxis] - self.centroids, axis=2) ``` -
KMeans 中我想聚成 100 类 结果发现只能聚成98类，为什么？
答：因为聚类过程中可能会产生空簇，可见例子。
-
讲一下 EM 算法，E 步和 M 步的具体步骤，E 中的期望是什么？
答：初始化参数 \(\theta^{old}\)；E 步：估计 \(p(Z\|X, \theta^{old})\)，求得样本的后验期望值；M 步：根据极大似然估计求得 \(\theta^{new}\)；根据 \(\theta\)，迭代至收敛。
-
KMeans 和 EM 有什么关系，和 GMM 有什么关系？
答：KMeans 的目标函数（整个数据集点到各自聚类中心的距离的平方和）可以用 EM 算法求解。K-Means 算法归类为 GMM 的 EM 解法的一个特例。
Decision Tree
-
id3 是什么？
答：利用信息增益（大的特征优选）的决策多叉树。
-
c4.5 是什么？
答：信息增益容易倾向选择取值多的属性，所以 c4.5 是利用信息增益比（大的特征优选）的决策多叉树。
-
cart 是什么？
答：利用基尼系数（从数据集 D 中随机抽取两个样本，类别标志不一样概率，小的优选）的决策二叉树，可为回归树，也可为分类树。
-
决策树中的特征选择方法有哪些？
答：分类：信息增益、信息增益比和基尼系数；回归：误差（一般取叶子结点数值的方差和）。
Dimension Reducing
-
SVD 算法是什么？
答：\(A=U \sum V^T\)。把一个矩阵分解为正交矩阵 \(U\)（经过 \(A\) 变换后的新标准正交基），对角矩阵 \(\sum\) （\(V\) 中向量与 \(U\) 中对应向量之间的比例关系，\(\sum\) 中的每个 \(\sigma\) 会从大到小排序，值越大代表该维度重要性越高）和正交矩阵 \(V\)（原始域的标准正交基）。
-
PCA，SVD 和 LDA 有什么区别？
答：PCA 和 SVD 是无监督算法，不需要类别信息，他们都可以将数据投影到低维空间，以最大程度保留原始数据的方差信息。LDA 是有监督算法，需要类别信息，他在降维的同时让类间距离尽可能大，类内距离尽可能小。
Emsemble Learning
-
ensemble method 中哪种方法降低 bias，哪种方法降低 variance
答：bagging 降低 variance，boosting 既能降低 bias，又能降低 variance。
根据中心极限定理：样本平均值将会约等于其所在总体的平均值，取样次数越多，结果就越接近正态分布；而且样本大小越大，样本平均值分布的标准差就越小。
在 bagging 中，可以把建立每一个分类器的过程都看作给定数据集下的随机变量，把分类器的组合看作样本，很明显分类器越多，预测结果的 variance 就越小。
boosting 的每一轮迭代都是基于前面的残差，不断的去学习残差，从而使模型一步步去逼近真实值，整个过程都在优化 loss function，很明显随着迭代次数增加，预测结果的 bias 就越小。另外，boosting 也属于集成学习，是由若干个若分类器组成的一个强分类器，但由于各阶段分类器之间相关性较强，若把 boosting 也看成一次抽样，变量之间并不相互独立，也不是完全相关，存在一定的互相依赖关系，因此方差降低得较少。
-
集成方法的个体学习器有什么要求？
答：好而不同。
-
集成方法分为什么？有哪些方法？
答：个体学习器不存在强依赖关系，可同时生成，有 Bagging、Random Forest；个体学习器存在强依赖关系，须串行生成，有 Boosting，AdaBoost，GBDT。
-
强可学习和弱可学习是什么？
答：对于存在一个多项式的学习算法，若正确率很高，则是强可学习的，若仅比随机猜测略好，则是弱可学习的。
-
Bagging 的工作机制是什么？
答：利用自助采样法得到多套数据集，然后通过多个基分类器分类。
-
Boosting 的工作机制是什么？
答：通过基学习器的表现对训练样本分布进行调整，使得分错样本得到更多关注。
-
Random Forest 是什么？
答：随机森林是 Bagging 的变种，其以决策树为基学习器，并在决策树的训练过程中加入了随机属性选择。其可以处理离散特征，又可以处理连续特征。
-
随机森林相比普通的 bagging 的改进是什么？
答：不仅对样本随机选择，还对特征随机选择。
-
bagging 的自动校验是什么？
答：包外估计。
-
GBDT 相对于随机森林的改进是什么？
答：随机森林中每棵决策树是独立的，而在 GBDT 中，每棵树都是以前一棵树的残差（真实值跟预测值的差值，刚好是平方损失函数的负梯度）为学习目标去拟合。基于残差的 GBDT 对异常值敏感，可以用绝对损失或 huber 损失来代替平方损失函数。
-
随机森林和 GBDT 的联系和区别？
答：相同点：都是由多棵树组成；最终的结果都是由多棵树一起决定
不同点：组成随机森林的树可以分类树也可以是回归树，而 GBDT 只由回归树组成；组成随机森林的树可以并行生成，而 GBDT 是串行生成；随机森林的结果是多数表决表决的，而 GBDT 则是多棵树累加之和；随机森林对异常值不敏感，而 GBDT 对异常值比较敏感；随机森林是通过减少模型的方差来提高性能，而 GBDT 是减少模型的偏差来提高性能的；随机森林不需要进行数据预处理，即特征归一化。而 GBDT 则需要进行特征归一化
-
AdaBoost 是什么？
答：此方法通过提高前一轮弱分类器错误分类样本权值来提高集成学习效果，它在预测时采用加权多数表决的方法，即加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。
-
GBDT 和 XgBoost 区别？
答：XgBoost 将树模型的复杂度（叶节点的数量和叶节点的得分越高，树就越复杂）作为正则项加在优化目标上，公式推导中用到了二阶导数信息，支持并行操作。
-
提升树是什么？
答：如果用于分类，那就是特殊的 AdaBoost，基分类器都为决策树，回归则情况有所不同。
Deep Learning
-
强化学习和监督学习有什么区别？
答：监督学习中每一个决策（预测标签）是独立的，它对决策的优化取决于标签，强化学习每一个决策是相互影响的，它对决策的优化取决于延时标签（奖励）。
-
什么是白化？
答：输入数据分布变换到 0 均值，单位方差的正态分布
-
batch normalization
答：BatchNorm 就是在深度神经网络训练过程中使得每一层神经网络的输入保持相同分布的。
对于深度学习这种包含很多隐层的网络结构，在训练过程中，因为各层参数不停变化，所以每个隐层都面临 covariate shift 的问题，输入分布老是变来变去，这就是 Internal Covariate Shift，Internal 指的是深层网络隐层，发生在网络内部。BatchNorm 的基本思想是让每个隐层节点的激活输入分布固定下来，避免 Internal Covariate Shift 问题。
经过 BN 后，大部分 Activation 的值落入非线性函数的线性区内，对应导数远离导数饱和区，加速训练收敛过程。
BN 为了保证非线性的获得，对变换后的 x 又进行了 scale 加上 shift 操作：y = scale * x + shift)。
-
特征标准化有什么意义？怎么做？
答：消除不同指标量纲的影响。归一化，正态化。
-
初始化的方法
答：链接
-
sgd、momentum、rmsprop、adam 区别与联系
答：都是梯度下降，SGD 没动量，Momentum 是一阶动量，RMSProp 是二阶动量，Adam 是一阶动量 + 二阶动量。
-
一阶优化和二阶优化对应的矩阵？
一阶对应 Jacobian 矩阵，二阶对应 Hessian 矩阵。当矩阵正定（positive definite），梯度为 0 处为极小值。
-
深度学习为什么不用二阶优化？
答：有些方法可用，但总体不适用。原因：计算量大，训练慢；求导复杂；深度学习不需要高精度解；稳定性差。
-
TensorFlow 和 Pytorch 如何在不同层使用不同的学习率？
答：链接
-
TensorFlow 和 Pytorch 如何固定参数和 fine-tune？
答：链接
-
TensorFlow 怎么实现 learning rate decay？
答：链接
-
Pytorch 怎么实现 learning rate decay？
答：链接
-
TensorFlow 内部求导机制？
答：符号求导。先提供每一个op求导的数学实现，然后使用链式法则求出整个表达式的导数。
-
TensorFlow 创建变量的方式有哪些，有什么区别？
答：
tf.Variable()和tf.get_variable()。前者一律创建新的变量，遇到同名变量，会在后面加后缀 1，2；后者如果遇到同名变量，则使用之前创建的变量，但要求这个变量一定在 variable_scope 中，且有 reuse 选项。 -
Pytorch 如何切换训练和测试模式？
答：
model.train()和model.eval() -
GPU 利用率低怎么办？
答：dataset API 可以支持以 streaming 的方式读取数据。
-
softmax 求导？
The derivation of the softmax function?
答：链接。\(softmax'(z)=softmax(z)(y_i-softmax(z))\)，其中\(y_i\)为标签。如果表示为 Jacobian 矩阵可为\(J_{softmax}=Diag(p)-pp^T\)，其中\(p=softmax(z)\)，而\(Diag(p)\)是以p为对角线的矩阵。
-
为什么 softmax 包含 “soft”？
答：“soft”表示 softmax 函数是连续可导的，以保证梯度下降可以用来优化损失函数。
“soft” means that the softmax function is continuous and differentiable so that the gradient descent can be used to optimize the loss function.
-
怎么得到一个 soft 版本的 argmax？
答：用 softmax 的结果与 index 的倒置相乘。
-
argmax 不可导怎么办？
答：gumbel softmax。
-
神经网络为什么会产生梯度消失现象？
答：两种情况下梯度消失经常出现，一是在深层网络中，二是采用了不合适的损失函数，比如 sigmoid（导数范围从 0 到 0.25）。前者是因为根据链式法则，如果每一层神经元对上一层的输出的偏导乘上权重结果都小于 1 的话，多次链乘之后会接近为 0，如果都大于 0 的话，多次链乘之后会接近正无穷。sigmoid 中心部位和两侧的梯度差别太大，如果权重初始化得太大或太小，激活值基本都在 sigmoid 两侧，两侧梯度几乎为 0，传播几层就没有梯度了。
-
有哪些激活函数？
答：sigmoid，softmax，tanh，ReLU，PReLU，Leakly ReLU，Maxout。
-
挑一种激活函数推导梯度下降的过程?
答：链接
-
激活函数如何选择？
答：除了 gate 之类的地方，尽量不要用 sigmoid，可以用 tanh 或者 relu 之类的激活函数。
-
RELU 在 0 点的导数是多少？
答：链接
-
dying relu？
答：链接
-
如何调参？
答：for 循环；贝叶斯优化。
-
什么是 Jensen 不等式？
答：链接
-
互信息是什么？
答：\(I(X; Y) = \sum_{y \in Y}\sum_{x \in X} {p(x,y)log{\frac{p(x,y)}{p(x)p(y)}}}\)。当变量相互独立时，互信息为 0。
-
KL 散度和交叉熵的区别？
答：自信息（一个事件的信息量）：\(I(x)=-logP(x)\)；
信息熵（一个分布的信息量）：\(H(x)=E_{X \sim P}[I(x)]=-E_{X \sim P}[P(x)]\)；
交叉熵（在给定的真实分布下，使用非真实分布所指定的策略需要的代价）：\(-\sum_{k=1}^N{p_klog_2{q_k}}\)；
交叉熵越低，策略越好，当交叉熵 = 信息熵，表示使用了真实分布；
相对熵 / KL 散度（两个分布之间的差异）：\(KL(f(x) \| g(x))=\sum_{x \in X} {f(x) * log_2{\frac{f(x)}{g(x)}}}\)；
相对熵 = 交叉熵 - 信息熵。
-
如何避免梯度消失或梯度爆炸？
答：权重合理初始化，梯度剪切（梯度爆炸），门机制，batch normalization。
-
权重初始化方法？
答：零初始化，常量初始化，高斯/均匀随机初始化，Xavier 初始化，He 初始化，正交初始化。
-
为什么不能零初始化或常量初始化？
答：if the neurons start with the same weights, then all the neurons will follow the same gradient, and will always end up doing the same thing as one another.
-
Xavier / He 初始化的目的是什么？
答：使每一层输出方差为 1。
-
多任务如何学习？
答：链接
-
CNN 在卷积和池化过程中，输入特征和输出特征的关系是怎样的？
答：输出尺寸 = (输入尺寸 - filter + 2 * padding）/ stride + 1。计算尺寸不被整除，卷积向下取整，池化向上取整。
-
为什么在 CNN 等结构中将原先的 sigmoid、tanh 换成 ReLU 可以取得比较好的效果？
答：解决了梯度消失问题。
-
RNN 系列为什么要正交初始化？
答：RNN 的反向传播本质是权值矩阵连乘，如果矩阵所有特征值绝对值小于 1，则梯度消失，大于 1，则梯度爆炸。
-
怎么得到正交初始化？
答：QR 分解或 SVD。
-
RNN 中只能采用 tanh 而不是 ReLU 作为激活函数么？
答：ReLU 能解决梯度消失，但对 CNN 有效，对 RNN 无效。因为CNN 每一层使用独立的参数不同，原始的 RNN 在每个阶段都共享一个参数。如果直接把 RNN 的激活函数换成 ReLU 会导致非常大的输出值。
-
LSTM 是什么？
答：遗忘门：\(f_t=\sigma(W_f[h_{t-1}, x_t] + b_f)\)，输出 [0, 1]，来表示信息保留程度。
输入门：\(i_t=\sigma(W_i[h_{t-1}, x_t] + b_i)\)，输出 [0, 1]，来表示信息更新程度。
输入转换为初步输出：\(\tilde{C_t}=\sigma(W_C[h_{t-1}, x_t] + b_C)\)。
使用遗忘门和输入门：\(C_t=f_t*C_{t-1}+i_t*\tilde{C_t}\)。
输出门：\(o_t=\sigma(W_o[h_{t-1}, x_t] + b_o)\)，输出 [0, 1]，来表示信息输出程度。
得到最终输出：\(h_t=o_t*tanh(C_t)\)。
-
GRU 是什么？
答：LSTM 的变种，将遗忘门和输入门合在一起，输入门 = 1 - 遗忘门。
-
LSTM 和 GRU 的联系和区别？
答：都是通过使梯度的乘法变成加法，来解决 RNN 由于梯度消失而不能对长期依赖建模的问题。前者三个门，后者两个门，所以前者计算更耗时。
-
门机制为什么能解决梯度消失或爆炸问题？
答：链接
Natural Language Processing
Traditional Methods
-
TF-IDF 是什么？
答：词频（TF）为词在当前文档中出现的频率，逆向文件频率（IDF）由总文件数目除以包含该词的文件数目，再将得到的商取以 10 为底得到。
-
手动加权或自主学习权重哪个好？
答：手动加权相当于引入特征，更为合理，自主学习权重相当于学习特征，能够学到隐含信息。
-
自然语言处理数据增强的方法？
答：a、加噪，如随机扔词或调整语序；b、同义词替换；c、回译；d、文档裁剪；e、生成对抗网络。
-
HMM 的两个假设是什么？
答：齐次马尔可夫性假设（当前时刻状态只跟上一状态相关）和观测独立性假设（当前观测只跟当前状态相关）。
-
CRF 是什么？
答：给定一组输入随机变量，另一组输出随机变量的条件概率分布模型，输出随机变量构成马尔可夫随机场。
-
HMM 和 CRF 的联系与区别
答：a.HMM 是生成模型，CRF 是判别模型
b.HMM 是概率有向图，CRF 是概率无向图
c.HMM 求解过程可能是局部最优，CRF 可以全局最优
d.CRF 概率归一化较合理，HMM 则会导致 label bias 问题
Word2Vec + Neural Networks
-
为什么不能用 one-hot 表示词？
答：维度灾难和语义鸿沟。
-
分布式假设是什么
答：相同上下文语境的词有类似含义。
-
了解哪些词向量方法？
答：固定表征（word2vec，Glove，FastText）和动态表征（cove，elmo，GPT，bert）。
-
word2vec 的原理？
答：word2vec 有两种模型 CBOW 和 Skip-Gram，前者是在已知上下文的情况下，预测当前词，后者是在已知当前词的情况下，预测上下文。
-
word2vec 的两个模型哪个对小数据集和非词典词比较友好？
答：CBOW 每个词在进入模型后，都相当于进行了均值处理，所以非词典词在进行加权平均后，也容易被忽视。
Skip-Gram 每个词都会被单独得训练，较少受其他高频的干扰。所以对于 Skip-Gram 在小数据集和非词典词上占优。
-
word2vec 中的 hierarchical softmax 是什么？
答：将一次分类分解为多次分类，从而把分类的时间复杂度从 O(N) 降低到 O(logN)，从而提高运算效率。word2vec 根据词频构建了一棵 Huffman 树，来实现 hierarchical softmax。
-
word2vec 中的 negative sampling 是什么？
答：负采样即在词汇表中采样一定数目的词作为负例，与原先的正例一起做多次二分类，从而提高模型训练速度。负采样受到词频影响，词频越高的词越可能被采样到。
-
LSA 是什么？
答：潜在语义分析，先构建一个单词-标题（或文章）矩阵成，然后再用 SVD 算法等进行处理。
-
Glove 的原理？
答：通过构建词向量和共现矩阵之间的近似关系，来进行训练
-
Glove 和 LSA 有什么联系或区别？
答：LSA 采用计算复杂度高的 SVD 算法，Glove 可看作是对 LSA 的一种优化。
-
Glove 和 word2vec 有什么联系或区别？
答：word2vec 是局部语料库训练的，其特征提取是基于滑窗的；而 Glove 的滑窗是为了构建共现矩阵，是基于全局语料的，因此，word2vec 可以进行在线学习，glove 不能。word2vec 是无监督学习；Glove 通常被认为是无监督学习，但实际上 Glove还是有 label 的，即共现次数。word2vec 损失函数是带权重的交叉熵，权重固定；glove的损失函数是最小平方损失函数，权重可做映射变换。总体来看，Glove 可看作是换了目标函数和权重函数的全局 word2vec。
-
FastText 的原理？
答：FastText 建立在 word2vec 基础上，其用 subword 来对非词典词进行处理，用 n-gram 来考虑词序。
-
elmo 的原理？
答：基于语言模型的动态词向量。采用 1 层静态向量 + 2 层 LSTM 提取特征，然后将两个方向得到的向量进行拼接。
-
cove 和 elmo 的联系和区别
答：都用了 LSTM 编码，但前者的输入单位是词，后者是字符。
-
CNN 在文本分类上一般怎么应用？
答：卷积核宽度为词向量的维度（词向量交换维度并不会起影响，所以没必要在词向量维度做卷积），长度为关注窗口的大小，通道数可为所用词向量。
Attention + Transformers
-
Attention 机制的 soft 和 hard 是什么？
答：Hard-attention，就是 0/1 问题，哪些区域是被 attentioned，哪些区域不关注；Soft-attention，[0,1] 间连续分布问题，每个区域被关注的程度高低，用 0~1 的 score 表示。
-
multi-head attention 的公式是怎样的？
答：\(Attention(Q,K,V) = softmax({QK^T\over {\sqrt {d_k}}})V\)。
-
multi-head attention 实现
答：
import torch import torch.nn as nn import torch.nn.functional as F class MultiHeadAttention(nn.Module): def __init__(self, embed_dim, num_heads): super(MultiHeadAttention, self).__init__() assert embed_dim % num_heads == 0, "Embedding dimension must be divisible by number of heads" self.embed_dim = embed_dim self.num_heads = num_heads self.head_dim = embed_dim // num_heads # Linear layers to project input to Q, K, V self.q_proj = nn.Linear(embed_dim, embed_dim) self.k_proj = nn.Linear(embed_dim, embed_dim) self.v_proj = nn.Linear(embed_dim, embed_dim) # Final output projection self.out_proj = nn.Linear(embed_dim, embed_dim) def forward(self, x): B, T, E = x.size() # Linear projections Q = self.q_proj(x) # (B, T, E) K = self.k_proj(x) V = self.v_proj(x) # Split into multiple heads: (B, num_heads, T, head_dim) Q = Q.view(B, T, self.num_heads, self.head_dim).transpose(1, 2) K = K.view(B, T, self.num_heads, self.head_dim).transpose(1, 2) V = V.view(B, T, self.num_heads, self.head_dim).transpose(1, 2) # Scaled dot-product attention scores = torch.matmul(Q, K.transpose(-2, -1)) / (self.head_dim ** 0.5) # (B, num_heads, T, T) weights = F.softmax(scores, dim=-1) attended = torch.matmul(weights, V) # (B, num_heads, T, head_dim) # Concatenate heads: (B, T, E) attended = attended.transpose(1, 2).contiguous().view(B, T, E) # Final linear projection output = self.out_proj(attended) return output -
multi-head attention 时间复杂度
答：\(O(d * seq\_len * seq\_len)\)。
-
grouped-query attention 实现
答：grouped-query attention 中，query 使用比 key/value 更少的 heads
import torch import torch.nn as nn import torch.nn.functional as F class GroupedQueryAttention(nn.Module): def __init__(self, embed_dim, num_query_heads, num_kv_heads): super(GroupedQueryAttention, self).__init__() assert embed_dim % num_query_heads == 0, "embed_dim must be divisible by num_query_heads" assert embed_dim % num_kv_heads == 0, "embed_dim must be divisible by num_kv_heads" self.embed_dim = embed_dim self.num_query_heads = num_query_heads self.num_kv_heads = num_kv_heads self.q_head_dim = embed_dim // num_query_heads self.kv_head_dim = embed_dim // num_kv_heads # Projection layers self.q_proj = nn.Linear(embed_dim, embed_dim) self.k_proj = nn.Linear(embed_dim, embed_dim) self.v_proj = nn.Linear(embed_dim, embed_dim) self.out_proj = nn.Linear(embed_dim, embed_dim) def forward(self, x): B, T, E = x.shape # Project inputs Q = self.q_proj(x).view(B, T, self.num_query_heads, self.q_head_dim).transpose(1, 2) # (B, QH, T, Dq) K = self.k_proj(x).view(B, T, self.num_kv_heads, self.kv_head_dim).transpose(1, 2) # (B, KVH, T, Dk) V = self.v_proj(x).view(B, T, self.num_kv_heads, self.kv_head_dim).transpose(1, 2) # (B, KVH, T, Dv) # Expand K/V to match query heads if needed if self.num_query_heads != self.num_kv_heads: repeat_factor = self.num_query_heads // self.num_kv_heads K = K.repeat_interleave(repeat_factor, dim=1) # (B, QH, T, Dk) V = V.repeat_interleave(repeat_factor, dim=1) # (B, QH, T, Dv) # Scaled dot-product attention scores = torch.matmul(Q, K.transpose(-2, -1)) / (self.q_head_dim ** 0.5) # (B, QH, T, T) attn_weights = F.softmax(scores, dim=-1) context = torch.matmul(attn_weights, V) # (B, QH, T, Dv) # Combine heads context = context.transpose(1, 2).contiguous().view(B, T, E) # (B, T, E) output = self.out_proj(context) # Final linear projection return output -
multi-head attention + kv cache 实现
答：query 必须每步重算，而 key/value 是过去的记忆，可以缓存。
import torch import torch.nn as nn import torch.nn.functional as F class SelfAttentionWithKVCache(nn.Module): def __init__(self, embed_dim, num_heads, max_seq_len): super().__init__() assert embed_dim % num_heads == 0 self.embed_dim = embed_dim self.num_heads = num_heads self.head_dim = embed_dim // num_heads self.q_proj = nn.Linear(embed_dim, embed_dim) self.k_proj = nn.Linear(embed_dim, embed_dim) self.v_proj = nn.Linear(embed_dim, embed_dim) self.out_proj = nn.Linear(embed_dim, embed_dim) # 初始化 KV Cache（支持最多 max_seq_len 步） self.register_buffer("key_cache", torch.zeros(1, num_heads, max_seq_len, self.head_dim)) self.register_buffer("value_cache", torch.zeros(1, num_heads, max_seq_len, self.head_dim)) self.max_seq_len = max_seq_len def forward(self, x, start_pos): """ x: [B, 1, E] - 当前一步的 token 表示 start_pos: int - 当前 token 在生成序列中的位置 """ B, T, E = x.shape # T == 1 during generation # QKV projection Q = self.q_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2) # [B, H, 1, D] K = self.k_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2) V = self.v_proj(x).view(B, T, self.num_heads, self.head_dim).transpose(1, 2) # 更新 KV cache self.key_cache[:, :, start_pos:start_pos+1, :] = K self.value_cache[:, :, start_pos:start_pos+1, :] = V # 从 0 到当前 step，取所有 KV K_cached = self.key_cache[:, :, :start_pos+1, :] # [B, H, T_cache, D] V_cached = self.value_cache[:, :, :start_pos+1, :] # [B, H, T_cache, D] # 注意力计算 scores = torch.matmul(Q, K_cached.transpose(-2, -1)) / (self.head_dim ** 0.5) # [B, H, 1, T_cache] attn_weights = F.softmax(scores, dim=-1) out = torch.matmul(attn_weights, V_cached) # [B, H, 1, D] out = out.transpose(1, 2).contiguous().view(B, T, E) # [B, 1, E] return self.out_proj(out) -
Transformer 的原理？
答：Transformer 的总体架构是 encoder-decoder，它的主要部分是利用 multi-head attention 去计算词与词之间的相似度。此外，为了融入位置信息，它还提出了 position embedding。
-
Transformer 的 position encoding 为什么选三角函数？
答：偶数位置，使用正弦编码，在奇数位置，使用余弦编码。任意位置的 \(PE_{pos+k}\) 都可以被 \(PE_{pos}\) 的线性函数表示。在 bert 中，position encoding 是学习得到的。
-
Transformer 使用的时候，制约显存的最关键因素是什么？
答：序列长度。
-
为什么要 multi-head
答：多头注意力允许模型在不同的表示子空间中学习信息，这样可以让模型同时关注不同的信息维度。每个头学习到的信息可以独立地编码输入序列的不同方面，然后将这些信息综合起来，得到更丰富的表示。
-
Transformer 的 Q 和 K 为什么使用不同的权重矩阵生成？如果强行让 Q=K 会发生什么？
答：注意力将退化为自相似匹配，容易捕捉到 trivial 信息（如位置对称性）；表达能力显著下降，模型性能变差；实际论文实验证明，共用 Q/K/V 权重会损害性能
-
Transformer 为什么是 Q * K^T，而不是 Q + K？
答：点积是最自然的相似度度量，而加法并不能提供一个明确的匹配度分数，它只是两个向量的混合，没有“匹配程度”的含义。
-
为什么要除以 \(\sqrt {d_k}\)
答：可以防止内积过大导致softmax函数梯度变得非常小，这有助于数值稳定性，使得学习过程更加稳定。此外，它还可以看作是一种缩放因子，帮助模型在不同维度上保持一致的性能。
Large Language Models
-
GPT 的原理？
答：基于语言模型的动态词向量。采用单向的、多层的、并行能力强的 Transformer 提取特征，利用到的是 Transformer 的 decoder 部分，见到的都是不完整的句子。
-
bert 的原理？
答：基于语言模型的动态词向量。采用双向的、多层的、并行能力强的 Transformer 提取特征，利用到的是 Transformer 的 encoder 部分，采用了完整句子。
-
bert 的训练目标？
答：bert 有 masked language modeling 和 next sentence prediction 两个目标
-
roberta 相比 bert 做了哪些改进？
答：更大的训练数据；移除 Next Sentence Prediction（NSP）任务，发现没有它模型更稳定、更强；更长时间的训练；更大的 batch size 和学习率调度优化；BERT 的 masking 是静态的（数据预处理阶段决定），RoBERTa 每个 epoch 随机重新 mask。
-
bert 强于 rnn 的地方？
答：并行，对大数据比较友好。
-
Qwen
-
Deepseek
答：1. 采用 GRPO 算法，显著降低 RL 训练成本。
-
数据收集，数据质量控制，数据生成
-
Tokenizer
-
Position Embedding
答：Sinusoidal，Learnable Embedding, RoPE, AliBi
-
LLM 常用的激活函数有？
答：ReLU, GeLU, Swish
-
Batch Normalization (BN) vs Layer Normalization (LN) vs RMSNorm
答：BN 是跨样本统计的，会泄漏信息，所以 LN 更 make sense，RMSNorm 参数量（d，缩放因子）为 LN （2d，缩放因子和偏移因子） 一半，更高效和稳定，并表现与 LN 相似
-
实现 LayerNorm
答：
import torch import torch.nn as nn class LayerNorm(nn.Module): def __init__(self, dim, eps=1e-5): super(LayerNorm, self).__init__() self.eps = eps self.gamma = nn.Parameter(torch.ones(dim)) # 缩放因子 self.beta = nn.Parameter(torch.zeros(dim)) # 偏移因子 def forward(self, x): mean = x.mean(dim=-1, keepdim=True) var = x.var(dim=-1, unbiased=False, keepdim=True) x_norm = (x - mean) / torch.sqrt(var + self.eps) return self.gamma * x_norm + self.beta -
实现 RMSNorm
答：RMSNorm 不减去均值，只用输入的均方根（RMS）来进行归一化。它更轻量，计算更快，没有
mean操作。import torch import torch.nn as nn class RMSNorm(nn.Module): def __init__(self, dim, eps=1e-8): super(RMSNorm, self).__init__() self.eps = eps self.scale = nn.Parameter(torch.ones(dim)) # 可学习缩放因子 def forward(self, x): # 计算 RMS rms = x.pow(2).mean(dim=-1, keepdim=True).add(self.eps).sqrt() x_norm = x / rms return self.scale * x_norm -
Pre Norm 和 Post Norm 有什么区别？
答：Pre Norm 在子层（Self-Attn / FFN）之前，Post Norm 在子层（Self-Attn / FFN）之后。Pre Norm 更常用，因为其更稳定，更容易收敛。
-
为什么 LLM 流行 MoE？
答：MoE 能显著提高模型容量而不成比例地增加计算成本
-
SFT
-
RLHF (PPO, DPO, GRPO)
答：PPO
\[L^{\text{PPO}}(\theta) = \mathbb{E}_t \left[ \min \left( r_t(\theta) \hat{A}_t,\ \text{clip}(r_t(\theta),\ 1 - \epsilon,\ 1 + \epsilon) \hat{A}_t \right) \right]\]其中 \(r_t(\theta) = \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)}\)，\(\hat{A}_t\)是优势函数的估计，\(\epsilon\) 是控制策略变动幅度的裁剪阈值（如 0.2）。
PPO 流程如下：
-
生成多个回复样本
-
通过奖励模型计算 reward（通常是 sample-level 的一个标量）
-
用 value head 输出每个 token 的 V(s_t)
-
从 reward 回溯分配每个 token 的 TD 残差 \(\delta_t\)
-
用 GAE 计算每个 token 的优势 A_t
-
对策略（token logits）进行加权训练
DPO
\[L^{\text{DPO}}(\theta) = -\log \left( \frac{\exp\left( \beta \cdot \log \pi_\theta(y^+ \mid x) \right)}{\exp\left( \beta \cdot \log \pi_\theta(y^+ \mid x) \right) + \exp\left( \beta \cdot \log \pi_\theta(y^- \mid x) \right)} \right)\]其中，\(y^+\) 是人类偏好的回答，\(y^-\) 是较差的回答，\(\beta\) 是温度系数，控制偏好强度
GRPO
\[L^{\text{GRPO}}(\theta) = - \log \left( \frac{\exp\left(R_\theta(x, y^+)\right)}{\exp\left(R_\theta(x, y^+)\right) + \exp\left(R_\theta(x, y^-)\right)} \right)\]其中，$R_\theta$ 表示奖励形式的打分函数：
\[R_\theta(x, y) = \beta \cdot \left( \log \pi_\theta(y \mid x) - \log \pi_{\text{ref}}(y \mid x) \right)\]\(\pi_{\text{ref}}\) 是参考策略（例如预训练模型），用于提供稳定的对比基准。
PPO 是 token-level，DPO/GRPO 是 sample-level，但 GRPO 可以回传到 token-level
-
-
PPO 有了 reward model 为什么还要 critic/value model？
答：critic/value model 是内部奖励，会在 RL 过程中更新，reward model 是外部奖励，是训练好的
-
GRPO 怎么去掉 critic/value model 的？
答：采样多次，用 reward model 评价的平均值来充当 critic/value model
-
LoRA 的 A 和 B 矩阵用什么初始化方法？
答：A 用的是小的高斯随机初始化，B 用的是全 0 初始化，所以初始时 W = W’。
-
Base eval
答：MMLU（通用语言理解类），GSM8K（编程与数学能力）
-
Chat Eval
答：MT-Bench，AlpacaEval，Arena
-
Safety / Halluciation
-
Long Context
-
RAG; KG + LLM
-
Reasoning
-
MCP 和 function calling 有什么区别？
答：MCP 可以在一次回复中调用多个函数，function calling 每轮最多调用一个函数。
-
LLM 常用的优化器有？
答：AdamW，Lion
-
多卡多机训练
答：Data Parallel，Tensor Parallel，Pipeline Parallel，Expert Parallel
-
DataParallel（DP）和 DistributedDataParallel（DDP）区别
答：DP 单进程，多 GPU（主卡调度），主卡负责 forward/backward；DDP 多进程，每个 GPU 一个进程，每卡独立计算 + 自动同步梯度。
-
为什么 MoE 训练使用 Expert Parallelism 而不是 Tensor Parallelism
答：MoE 用 gating 网络在多个专家中选择最合适的几个来处理输入，因此 Expert Parallelism 不会损失 Data Parallelism 的数量，因为不同 Expert 处理不同的 Data
-
deepspeed 的 Zero-1， Zero 2， Zero 3
答：Zero-1 优化器状态拆分（例如 Adam 的动量），Zero-2 再加梯度拆分，Zero-3 参数也切分，每卡只保存部分权重。三个模式支持自动 Offload 到 CPU / NVMe，进一步节省显存
-
vllm
答：把 KV 缓存当作“虚拟内存”；每条序列的缓存按页（page）管理，动态分配到显存中；PagedAttention = 分页机制 + 注意力机制
Applications
-
浏览器的联想词运用了什么理论和原理？
答：贝叶斯原理。
CV and position related
Basic
-
Choose one paper
-
Choose one LLM
答：Qwen, LLaMA, GPT, deepseek; multilingual, coding, RAG
-
Choose one project
答：task description; solution; results; future work; challenges
Sentiment Analysis
-
情感分析相对于一般文本分类有什么不同？
答：特征方面（情感词典，融合了情感的词向量）。
-
怎么构建情感词典？
答：可以先人工制作一个小型的情感词典，然后利用语料，根据一些启发式规则（如“and”连接的词情感一样，“but”相反）来获得新的情感词，不断迭代扩展词典大小。
-
情感词典会有哪些问题？
答：不同的领域的情感词可能不一样；表达情感的词不一定是情感词；讽刺语境。
-
如何检测不文明词汇？
答：词典，分类问题。