{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"_kg_hide-input":true},"cell_type":"code","source":"# This Python 3 environment comes with many helpful analytics libraries installed\n# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python\n# For example, here's several helpful packages to load in \n\nimport numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n\n# Input data files are available in the \"../input/\" directory.\n# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory\n\nimport os\nprint(os.listdir(\"../input\"))\n!pip install lapjv\nfrom lapjv import lapjv\n# Any results you write to the current directory are saved as output.","execution_count":null,"outputs":[]},{"metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","collapsed":true,"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","trusted":false},"cell_type":"markdown","source":"# Introduction\n\n\nAt this point of the competition I think most of us have read [this great solution](https://www.kaggle.com/martinpiotte/whale-recognition-model-with-score-0-78563) by** @martinpiotte**. (If you haven't, you should). I've also ported it [here](https://www.kaggle.com/suicaokhoailang/martin-piotte-s-siamese-baseline), and it seems like using Martin's old model can achieve 0.822 LB as reported by [this kernel](https://www.kaggle.com/seesee/siamese-pretrained-0-822).\n\nI think the most interesting part of the solution is the traing data generator. As it was a siamese network, for each training step we have to chose a pair of images for comparison. The selection strategy, according to the authors:\n\n- Exactly 50% of the pairs are for matching whales, and 50% for different whales;\n- Each image from the training set is used exactly 4 times per epoch: A and B images of matching whales, A and B images of different whale pairs;\n- Pairs of images of different whales are selected to be difficult for the network to distinguish at a given stage of the training. This is inspired from adversarial training: find pairs of images that are from different whales, but that are still very similar from the model perspective.\n\nChoosing the matching pairs are easy, but how do we select the unmatched ones to maximize the model's robustness and prevent overfitting? That's when the linear assignment problem (LAP) comes into play."},{"metadata":{"_uuid":"9b1466a82100acebeaa6f5903ef5ac5fe9d80865"},"cell_type":"markdown","source":"# Linear Assigment Problem\n\nAn example of LAP that we are given n facilities and n locations and a $nxn$ matrix $C$ where $c_{ij}$ represents the cost of placing facility $i$ to location $j$. $C$ is the cost matrix, and the objective is to find an optimal assignment of facilities to locations such that the total placement cost is minimized.\n\n\nA naive algorithm will have an factorial time complexity while Hungarian algorithm can achieve $O(n^3)$. Here, we use the Jonker-Volgenant algorithm, also $O(n^3)$ but faster than the former in practice.\n\nIf we treat and the facilities and the locations as the whales, and the cost is the *dissimilarity* between them, **our problem become matching one whale to exactly one another so that the total dissimilarity of all the matches is minimized** (and the similarity is maximized) i.e we try to pick out a subset of our training data so that it *confuses* the model the most, becaus**e each image in each pair belong to a different whale, *yet* they look very similar according to the model's current parameters.**\n"},{"metadata":{"_uuid":"7ebc01b43cf15e05584c565366435508dcb395f2"},"cell_type":"markdown","source":"# How It Applies\n\n\nThere are a few tweaks. The cost matrix in our case is symmetrical and it looks like below. Here I assume 0 means totally similar and 1 for totally different. Matched pairs (the main diagonal) will have a score of 0. The scores may be the L2 distance of each image's output from a feature extractor model, or in case of Martin's solution it was a probability of 2 images belong to the same whale. \n"},{"metadata":{"_kg_hide-input":false,"trusted":true,"_uuid":"348a08a05cd5ecc3839def1e4912a55177419c0d"},"cell_type":"code","source":"import matplotlib.pyplot as plt\nimport matplotlib\ncost_mat = np.array([ \n   [0, 0.2, 0.3,0.1, 0.15], \n   [0, 0, 0.35,0.12, 0.37], \n   [0, 0, 0, 0.1, 0.15], \n   [0, 0, 0, 0, 0.08], \n   [0, 0, 0, 0, 0], \n ]) \n\ncost_mat += cost_mat.T\n\n\ndef draw_cost_mat(cost_mat, subplot=111):\n    plt.subplot(subplot)\n    size = cost_mat.shape[0]\n    x_start = 3.0 \n    x_end = 9.0 \n    y_start = 6.0 \n    y_end = 12.0 \n    extent = [x_start, x_end, y_start, y_end]\n    jump_x = (x_end - x_start) / (2.0 * size) \n    jump_y = (y_end - y_start) / (2.0 * size) \n    x_positions = np.linspace(start=x_start, stop=x_end, num=size, endpoint=False) \n    y_positions = np.linspace(start=y_start, stop=y_end, num=size, endpoint=False)  \n\n    plt.imshow(cost_mat, extent=extent)\n    plt.imshow(cost_mat, extent=extent)         \n    for y_index, y in enumerate(y_positions): \n         for x_index, x in enumerate(x_positions): \n            label = np.flip(cost_mat,1)[x_index, y_index] \n            text_x = x + jump_x \n            text_y = y + jump_y \n            plt.text(text_x, text_y, label, color='white', ha='center', va='center')\n\nmatplotlib.rcParams['figure.figsize'] = [15, 5]\n\ndraw_cost_mat(cost_mat,111)\n\nplt.show() ","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"7633564784af0cf681b988efde10ee180d8ee1d2"},"cell_type":"markdown","source":"Since we only care about finding unmatched pairs, we set the main diagonal's values to ∞ so that the algorithm won't ever pick them up.\n\nFor each epoch, lapjv will output a solution consists of n pairs of unmatched whales, when we're done with those pairs we set their similarity to ∞ and running the solver again for another epoch.\n\nEventually, the cost matrix will run out of finite values after a few epochs and we will need to reset it by running all training images through the feature extractor with the model's updated parameters."},{"metadata":{"trusted":true,"_uuid":"f403eb68f35d0a0ebfe94642f1a431de0e15c3f6"},"cell_type":"code","source":"# set the main diagonal to infinity\ncost_mat[np.arange(cost_mat.shape[0]), np.arange(cost_mat.shape[0])] = np.inf\n\ndraw_cost_mat(cost_mat, 121)\n\nsolved = cost_mat.copy()\n\n# Solving LAP\nx = lapjv(solved)[0]\ny = np.arange(len(x), dtype=np.int32)\n# Set the selected pairs scores to infinity\n#  the x,y pair will be used for training\nsolved[x,y] = np.inf\nsolved[y,x] = np.inf\n\ndraw_cost_mat(solved, 122)\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"ac1639577119c6f181695253627eefb1ce27b4ac"},"cell_type":"markdown","source":"# A Potential Bottleneck\n\nAs we keep training our model will get better and better at distinguishing pairs which were previously difficult. That will make all the costs in the cost matrix very close to 1 and to each other. As lapjv becomes horribly time consuming, I think it'll be better to switch to random matching at that point."}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}