Практически уроци

Как да векторизираме показателите за (не)сходство по двойки

Прост модел за векторизиране на показатели като разстояние L1 и пресичане над съюз за всички двойки точки.

Можете да векторизирате цял клас показатели за (не)сходство по двойки със същия модел в NumPy, PyTorch и TensorFlow. Това е важно, когато стъпка във вашия алгоритъм за наука за данни или машинно обучение изисква да изчислите тези показатели по двойки, защото вероятно не искате да губите време за изчисление със скъпи вложени цикли for.

Този модел работи всеки път, когато можете да разделите изчислението по двойки на две отделни стъпки: разширяване и намаляване. И работи еднакво добре за метрики на подобие като пресичане върху обединение между две кутии и метрики на различие като евклидово разстояние. Тази публикация обяснява модела и го конкретизира с два примера от реалния свят.

За краткост понякога наричам „прилика“ като стенограма както за прилика, така и за несходство. Също така понякога използвам „точка“, за да означава всеки елемент, който можем да използваме при сравнения по двойки. Например, в компютърното зрение кутия, кодирана като (x1, y1, x2, y2), може да се третира като точка в 4-измерното пространство.

Защо изчисляваме функции за подобие по двойки?

Има няколко алгоритми за наука за данни и машинно обучение, които изискват показатели за сходство по двойки като една от техните стъпки. Всъщност scikit-learn има цял „модул“, посветен на този тип операции.

Ето няколко примера, при които може да искате да изчислите показатели по двойки:

  • Сравняване на точки с центроиди. Както при групирането, така и при класификацията може да бъде полезно да се сравнят отделните точки със средните стойности на класа за набор от точки. Тези средни стойности на класа се наричат ​​центроиди и самите те са точки, което означава, че сравнението е операция по двойки.
  • Създаване на разходни матрици за двустранно присвояване. При „проследяване чрез откриване“ обикновено искате да присвоите нови откривания на съществуващи обекти по сходство. Унгарският алгоритъм може да създаде тези присвоявания чрез минимизиране на общите разходи, като същевременно изисква един обект да бъде присвоен на едно откриване (най-много) и обратно. Входът за този алгоритъм е матрица на разходите, където всеки елемент е разликата между обект и ново откриване. Примери за различие могат да бъдат евклидовото разстояние или обратното на пресичане над съюза.
  • Създаване на ядра за регресия на процеса на Гаус (GP). Несигурността в Гаусов процес се определя от функция, която параметризира ковариацията между произволни двойки точки. Правенето на изводи с GP изисква да изчислите матрица на двойната ковариация за вашия набор от данни. Най-често срещаната ковариационна функция е експоненциалната на квадрат.

Защо сходството по двойки е тясно място?

Под „по двойки“ имаме предвид, че трябва да изчислим сходството за всяка двойка точки. Това означава, че изчислението ще бъде O(M*N), където M е размерът на първия набор от точки, а N е размерът на втория набор от точки. Наивният начин за решаване на това е с вложен for-цикъл. Не прави това! Вложените for цикли са известни като бавни в Python.

Красотата на NumPy (и неговите братовчеди PyTorch и TensorFlow) е, че можете да използвате векторизация, за да изпращате for цикли към оптимизирани реализации на ниско ниво. Писането на бърз, научен код на Python до голяма степен е свързано с разбирането на API на тези пакети.

И така, как работи?

Обикновено, ако искате да векторизирате показател за сходство по двойки между набор от M D-измерни точки с форма (M, D) и набор от N D-измерни точки с форма (N, D), трябва да изпълните две стъпки:

  1. Разгъване. Използвайте елементна операция между две D-измерни точки с излъчване, за да създадете разширен масив с форма (M, N, D).
  2. Намаляване. Използвайте обобщена операция, за да намалите последното измерение, създавайки матрица с форма (M, N).

Това е доста просто. Има само няколко неща, които трябва да знаете:

  • Когато изчислявате сходство по двойки между матрица от точки и себе си, M ще бъде същото като N.
  • Понякога ще искате да приложите допълнителни изчисления по елементи и за вашия показател за сходство. Това може да се направи по всяко време, без да се провали резултатът.

Нека да разгледаме няколко примера, в които изчисляваме сходство по двойки между набори от точки и самите тях, за да направим процеса по-конкретен.

Разстояние Манхатън по двойки

Ще започнем с разстоянието Манхатън по двойки или нормата L1, защото е лесно. След това ще разгледаме по-интересна функция за подобие.

Разстоянието Манхатън между две точки е сумата от абсолютната стойност на разликите. Да кажем, че имаме два 4-измерни вектора NumPy, x и x_prime. Изчисляването на разстоянието Манхатън между тях е лесно:

import numpy as np
x = np.array([1, 2, 3, 4])
x_prime = np.array([2, 3, 4, 5])
np.abs(x - x_prime).sum()
# Expected result
# 4

Сега ще разширим разстоянието Манхатън до сравнение по двойки. Нека X са четирите ъгъла на единичен квадрат:

