-
Notifications
You must be signed in to change notification settings - Fork 24
/
metrics.py
376 lines (288 loc) · 11.7 KB
/
metrics.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
import torch
import torchaudio.functional as TAF
import numpy as np
from sklearn.cross_decomposition import CCA
try:
import pymp
pymp_available = True
except ImportError:
pymp_available = False
print("Please install the pymp library using `pip install pymp` to speed up non-batched metrics")
class AlignmentMetrics:
SUPPORTED_METRICS = [
"cycle_knn",
"mutual_knn",
"lcs_knn",
"cka",
"unbiased_cka",
"cknna",
"svcca",
"edit_distance_knn",
]
@staticmethod
def measure(metric, *args, **kwargs):
""" metric is a string for the function """
if metric not in AlignmentMetrics.SUPPORTED_METRICS:
raise ValueError(f"Unrecognized metric: {metric}")
return getattr(AlignmentMetrics, metric)(*args, **kwargs)
@staticmethod
def cycle_knn(feats_A, feats_B, topk):
"""
LLM nearest neighbors -> Query Language Pair -> LVM nearest neighbors
Args:
feats_A: A torch tensor of shape N x feat_dim
feats_B: A torch tensor of shape N x feat_dim
Returns:
acc: a float representing the accuracy
"""
knn_A = compute_nearest_neighbors(feats_A, topk)
knn_B = compute_nearest_neighbors(feats_B, topk)
return compute_knn_accuracy(knn_A[knn_B]).item()
@staticmethod
def mutual_knn(feats_A, feats_B, topk):
"""
Computes the mutual KNN accuracy.
Args:
feats_A: A torch tensor of shape N x feat_dim
feats_B: A torch tensor of shape N x feat_dim
Returns:
A float representing the mutual KNN accuracy
"""
knn_A = compute_nearest_neighbors(feats_A, topk)
knn_B = compute_nearest_neighbors(feats_B, topk)
n = knn_A.shape[0]
topk = knn_A.shape[1]
# Create a range tensor for indexing
range_tensor = torch.arange(n, device=knn_A.device).unsqueeze(1)
# Create binary masks for knn_A and knn_B
lvm_mask = torch.zeros(n, n, device=knn_A.device)
llm_mask = torch.zeros(n, n, device=knn_A.device)
lvm_mask[range_tensor, knn_A] = 1.0
llm_mask[range_tensor, knn_B] = 1.0
acc = (lvm_mask * llm_mask).sum(dim=1) / topk
return acc.mean().item()
@staticmethod
def lcs_knn(feats_A, feats_B, topk):
knn_A = compute_nearest_neighbors(feats_A, topk)
knn_B = compute_nearest_neighbors(feats_B, topk)
score = longest_ordinal_sequence(knn_A, knn_B).float().mean()
return score
@staticmethod
def cka(feats_A, feats_B, kernel_metric='ip', rbf_sigma=1.0, unbiased=False):
"""Computes the unbiased Centered Kernel Alignment (CKA) between features."""
if kernel_metric == 'ip':
# Compute kernel matrices for the linear case
K = torch.mm(feats_A, feats_A.T)
L = torch.mm(feats_B, feats_B.T)
elif kernel_metric == 'rbf':
# COMPUTES RBF KERNEL
K = torch.exp(-torch.cdist(feats_A, feats_A) ** 2 / (2 * rbf_sigma ** 2))
L = torch.exp(-torch.cdist(feats_B, feats_B) ** 2 / (2 * rbf_sigma ** 2))
else:
raise ValueError(f"Invalid kernel metric {kernel_metric}")
# Compute HSIC values
hsic_fn = hsic_unbiased if unbiased else hsic_biased
hsic_kk = hsic_fn(K, K)
hsic_ll = hsic_fn(L, L)
hsic_kl = hsic_fn(K, L)
# Compute CKA
#print('hsic', hsic_kl)
cka_value = hsic_kl / (torch.sqrt(hsic_kk * hsic_ll) + 1e-6)
return cka_value.item()
@staticmethod
def unbiased_cka(*args, **kwargs):
kwargs['unbiased'] = True
return AlignmentMetrics.cka(*args, **kwargs)
@staticmethod
def svcca(feats_A, feats_B, cca_dim=10):
# Center and scale the activations
def preprocess_activations(act):
act = act - torch.mean(act, axis=0)
act = act / (torch.std(act, axis=0) + 1e-8)
return act
feats_A = preprocess_activations(feats_A)
feats_B = preprocess_activations(feats_B)
# Compute SVD
U1, _, _ = torch.svd_lowrank(feats_A, q=cca_dim)
U2, _, _ = torch.svd_lowrank(feats_B, q=cca_dim)
U1 = U1.cpu().detach().numpy()
U2 = U2.cpu().detach().numpy()
# Compute CCA
cca = CCA(n_components=cca_dim)
cca.fit(U1, U2)
U1_c, U2_c = cca.transform(U1, U2)
# sometimes it goes to nan, this is just to avoid that
U1_c += 1e-10 * np.random.randn(*U1_c.shape)
U2_c += 1e-10 * np.random.randn(*U2_c.shape)
# Compute SVCCA similarity
svcca_similarity = np.mean(
[np.corrcoef(U1_c[:, i], U2_c[:, i])[0, 1] for i in range(cca_dim)]
)
return svcca_similarity
@staticmethod
def edit_distance_knn(feats_A, feats_B, topk):
"""
Computes the edit distance between the nearest neighbors of feats_A and feats_B.
"""
knn_A = compute_nearest_neighbors(feats_A, topk)
knn_B = compute_nearest_neighbors(feats_B, topk)
# given N x topk with integer entries, compute edit distance
n = knn_A.shape[0]
topk = knn_A.shape[1]
edit_distance = compute_distance(knn_A, knn_B, TAF.edit_distance)
return 1 - torch.mean(edit_distance) / topk
@staticmethod
def cknna(feats_A, feats_B, topk=None, distance_agnostic=False, unbiased=True):
""" similarity only cka variant """
n = feats_A.shape[0]
if topk < 2:
raise ValueError("CKNNA requires topk >= 2")
if topk is None:
topk = feats_A.shape[0] - 1
K = feats_A @ feats_A.T
L = feats_B @ feats_B.T
device = feats_A.device
def similarity(K, L, topk):
if unbiased:
K_hat = K.clone().fill_diagonal_(float("-inf"))
L_hat = L.clone().fill_diagonal_(float("-inf"))
else:
K_hat, L_hat = K, L
# get topk indices for each row
# if unbiased we cannot attend to the diagonal unless full topk
# else we can attend to the diagonal
_, topk_K_indices = torch.topk(K_hat, topk, dim=1)
_, topk_L_indices = torch.topk(L_hat, topk, dim=1)
# create masks for nearest neighbors
mask_K = torch.zeros(n, n, device=device).scatter_(1, topk_K_indices, 1)
mask_L = torch.zeros(n, n, device=device).scatter_(1, topk_L_indices, 1)
# intersection of nearest neighbors
mask = mask_K * mask_L
if distance_agnostic:
sim = mask * 1.0
else:
if unbiased:
sim = hsic_unbiased(mask * K, mask * L)
else:
sim = hsic_biased(mask * K, mask * L)
return sim
sim_kl = similarity(K, L, topk)
sim_kk = similarity(K, K, topk)
sim_ll = similarity(L, L, topk)
return sim_kl.item() / (torch.sqrt(sim_kk * sim_ll) + 1e-6).item()
def hsic_unbiased(K, L):
"""
Compute the unbiased Hilbert-Schmidt Independence Criterion (HSIC) as per Equation 5 in the paper.
> Reference: https://jmlr.csail.mit.edu/papers/volume13/song12a/song12a.pdf
"""
m = K.shape[0]
# Zero out the diagonal elements of K and L
K_tilde = K.clone().fill_diagonal_(0)
L_tilde = L.clone().fill_diagonal_(0)
# Compute HSIC using the formula in Equation 5
HSIC_value = (
(torch.sum(K_tilde * L_tilde.T))
+ (torch.sum(K_tilde) * torch.sum(L_tilde) / ((m - 1) * (m - 2)))
- (2 * torch.sum(torch.mm(K_tilde, L_tilde)) / (m - 2))
)
HSIC_value /= m * (m - 3)
return HSIC_value
def hsic_biased(K, L):
""" Compute the biased HSIC (the original CKA) """
H = torch.eye(K.shape[0], dtype=K.dtype, device=K.device) - 1 / K.shape[0]
return torch.trace(K @ H @ L @ H)
def compute_knn_accuracy(knn):
"""
Compute the accuracy of the nearest neighbors. Assumes index is the gt label.
Args:
knn: a torch tensor of shape N x topk
Returns:
acc: a float representing the accuracy
"""
n = knn.shape[0]
acc = knn == torch.arange(n, device=knn.device).view(-1, 1, 1)
acc = acc.float().view(n, -1).max(dim=1).values.mean()
return acc
def compute_nearest_neighbors(feats, topk=1):
"""
Compute the nearest neighbors of feats
Args:
feats: a torch tensor of shape N x D
topk: the number of nearest neighbors to return
Returns:
knn: a torch tensor of shape N x topk
"""
assert feats.ndim == 2, f"Expected feats to be 2D, got {feats.ndim}"
knn = (
(feats @ feats.T).fill_diagonal_(-1e8).argsort(dim=1, descending=True)[:, :topk]
)
return knn
def longest_ordinal_sequence(X, Y):
""" For each pair in X and Y, compute the length of the longest sub-sequence (LCS) """
def lcs_length(x, y):
"""
Compute the length of the longest common subsequence between two sequences.
This is a classic dynamic programming implementation.
"""
m, n = len(x), len(y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
lcs = compute_distance(X, Y, lcs_length)
return lcs
def compute_distance(X, Y, dist_fn):
""" compute distance in parallel"""
B, N = X.shape
distances = np.zeros(B)
X, Y = X.cpu().numpy(), Y.cpu().numpy()
if pymp_available:
with pymp.Parallel(4) as p:
for i in p.range(B):
distances[i] = dist_fn(X[i], Y[i])
else:
for i in range(B):
distances[i] = dist_fn(X[i], Y[i])
return torch.tensor(distances)
def remove_outliers(feats, q, exact=False, max_threshold=None):
if q == 1:
return feats
if exact:
# sorts the whole tensor and gets the q-th percentile
q_val = feats.view(-1).abs().sort().values[int(q * feats.numel())]
else:
# quantile for element in the tensor and take the average
q_val = torch.quantile(feats.abs().flatten(start_dim=1), q, dim=1).mean()
if max_threshold is not None:
max_threshold = max(max_threshold, q_val)
return feats.clamp(-q_val, q_val)
if __name__ == "__main__":
import torch.nn.functional as F
torch.manual_seed(0)
feats_A = torch.randn(64, 8192)
feats_B = torch.randn(64, 8192)
feats_A = F.normalize(feats_A, dim=-1)
feats_B = F.normalize(feats_B, dim=-1)
import time
trials = 10
t0 = time.time()
for metric in AlignmentMetrics.SUPPORTED_METRICS:
scores, times = [], []
for t in range(trials):
t_st = time.time()
kwargs = {}
if 'nn' in metric:
kwargs['topk'] = 10
if 'cca' in metric:
kwargs['cca_dim'] = 10
if 'kernel' in metric:
kwargs['dist'] = 'sample'
score = AlignmentMetrics.measure(metric, feats_A, feats_B, **kwargs)
scores.append(score)
times.append(time.time() - t_st)
print(f"{metric.rjust(20)}: {np.mean(scores):1.3f} [elapsed: {np.mean(times):.2f}s]")
print(f'Total time: {time.time() - t0:.2f}s')