原文作者：Jack Stark
在算法崗的面試中，除了資料結構和算法的程式設計題外，機器學習/深度學習的程式設計題也常常用來考察候選人的基礎能力。不能講了一大堆天花亂墜的算法，連個簡單的算法都不能獨立實作。
非極大值抑制(NMS)
NMS用來去掉重複的框。輸入前面得到的框，對于每一類，按照score進行降序排序，最大的那個一定保留，然後和其他的框計算IOU。IOU大于一定門檻值視為重複的框，丢棄掉。
import numpy as np
def nms(dets, thresh):
x1 = dets[:, 0] # bbox top_x
y1 = dets[:, 1] # bbox top_y
x2 = dets[:, 2] # bbox bottom_x
y2 = dets[:, 3] # bbox bottom_y
scores = dets[:, 4] # 分類score
areas = (x2 - x1 + 1) * (y2 - y1 + 1)
order = scores.argsort()[::-1] # 按score做降序排序
keep = []
while order.size > 0:
i = order[0]
keep.append(i)
xx1 = np.maximum(x1[i], x1[order[1:]])
yy1 = np.maximum(y1[i], y1[order[1:]])
xx2 = np.minimum(x2[i], x2[order[1:]])
yy2 = np.minimum(y2[i], y2[order[1:]])
w = np.maximum(0.0, xx2 - xx1 + 1)
h = np.maximum(0.0, yy2 - yy1 + 1)
interp = w * h
iou = interp / (areas[i] + areas[order[1:]] - interp)
inds = np.where(iou <= thresh)[0]
order = order[inds + 1] # 加1的原因。假設一個類别有n個框，這裡的索引是n-1個iou是對應的，
# 這裡要映射到原來長度為n的order，是以加1。
return keep Batch Normalization
訓練階段，求均值和方差時，在N、H、W上操作，而保留通道 C 的次元。具體來說，就是把第1個樣本的第1個通道，加上第2個樣本第1個通道 ...... 加上第 N 個樣本第1個通道，求平均，得到通道 1 的均值（注意是除以 N×H×W 而不是單純除以 N，最後得到的是一個代表這個 batch 第1個通道平均值的數字，而不是一個 H×W 的矩陣）。
import numpy as np
def batch_rorm(x, gamma, beta):
# x_shape:[N, C, H, W]
results = 0.
eps = 1e-5
x_mean = np.mean(x, axis=(0, 2, 3), keepdims=True)
x_var = np.var(x, axis=(0, 2, 3), keepdims=True)
x_normalized = (x - x_mean) / np.sqrt(x_var + eps)
results = gamma * x_normalized + beta
return results BN在測試階段使用的統計量不是在一個batch上計算的，而是整個資料集上的，可以用移動平均法求得。
Group Normalization
計算均值和标準差時，把每一個樣本 feature map 的 channel 分成 G 組，每組将有 C/G 個 channel，然後将這些 channel 中的元素求均值和标準差。各組 channel 用其對應的歸一化參數獨立地歸一化。多用于檢測分割等占用顯存較大的任務。
import numpy as np
def group_norm(x, gamma, beta, G=16):
# x_shape:[N, C, H, W]
results = 0.
eps = 1e-5
x = np.reshape(x, (x.shape[0], G, x.shape[1]//G, x.shape[2], x.shape[3]))
x_mean = np.mean(x, axis=(2, 3, 4), keepdims=True)
x_var = np.var(x, axis=(2, 3, 4), keepdims=True)
x_normalized = (x - x_mean) / np.sqrt(x_var + eps)
results = gamma * x_normalized + beta
results = np.reshape(results, (results.shape[0], results.shape[1]*results.shape[2], results.shape[3], results.shape[4]))
return results Kmeans聚類
下面是簡易版本的實作。
注意，np.random.randint()是取值範圍是左閉右開區間，python自帶的random.randint()是閉區間。
import numpy as np
import random
def kmeans(data, k):
m = len(data) # 樣本個數
n = len(data[0]) # 次元
cluster_center = np.zeros((k, n)) # k個聚類中心
# 選擇合适的初始聚類中心
# 在已有資料中随機選擇聚類中心
# 也可以直接用随機的聚類中心
init_list = np.random.randint(low=0, high=m, size=k) # [0, m)
for index, j in enumerate(init_list):
cluster_center[index] = data[j][:]
# 聚類
cluster = np.zeros(m, dtype=np.int) - 1 # 所有樣本尚未聚類
cc = np.zeros((k, n)) # 下一輪的聚類中心
c_number = np.zeros(k) # 每個簇樣本的數目
for times in range(1000):
for i in range(m):
c = nearst(data[i], cluster_center)
cluster[i] = c # 第i個樣本歸于第c簇
c_number[c] += 1
cc[c] += data[i]
for i in range(k):
cluster_center[i] = cc[i] / c_number[i]
cc.flat = 0
c_number.flat = 0
return cluster
def nearst(data, cluster_center):
nearst_center_index = 0
dis = np.sum((cluster_center[0] - data) ** 2)
for index, center in enumerate(cluster_center):
dis_temp = np.sum((center - data) ** 2)
if dis_temp < dis:
nearst_center_index = index
dis = dis_temp
return nearst_center_index
if __name__ == "__main__":
data = [[0,0], [1,0], [0,1], [100,100], [101,101], [102, 100], [-100,-100], [-101,-101], [-102, -100]]
data = np.array(data)
cluster = kmeans(data, 3)
print(cluster)
# [0 0 0 1 1 1 2 2 2] 每個樣本對應的類别，結果有随機性 softmax
import numpy as np
def convert_label_to_onehot(classes, labels):
"""
classes: 類别數
labels: array,shape=(N,)
"""
return np.eye(classes)[labels].T
def softmax(logits):
"""logits: array, shape=(N, C)"""
res = np.zeros_like(logits)
for i, row in enumerate(logits):
exp_sum = np.sum(np.exp(row))
for j, val in enumerate(row):
res[i,j] = np.exp(val)/ exp_sum
return res
if __name__ == '__main__':
# 有四個樣本，有三個類别
logits = np.array([[0, 0.45, 0.55],
[0.9, 0.05, 0.05],
[0.4, 0.6, 0],
[1, 0, 0]])
pred = np.argmax(softmax(logits), axis=1)
print(pred) softmax的上、下溢出問題
首先，什麼是上溢出和下溢出？實數在計算機内用二進制表示，不是一個精确值。
- 當數值過小的時候，被四舍五入為0，這就是下溢出。此時如果除以它就會出問題。(也有說法指超出所能表示的最小數字時是下溢出)。
- 當數值過大超出所能表示的最大正數時，就會發生上溢出。
如對于一個數組
求softmax，
，如果 某個
非常大，那麼
将會非常大，有可能上溢出；當所有
都非常小(絕對值很大的負數)，求指數之後會接近于0，就有可能下溢出。
有個方法可以同時解決上溢出和下溢出的問題：
求所有z中的最大值max_z，然後求
即可，這樣肯定不會有上溢出的風險，同時由于在分母上肯定有一個1，是以也不會有下溢出的風險。
PR曲線和ROC曲線的繪制
這兩種曲線是評價分類模型performance的常用方法。其中，PR圖的縱坐标是precision，橫坐标是recall；ROC曲線的縱坐标是True Positive Rate，橫坐标是False Positive Rate。它們的公式如下：
實作的代碼如下：
import numpy as np
import matplotlib.pyplot as plt
data_number = 50
labels = np.random.randint(0, 2, size=data_number) # 真實的類别
scores = np.random.choice(np.arange(0.1, 1, 0.01), data_number) # 模型判斷樣本為類别1的置信度
def pr_curve(y, pred):
pos = np.sum(y == 1)
neg = np.sum(y == 0)
pred_sort = np.sort(pred)[::-1]
index = np.argsort(pred)[::-1]
y_sort = y[index]
print(y_sort)
pre = []
rec = []
for i, item in enumerate(pred_sort):
if i == 0:
pre.append(1)
rec.append(0)
else:
pre.append(np.sum((y_sort[:i] == 1)) / i)
rec.append(np.sum((y_sort[:i] == 1)) / pos)
# 畫圖
plt.plot(rec, pre, 'k')
# plt.legend(loc='lower right')
plt.title('PR curve')
plt.plot([(0, 0), (1, 1)], 'r--')
plt.xlim([-0.01, 1.01])
plt.ylim([-0.01, 01.01])
plt.ylabel('precision')
plt.xlabel('recall')
plt.show()
def roc_curve(y, pred):
pos = np.sum(y == 1)
neg = np.sum(y == 0)
pred_sort = np.sort(pred)[::-1]
index = np.argsort(pred)[::-1]
y_sort = y[index]
print(y_sort)
tpr = []
fpr = []
thr = []
for i, item in enumerate(pred_sort):
tpr.append(np.sum((y_sort[:i] == 1)) / pos)
fpr.append(np.sum((y_sort[:i] == 0)) / neg)
thr.append(item)
# 畫圖
plt.plot(fpr, tpr, 'k')
plt.title('ROC curve')
plt.plot([(0, 0), (1, 1)], 'r--')
plt.xlim([-0.01, 1.01])
plt.ylim([-0.01, 01.01])
plt.ylabel('True Positive Rate')
plt.xlabel('False Positive Rate')
plt.show()
pr_curve(labels, scores)
roc_curve(labels, scores) ![16.開源項目--git将多個送出合并為一個送出[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)