X = np.array([
    [0, 0],
    [0, 1],
    [1, 1],
    [1, 0]
])

Разстоянието Манхатън между всяка двойка от тези точки ще бъде 0 (ако са еднакви), 1 (ако споделят една страна) или 2 (ако не споделят една страна). Матрица на разлики по двойки, сравняваща набора от точки със себе си, ще има форма (4, 4). Всяка точка получава ред и всяка точка получава колона. Редът на редовете и колоните ще бъде същият, което означава, че трябва да получим 0s по диагонала, тъй като разстоянието Манхатън между точка и себе си е 0.

Нека изчислим по двойки разстоянието Манхатън между всяка от тези точки и самите тях по простия начин, с вложен for-цикъл:

manhattan = np.empty((4, 4))
for i, x in enumerate(X):
    for j, x_prime in enumerate(X):
        manhattan[i, j] = np.abs(x - x_prime).sum()
manhattan
# Expected result
# array([[0., 1., 2., 1.],
#        [1., 0., 1., 2.],
#        [2., 1., 0., 1.],
#        [1., 2., 1., 0.]])

Всеки елемент manhattan[i, j] сега е разстоянието Манхатън между точка X[i] и X[j]. Достатъчно лесно.

Сега нека го векторизираме. Първото нещо, от което се нуждаем, е операция за разширяване, която може да бъде излъчена върху двойки точки, за да създадем масив (4, 4, 2). Изваждането работи с излъчване, така че оттук трябва да започнем.

За да разширим правилно, трябва да вмъкнем измерения, така че операндите да имат форма съответно (4, 1, 2) и (1, 4, 2). Това работи, защото излъчването на NumPy прави стъпки назад през измеренията и разширява осите, когато е необходимо. Това ще доведе до масив от разстояние, който е (4, 4, 2):

deltas = X[:, None, :] - X[None, :, :]
deltas.shape
# Expected result
# (4, 4, 2)

Сега създадохме 4x4 набор от двуизмерни точки, наречени deltas. Начинът, по който работи този резултат, е, че deltas[i, j, k] е резултат от X[i, k] - X[j, k]. Би било еквивалентно на присвояване на deltas[i, j, :] = x - x_prime във вложения for цикъл по-горе.

На този етап ние сме свободни да приложим операцията за абсолютна стойност по елемент, тъй като тя не променя формата:

abs_deltas = np.abs(deltas)
abs_deltas.min()
# Expected result
# 0

Все още трябва да изпълним стъпката за намаляване, за да създадем (4, 4) L1 матрица на разстоянието. Можем да направим това, като сумираме по последната ос:

manhattan_distances = abs_deltas.sum(axis=-1)
manhattan_distances
# Expected result
# array([[0, 1, 2, 1],
#        [1, 0, 1, 2],
#        [2, 1, 0, 1],
#        [1, 2, 1, 0]])

Ето! Векторизирано разстояние по двойки Манхатън.

Между другото, когато операциите на NumPy приемат аргумент axis, това обикновено означава, че имате опцията да намалите едно или повече измерения. И така, за да преминем от (4, 4, 2) масив от делта към (4, 4) матрица с разстояния, ние сумираме по последната ос, като предаваме axis=-1 на метода sum(). -1 е съкращение за „последната ос“.

Нека опростим горните фрагменти до едноредов, който генерира разстояния на Манхатън по двойки между всички двойки точки на единичния квадрат:

np.abs(X[:, None, :] - X[None, :, :]).sum(axis=-1)
# Expected result
# array([[0, 1, 2, 1],
#        [1, 0, 1, 2],
#        [2, 1, 0, 1],
#        [1, 2, 1, 0]])

Пресичане по двойки над съюз

Сега, след като видяхте как да векторизирате показатели за сходство по двойки, нека да разгледаме един по-интересен пример. Пресичане над съединение (IoU) е мярка за степента, до която две кутии се припокриват. Да приемем, че имате две кутии, всяка параметризирана от горния ляв ъгъл (x1, y1) и долния десен ъгъл (x2, y2). IoU е площта на пресечната точка между двете кутии, разделена на площта на обединението между двете кутии.

Нека използваме кутии, генерирани от популярния модел YoloV3. Ще използваме относителни координати, така че максималната възможна стойност за която и да е от координатите е 1.0, а минималната е 0.0:

bicycle = np.array([0.129, 0.215, 0.767, 0.778])
truck = np.array([0.62 , 0.141, 0.891, 0.292])
dog = np.array([0.174, 0.372, 0.408, 0.941])

Площта на клетка (x1, y1, x2, y2) е (x2 - x1) * (y2 - y1). Така че, ако имате две кутии a и b, можете да изчислите IoU, като създадете пресечна кутия (когато съществува) и след това изчислите площта на пресечната точка и площта на всяка от отделните кутии. След като имате това, IoU е intersection / (a_area + b_area - intersection). Резултатът ще бъде 0, ако полетата не се припокриват (тъй като полето за пресичане не съществува) и 1, когато полетата имат перфектно припокриване.

