2021年7月初，深圳TPlink圖像算法工程師面試題分享

問題1：介紹下K近鄰、kmeans聚類算法

K近鄰算法也稱為knn算法。
knn算法的核心思想是未標記樣本的類別，由距離其最近的k個鄰居投票來決定。
具體的，假設(shè)我們有一個已標記好的數(shù)據(jù)集。此時有一個未標記的數(shù)據(jù)樣本，我們的任務(wù)是預(yù)測出這個數(shù)據(jù)樣本所屬的類別。knn的原理是，計算待標記樣本和數(shù)據(jù)集中每個樣本的距離，取距離最近的k個樣本。待標記的樣本所屬類別就由這k個距離最近的樣本投票產(chǎn)生。

假設(shè)X_test為待標記的樣本，X_train為已標記的數(shù)據(jù)集，算法原理如下：
遍歷X_train中的所有樣本，計算每個樣本與X_test的距離，并把距離保存在Distance數(shù)組中。
對Distance數(shù)組進行排序，取距離最近的k個點，記為X_knn。
在X_knn中統(tǒng)計每個類別的個數(shù)，即class0在X_knn中有幾個樣本，class1在X_knn中有幾個樣本等。
待標記樣本的類別，就是在X_knn中樣本個數(shù)最多的那個類別。

算法優(yōu)缺點
優(yōu)點：準確性高，對異常值和噪聲有較高的容忍度。
缺點：計算量較大，對內(nèi)存的需求也較大。

算法參數(shù)
其算法參數(shù)是k，參數(shù)選擇需要根據(jù)數(shù)據(jù)來決定。
k值越大，模型的偏差越大，對噪聲數(shù)據(jù)越不敏感，當k值很大時，可能造成欠擬合；
k值越小，模型的方差就會越大，當k值太小，就會造成過擬合。

kmeans聚類算法
K-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。
假設(shè)要把樣本集分為k個類別，算法描述如下：
（1）適當選擇k個類的初始中心，最初一般為隨機選?。?/span>
（2）在每次迭代中，對任意一個樣本，分別求其到k個中心的歐式距離，將該樣本歸到距離最短的中心所在的類；
（3）利用均值方法更新該k個類的中心的值；
（4）對于所有的k個聚類中心，重復（2）（3），類的中心值的移動距離滿足一定條件時，則迭代結(jié)束，完成分類。
Kmeans聚類算法原理簡單，效果也依賴于k值和類中初始點的選擇。

問題2：介紹下隨機森林和SVM算法
隨機森林是一種基于bagging的分類算法，它通過自助法（bootstrap）重采樣技術(shù)，從原始訓練樣本集N中有放回地重復隨機抽取n個樣本生成新的訓練樣本集合訓練決策樹，然后按以上步驟生成m棵決策樹組成隨機森林，新數(shù)據(jù)的分類結(jié)果按分類樹投票多少形成的分數(shù)而定。

隨機森林大致過程如下：
1）從樣本集中有放回隨機采樣選出n個樣本；
2）從所有特征中隨機選擇k個特征，對選出的樣本利用這些特征建立決策樹（一般是CART，也可是別的或混合）；
3）重復以上兩步m次，即生成m棵決策樹，形成隨機森林；
4）對于新數(shù)據(jù)，經(jīng)過每棵樹決策，最后投票確認分到哪一類。

2.隨機森林特點：
隨機森林有很多優(yōu)點：
1） 每棵樹都選擇部分樣本及部分特征，一定程度避免過擬合；
2） 每棵樹隨機選擇樣本并隨機選擇特征，使得具有很好的抗噪能力，性能穩(wěn)定；
3） 能處理很高維度的數(shù)據(jù)，并且不用做特征選擇；
4） 適合并行計算；
5） 實現(xiàn)比較簡單；
缺點：
1） 參數(shù)較復雜；
2） 模型訓練和預(yù)測都比較慢。

SVM算法：
是一種二分類模型，它的基本模型是定義在特征空間上的間隔最大的線性分類器，間隔最大使它有別于感知機。

SVM可分為三種：
線性可分SVM
當訓練數(shù)據(jù)線性可分時，通過最大化硬間隔（hard margin）可以學習得到一個線性分類器，即硬間隔SVM。
線性SVM
當訓練數(shù)據(jù)不能線性可分但是近似線性可分時，通過最大化軟間隔（soft margin）也可以學習到一個線性分類器，即軟間隔SVM。
非線性SVM
當訓練數(shù)據(jù)線性不可分時，通過使用核技巧（kernel trick）和最大化軟間隔，可以學習到一個非線性SVM。