Ето кода за изчисляване на IoU за двойката велосипед-куче и двойката куче-камион:

def iou(a, b):
    """
    Intersection over Union for two boxes a, b
    parameterized as x1, y1, x2, y2.
    """
    # Define the inner box
    x1 = max(a[0], b[0])
    y1 = max(a[1], b[1])
    x2 = min(a[2], b[2])
    y2 = min(a[3], b[3])
    # Area of a, b separately
    a_area = (a[2] - a[0]) * (a[3] - a[1])
    b_area = (b[2] - b[0]) * (b[3] - b[1])
    total_area = a_area + b_area
    # Area of inner box
    intersection = max(0, x2 - x1) * max(y2 - y1, 0)
    # Area of union
    union = total_area - intersection
    return intersection / union
iou(bicycle, dog), iou(dog, truck)
# Expected result
# (0.2391024221313951, 0.0)

За да векторизираме IoU, трябва да векторизираме пресечната точка и общата площ отделно. След това можем да изчислим IoU като елементна операция между двата мат

Първо подредете трите кутии, за да създадете (3, 4) матрица:

X = np.stack([
    dog,
    bicycle,
    truck
])
X.shape
# Expected result
# (3, 4)

Операцията np.stack() поставя множество масиви NumPy заедно чрез добавяне на ново измерение. По подразбиране добавя измерение в началото.

След това изчислете координатите на пресечните кутии за всички двойки кутии:

x1 = np.maximum(X[:, None, 0], X[None, :, 0])
y1 = np.maximum(X[:, None, 1], X[None, :, 1])
x2 = np.minimum(X[:, None, 2], X[None, :, 2])
y2 = np.minimum(X[:, None, 3], X[None, :, 3])
inner_box = np.stack([x1, y1, x2, y2], -1)
inner_box.shape
# Expected result
# (3, 3, 4)

Това е стъпката на разширяване за пресичане. Не можем да го направим в една стъпка, защото вътрешната кутия е максимумът между съответните координати и минимумът между другите. Но ние подреждаме резултата, за да стане ясно, че тази стъпка наистина разширява резултата до (3, 3, 4) масив. Всеки елемент inner_box[i, j, k] е kта координата на пресечната точка между поле i и поле j.

Сега изчислете площта на вътрешната кутия:

intersection = (
    np.maximum(inner_box[..., 2] - inner_box[..., 0], 0) *
    np.maximum(inner_box[..., 3] - inner_box[..., 1], 0)
)
intersection.shape
# Expected result
# (3, 3)

Операцията с площ намалява последното измерение. Правим това намаление ръчно, като избираме индекси, но все още намаляваме това измерение, точно както направихме с sum(axis=-1) по-горе.

Трябва да направим друга операция по двойки, за да получим обща площ между двойки кутии, но тази е малко по-различна. За обща площ „точките“ вече не са кутии, те са площи. Тоест, вместо да правим изчисление по двойки между два (3, 4) набора кутии, ще направим операция по двойки между два набора области. Въпреки че разтягаме термина „точка“, моделът е същият като в предишните примери.

Първо изчисляваме площта на всяка отделна кутия, за да създадем нашите вектори на площта, след което изчисляваме общата площ със стъпка на разширяване:

a_area = (X[:, 2] - X[:, 0]) * (X[:, 3] - X[:, 1])
b_area = (X[:, 2] - X[:, 0]) * (X[:, 3] - X[:, 1])
total_area = a_area[:, None] + b_area[None, :]
total_area.shape
# Expected result
# (3, 3)

Мислете за total_area като с форма (3, 3, 1), където всеки елемент total_area[i, j, 0] съдържа сумата от площите между чифт кутии. NumPy автоматично притиска последното измерение, така че действителният резултат е (3, 3) и не е необходимо изрично да изпълняваме стъпката за намаляване.

Останалата част от изчислението на IoU е по елементи между матриците intersection и total_area. Това е аналогично на случая с единична кутия по-горе:

union = total_area - intersection
intersection / union
# Expected result
# array([[1.        , 0.23910242, 0.        ],
#        [0.23910242, 1.        , 0.02911295],
#        [0.        , 0.02911295, 1.        ]])

Забележете, всичките диагонални елементи са 1 (перфектен IoU), а елементите, които не се припокриват, са 0.

Заключение

Това е! В тази публикация говорихме за това какво е сходство по двойки и някои случаи на употреба, когато това е важно. Говорихме и за това защо това може да бъде толкова трудно място за вашите алгоритми за машинно обучение. След това видяхме общ подход за векторизиране на тези изчисления за подобие по двойки: 1) разширяване и 2) намаляване. Ако можете да разделите изчислението по двойки на тези две стъпки, можете да го векторизирате. И вие сте свободни да добавяте всякакви допълнителни операции по елемент, от които може да се нуждаете. Всички примери в тази публикация използват NumPy, но не забравяйте, че можете да използвате този трик и в PyTorch и TensorFlow.

Приятно програмиране!