SVM的的學習策略就是間隔最大化，可形式化為一個求解凸二次規(guī)劃的問題，也等價于正則化的合頁損失函數(shù)的最小化問題。SVM的的學習算法就是求解凸二次規(guī)劃的最優(yōu)化算法。

問題3：Batch-norm作用和參數(shù)
batch norm的作用


1.batch norm對于輸入數(shù)據(jù)做了零均值化和方差歸一化過程，方便了下一層網(wǎng)絡(luò)的訓練過程，從而加速了網(wǎng)絡(luò)的學習。不同batch的數(shù)據(jù)，由于加入了batch norm，中間層的表現(xiàn)會更加穩(wěn)定，輸出值不會偏移太多。各層之間受之前層的影響降低，各層之間比較獨立，有助于加速網(wǎng)絡(luò)的學習。梯度爆炸和梯度消失現(xiàn)象也得到了一些緩解（我自己加上去的）。

2. batch norm利用的是mini-batch上的均值和方差來做的縮放，但是不同的mini-batch上面的數(shù)據(jù)是有波動的，相當于給整個模型引入了一些噪音，從而相當于有了一些正則化的效果，從而提升表現(xiàn)。

測試時的batch norm在訓練過程中，y，b參數(shù)和w相似，直接利用梯度值乘以學習率，更新值就好了。需要注意的是，batch norm中的z的均值和方差都是通過每一個mini-batch上的訓練數(shù)據(jù)得到的。在測試過程中，不能通過單獨樣本的數(shù)據(jù)計算均值和方差，我們可以通過讓訓練過程中的每一個mini-batch的均值和方差數(shù)據(jù)，計算指數(shù)加權(quán)平均，從而得到完整樣本的均值和方差的一個估計。在測試過程中，使用該值作為均值和方差，從而完成計算。

問題4：L1/L2的區(qū)別和作用

L1/L2的區(qū)別
L1是模型各個參數(shù)的絕對值之和。
L2是模型各個參數(shù)的平方和的開方值。
L1會趨向于產(chǎn)生少量的特征，而其他的特征都是0。
因為最優(yōu)的參數(shù)值很大概率出現(xiàn)在坐標軸上，這樣就會導致某一維的權(quán)重為0 ，產(chǎn)生稀疏權(quán)重矩陣
L2會選擇更多的特征，這些特征都會接近于0。
最優(yōu)的參數(shù)值很小概率出現(xiàn)在坐標軸上，因此每一維的參數(shù)都不會是0。當最小化||w||時，就會使每一項趨近于0。
L1的作用是為了矩陣稀疏化。假設(shè)的是模型的參數(shù)取值滿足拉普拉斯分布。
L2的作用是為了使模型更平滑，得到更好的泛化能力。假設(shè)的是參數(shù)是滿足高斯分布。


問題5：模型的加速與壓縮

深度學習模型壓縮與加速是指利用神經(jīng)網(wǎng)絡(luò)參數(shù)和結(jié)構(gòu)的冗余性精簡模型，在不影響任務(wù)完成度的情況下，得到參數(shù)量更少、結(jié)構(gòu)更精簡的模型。被壓縮后的模型對計算資源和內(nèi)存的需求更小，相比原始模型能滿足更廣泛的應(yīng)用需求。（事實上，壓縮和加速是有區(qū)別的，壓縮側(cè)重于減少網(wǎng)絡(luò)參數(shù)量，加速側(cè)重于降低計算復雜度、提升并行能力等，壓縮未必一定能加速）

主流的壓縮與加速技術(shù)有4種：結(jié)構(gòu)優(yōu)化、剪枝（Pruning）、量化（Quantization）、知識蒸餾（Knowledge Distillation）。

問題6：兩個鏈表存在交叉結(jié)點，怎么判斷交叉點
該題為leetcode160——相交鏈表
方法一：暴力解法
對于A中的每一個結(jié)點，我們都遍歷一次鏈表B查找是否存在重復結(jié)點，第一個查找到的即第一個公共結(jié)點。
時間復雜度：O(n^2)
空間復雜度：O(1)
無法通過，會超時。

方法二：
對暴力解法的一個優(yōu)化方案是：先將其中一個鏈表存到哈希表中，此時再遍歷另外一個鏈表查找重復結(jié)點只需 O(n) 時間。
代碼如下：
時間復雜度：O(n)
空間復雜度：O(n)

方法三：走過彼此的路
利用兩鏈表長度和相等的性質(zhì)來使得兩個遍歷指針同步。
具體做法是：讓兩指針同時開始遍歷，遍歷到結(jié)尾的時候，跳到對方的頭指針，如果有公共結(jié)點，則，會同時到達相遇的地方。
代碼如下：
時間復雜度：O(n)
空間復雜度：O(1)