{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"2022-01-26-deepwalk.ipynb","provenance":[{"file_id":"https://github.com/recohut/nbs/blob/main/raw/T384270%20%7C%20DeepWalk%20in%20python.ipynb","timestamp":1644674259116}],"collapsed_sections":[],"toc_visible":true,"authorship_tag":"ABX9TyOzNKbYgMjjVsOkMk1OZIyv"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","metadata":{"id":"l5uXqP2G7ov1"},"source":["# DeepWalk in python"]},{"cell_type":"markdown","metadata":{"id":"_Ue1g8397t0o"},"source":["## Imports"]},{"cell_type":"code","metadata":{"id":"V_CAT4tG7om_"},"source":["import random\n","import networkx as nx \n","from gensim.models import Word2Vec\n","\n","import numpy as np\n","from abc import ABC\n","import pandas as pd"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"_GAkUKgmTkZR"},"source":["## Deepwalk"]},{"cell_type":"code","metadata":{"id":"6DW32rssTing"},"source":["class DeepWalk:\n","  \"\"\"\n","  Implement DeepWalk algorithm.\n","  reference paper : DeepWalk: Online Learning of Social Representations\n","  link : https://arxiv.org/abs/1403.6652\n","  Using the algorithm can get graph embedding model with your network data.\n","  \"\"\"\n","  def __init__(self, G=None, adjlist_path=None, edgelist_path=None):\n","    \"\"\"\n","    Parameters\n","    G : networkx : networkx graph.\n","    \n","    adjlist_path : network file path. \n","    \"\"\"\n","    if G == adjlist_path == edgelist_path == None:\n","      raise ValueError('all parameter is None, please check your input.')\n","      \n","    try:\n","      \n","      if G != None:\n","        self.G = G\n","      elif adjlist_path != None:\n","        self.G = nx.read_adjlist(adjlist_path)\n","      elif edgelist_path != None:\n","        self.G = nx.read_edgelist(edgelist_path)\n","\n","    except Exception as e:\n","      print(e)\n","\n","\n","  def random_walk(self, iterations, start_node=None, random_walk_times=5):\n","    \"\"\"\n","    : Implement of random walk algorithm :\n","    Parameters\n","    ----------------------------------------\n","    iterations : int : random walk number of iteration \n","    start_node : str : choose start node (random choose a node, if start_node is None)\n","    random_walk_times : int : random walk times.\n","    ----------------------------------------\n","    Returns\n","    walk_records : list of walks record\n","    \"\"\"\n","    walk_records = []\n","\n","    for i in range(iterations):\n","      \n","      if start_node is None:\n","        s_node = random.choice(list(self.G.nodes()))\n","        walk_path = [s_node]\n","      else:\n","        walk_path = [start_node]\n","        \n","      current_node = s_node\n","      while(len(walk_path) < random_walk_times):\n","        neighbors = list(self.G.neighbors(current_node))\n","        \n","        \n","        current_node = random.choice(neighbors)\n","        walk_path.append(current_node)\n","          \n","      walk_records.append(walk_path)\n","    \n","    return walk_records\n","\n","  def buildWord2Vec(self, **kwargs):\n","    \"\"\"\n","    \n","    Using gensim to build word2vec model\n","    Parameters\n","    ----------------------------------------\n","    **kwargs\n","    \n","    walk_path : list : random walk results\n","    size : int : specific embedding dimension, default : 100 dim\n","    window : int : specific learn context window size, default : 5\n","    workers : int : specific workers. default : 2\n","    ----------------------------------------\n","    Returns\n","    walk_records : list of walks record\n","    \"\"\"\n","    \n","    walk_path = kwargs.get('walk_path', None)\n","    if walk_path is None:\n","      return \n","    \n","    size = kwargs.get('size', 100)\n","    window = kwargs.get('window', 5)\n","    workers = kwargs.get('workers', 2)\n","\n","    embedding_model = Word2Vec(walk_path, size=size, window=window, min_count=0, workers=workers, sg=1, hs=1)\n","\n","    return embedding_model"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"B7Kv5bfhaIsh"},"source":["## Hierarchical Softmax\n","First, we'll build the components required to use hierarchical softmax. From the paper:\n","\n","Computing the partition function (normalization factor) is expensive. If we assign the vertices to the leaves of a binary tree, the prediction problem turns into maximizing the probability of a specific path in the tree\n","\n","Thus, instead of having a classifier that predicts probabilities for each word from our vocabulary (besides the one we're currently iterating on), we can structure the loss function as a binary tree where every internal node contains its own binary classifier. Computing the loss (and gradient) can therefore be done in $O(logv)$ predictions rather than $O(v)$ (as is the case with $v$ labels), where $v$ is the number of vertices in our graph."]},{"cell_type":"code","metadata":{"id":"OPTTtTT9aIpg"},"source":["class Tree(ABC): \n","    @staticmethod\n","    def merge(dims, lr, batch_size, left=None, right=None):\n","        if left is not None: left.set_left()\n","        if right is not None: right.set_right()\n","        return InternalNode(dims, lr, batch_size, left, right)\n","    \n","    @staticmethod\n","    def build_tree(nodes, dims, lr, batch_size):\n","        if len(nodes) % 2 != 0: nodes.append(None)\n","        while len(nodes) > 1:\n","            nodes = [Tree.merge(dims, lr, batch_size, nodes[i], nodes[i+1]) for i in range(0, len(nodes) - 1, 2)]\n","        return nodes[0]\n","        \n","    def set_parent(self, t):\n","        self.parent = t\n","        \n","    def set_left(self): self.is_right = False\n","        \n","    def set_right(self): self.is_right = True"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Ivhz8tvMaWZg"},"source":["class InternalNode(Tree):\n","    def __init__(self, dims, lr, batch_size, left=None, right=None, parent=None, is_right=None):\n","        self.dims = dims\n","        self.set_left_child(left)\n","        self.set_right_child(right)\n","        self.set_parent(parent)\n","        self.is_right = is_right\n","        self.params = np.random.uniform(size=self.dims) \n","        self.gradients = []\n","        self.lr = lr\n","        self.batch_size= batch_size\n","        \n","    def set_left_child(self, child: Tree):\n","        self.left = child\n","        if self.left is not None:\n","            self.left.set_parent(self)\n","            self.left.set_left()\n","            \n","    def set_right_child(self, child: Tree):\n","        self.right = child\n","        if self.right is not None:\n","            self.right.set_parent(self)\n","            self.right.set_right()\n","            \n","    def set_parent(self, parent: Tree):\n","        self.parent = parent    \n","        \n","    def predict(self, embedding, right=True):\n","        d = self.params.dot(embedding) if right else -self.params.dot(embedding)\n","        return 1/(1+np.exp(-d))\n","    \n","    def update_gradients(self, gradient: np.array):\n","        self.gradients.append(gradient)\n","        if len(self.gradients) >= self.batch_size:\n","            avg_gradient = np.stack(self.gradients, axis=0).mean(axis=0)\n","            self.params = self.params - self.lr * avg_gradient\n","            self.gradients = []\n","        \n","    def __eq__(self, other):\n","        return (\n","            self.dims == other.dims and\n","            self.left == other.left and\n","            self.right == other.right and\n","            self.lr == other.lr and\n","            self.batch_size == other.batch_size\n","        )"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"s4cUO_97aZgW"},"source":["class Leaf(Tree):\n","    def __init__(self, vertex, parent: InternalNode = None, is_right = False):\n","        self.parent = parent\n","        self.is_right = is_right \n","        self.vertex = vertex\n","        \n","    def update(self, anchor_vertex):\n","        node = self\n","        gradients = []\n","        total_cost = 0.\n","        emb_grads = []\n","        while node.parent is not None:\n","            is_right = node.is_right\n","            node = node.parent        \n","            prob = node.predict(anchor_vertex.embedding, is_right)\n","            log_prob = np.log(prob)\n","            total_cost -= log_prob\n","            u = 1 - prob\n","            node.update_gradients(u*anchor_vertex.embedding)\n","            emb_grads.append(u*node.params)\n","        anchor_vertex.update_embedding(sum(emb_grads))\n","        return total_cost"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"mE_0ks6PabTD"},"source":["class Vertex(object):\n","    def __init__(self, dim, lr, batch_size):\n","        self.dim = dim\n","        self.embedding = np.random.uniform(size=dim)\n","        self.lr = lr\n","        self.gradients = []\n","        self.batch_size = batch_size\n","        \n","    def update_embedding(self, gradient: np.array): \n","        self.gradients.append(gradient)\n","        if len(self.gradients) >= self.batch_size:\n","            avg_gradient = np.stack(self.gradients, axis=0).mean(axis=0)\n","            self.embedding = self.embedding - self.lr * avg_gradient\n","            self.gradients = []"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Ux9slFZ-adiw"},"source":["v = Vertex(8, 1e-1, 1)\n","v2 = Vertex(8, 1e-1, 1)\n","leaf = Leaf(v)\n","leaf2 = Leaf(v2)\n","i = InternalNode(8, 1e-1, 1, leaf, leaf2)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"3dp2DCMgai2j","executionInfo":{"status":"ok","timestamp":1633185052067,"user_tz":-330,"elapsed":6,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"41d60917-dfc5-4dc2-a955-d6a34fdadf7a"},"source":["before = leaf2.vertex.embedding\n","before_parent = leaf.parent.params\n","print(before)"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[0.70466282 0.4704185  0.15045063 0.93010221 0.04333254 0.33917607\n"," 0.3072665  0.97709016]\n"]}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"6nTMuDVBajHJ","executionInfo":{"status":"ok","timestamp":1633185058468,"user_tz":-330,"elapsed":703,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"9b3e5a23-41f5-4d17-eb78-946212109211"},"source":["leaf.update(leaf2.vertex)\n","after = leaf2.vertex.embedding\n","after_parent = leaf.parent.params\n","print(after)"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[0.70405907 0.45365486 0.08264726 0.91088379 0.01787853 0.27183648\n"," 0.26271421 0.96241706]\n"]}]},{"cell_type":"markdown","metadata":{"id":"fSmBZypRakhm"},"source":["Leaves 1 and 2 should share parent i. Also, each should have its own vertex (v and v2 respectively)."]},{"cell_type":"code","metadata":{"id":"_pY0JOE_amtM"},"source":["assert leaf.vertex == v\n","assert leaf.vertex != v2\n","assert leaf2.vertex == v2\n","assert leaf2.vertex != v\n","assert leaf.parent == i\n","assert leaf2.parent == i"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"NRvDC5rnanwm"},"source":["As a convenience method, we have Tree.merge which should do the same thing as the manual passing to the InternalNode constructor above."]},{"cell_type":"code","metadata":{"id":"fb6NsUPlapka"},"source":["i2 = Tree.merge(8, 1e-1, 1, leaf, leaf2)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"2w1yuw3Waqpr"},"source":["assert i2 == i"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"dYGVHNvYar0D"},"source":["We should be able to create an internal node with a single child."]},{"cell_type":"code","metadata":{"id":"yiveInG5atPm"},"source":["i3 = InternalNode(8, 0.01, 1, leaf)\n","assert i3.left == leaf\n","assert i3.right is None"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"6lz38Mizaumb"},"source":["We should be able to combine two internal nodes under a third internal node."]},{"cell_type":"code","metadata":{"id":"tN4e7CGDawIn"},"source":["two_internal_nodes = Tree.merge(8, 0.01, 1, i, i2)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"iJpxRbHlaxsA"},"source":["assert two_internal_nodes.left == i\n","assert two_internal_nodes.right == i2\n","assert i.parent == two_internal_nodes\n","assert i2.parent == two_internal_nodes"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"fxkGgObGazPL"},"source":["p = Tree.merge(8, 1e-1, 1, leaf, leaf2)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"C6A0p1Mra0jv","executionInfo":{"status":"ok","timestamp":1633185128668,"user_tz":-330,"elapsed":532,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"4d798539-0996-47cd-ee4a-5170709eb09b"},"source":["leaf.parent == leaf2.parent"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{},"execution_count":16}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"hlHh21ooa1u-","executionInfo":{"status":"ok","timestamp":1633185133919,"user_tz":-330,"elapsed":716,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"2a7ca9bc-41dd-4291-8ac0-6e8e7424c848"},"source":["leaf.vertex.embedding"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([0.14202065, 0.94789345, 0.96777175, 0.12845376, 0.33301731,\n","       0.25128948, 0.98405048, 0.66509886])"]},"metadata":{},"execution_count":17}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"Y948sZOYa27u","executionInfo":{"status":"ok","timestamp":1633185139193,"user_tz":-330,"elapsed":424,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"9a5e0306-365f-43f2-b244-8636e2448fc8"},"source":["before = leaf2.vertex.embedding.copy()\n","before_parent = leaf.parent.params.copy()\n","leaf.update(leaf2.vertex)\n","after = leaf2.vertex.embedding\n","after_parent = leaf.parent.params\n","(before, after)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(array([0.70405907, 0.45365486, 0.08264726, 0.91088379, 0.01787853,\n","        0.27183648, 0.26271421, 0.96241706]),\n"," array([ 0.66127081,  0.45437708,  0.00473115,  0.84110065, -0.02988149,\n","         0.22792929,  0.2618126 ,  0.92318361]))"]},"metadata":{},"execution_count":18}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"V7o7Ugtwa4VA","executionInfo":{"status":"ok","timestamp":1633185146746,"user_tz":-330,"elapsed":515,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"48cc8c72-7984-431b-a5a1-b9b080f5c973"},"source":["(before_parent, after_parent)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(array([0.55046806, 0.03145724, 0.89740018, 0.87697905, 0.54720746,\n","        0.52541901, 0.03329589, 0.53246957]),\n"," array([ 0.48884187, -0.00825111,  0.89016608,  0.79724952,  0.54564255,\n","         0.5016252 ,  0.01030055,  0.44822934]))"]},"metadata":{},"execution_count":19}]},{"cell_type":"code","metadata":{"id":"kaZ9yTnba6I1"},"source":["assert leaf.parent.predict(leaf2.vertex.embedding, right=False) + leaf.parent.predict(leaf2.vertex.embedding)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"rZQVRYJNa7Qg","executionInfo":{"status":"ok","timestamp":1633185158126,"user_tz":-330,"elapsed":425,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"27781dd6-6951-4189-a1f2-e9acfcca76a5"},"source":["leaf.parent.predict(leaf2.vertex.embedding)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["0.8188850193603718"]},"metadata":{},"execution_count":21}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"zwNqR-Cpa88M","executionInfo":{"status":"ok","timestamp":1633185166246,"user_tz":-330,"elapsed":619,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"a4519140-c8c3-465a-c6c5-7ef3db21c18c"},"source":["new_leaf = Leaf(Vertex(8, 0.01, 1))\n","new_leaf2 = Leaf(Vertex(8, 0.01, 1))\n","merged = Tree.merge(8, 0.01, 1, new_leaf, new_leaf2)\n","before1 = new_leaf2.vertex.embedding.copy()\n","new_leaf.update(new_leaf2.vertex)\n","after1 = new_leaf2.vertex.embedding\n","(before1, after1)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(array([0.93594794, 0.00617317, 0.83736121, 0.53829744, 0.86273901,\n","        0.25883039, 0.64857575, 0.48665158]),\n"," array([ 0.92966094, -0.00183856,  0.83637281,  0.52932184,  0.85800988,\n","         0.25527446,  0.64106637,  0.47856129]))"]},"metadata":{},"execution_count":22}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"aQNA3TD1a-2D","executionInfo":{"status":"ok","timestamp":1633185172323,"user_tz":-330,"elapsed":645,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"9a767b11-b153-49ba-8ede-c2cba83097a5"},"source":["before2 = new_leaf.vertex.embedding.copy()\n","new_leaf2.update(new_leaf.vertex)\n","after2 = new_leaf.vertex.embedding\n","(before2, after2)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(array([0.01577104, 0.73203528, 0.51886159, 0.03187183, 0.52233666,\n","        0.12200931, 0.67895869, 0.06495115]),\n"," array([0.01467268, 0.73063752, 0.51869031, 0.03030379, 0.52151184,\n","        0.12138838, 0.67764856, 0.06353787]))"]},"metadata":{},"execution_count":23}]},{"cell_type":"code","metadata":{"id":"Jmyp5cHvbAYP"},"source":["emb_length = 10\n","lr = 1e-3\n","bs = 100\n","v1 = Vertex(emb_length, lr, bs)\n","v2 = Vertex(emb_length, lr, bs)\n","v3 = Vertex(emb_length, lr, bs)\n","random_walk = [v1, v2, v3]\n","leaves = list(map(lambda x: Leaf(x), random_walk))\n","tree = Tree.build_tree(leaves, emb_length, lr, bs)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"0fQmteX6bFb_","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1633185240163,"user_tz":-330,"elapsed":662,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"e3d0d2a7-05e8-4ab8-8c76-705d4a89b127"},"source":["leaves"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[<__main__.Leaf at 0x7fc68b836d50>,\n"," <__main__.Leaf at 0x7fc68b836a90>,\n"," <__main__.Leaf at 0x7fc68b836250>,\n"," None]"]},"metadata":{},"execution_count":25}]},{"cell_type":"code","metadata":{"id":"8ZjzHNozbFcA","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1633185241985,"user_tz":-330,"elapsed":10,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"15d2626b-42e2-4e7d-9c0c-2b197b5f5478"},"source":["tree.__class__"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["__main__.InternalNode"]},"metadata":{},"execution_count":26}]},{"cell_type":"code","metadata":{"id":"f36Fs_C1bFcC","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1633185242731,"user_tz":-330,"elapsed":9,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"fafb1c70-5d61-469d-f9bd-38d87564e6d7"},"source":["v1.embedding.shape, v2.embedding.shape, v3.embedding.shape"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["((10,), (10,), (10,))"]},"metadata":{},"execution_count":27}]},{"cell_type":"code","metadata":{"id":"MRKD0Yf3bFcD"},"source":["leaf1, leaf2, leaf3, empty_leaf = leaves"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"jKiUuANrbFcD","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1633185244387,"user_tz":-330,"elapsed":15,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"b44b881b-9cf7-4b8a-ff19-e633950f81b4"},"source":["leaf3.vertex.embedding"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["array([0.56054777, 0.8018071 , 0.99571521, 0.35924211, 0.63936966,\n","       0.31256406, 0.49017507, 0.63942332, 0.55382691, 0.59270016])"]},"metadata":{},"execution_count":29}]},{"cell_type":"code","metadata":{"id":"OHqy3C6TbFcD","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1633185244842,"user_tz":-330,"elapsed":30,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"a531b6ba-2394-43f4-cb71-6be33db1b548"},"source":["leaf1.parent, leaf2.parent, leaf3.parent"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(<__main__.InternalNode at 0x7fc68b836610>,\n"," <__main__.InternalNode at 0x7fc68b836610>,\n"," <__main__.InternalNode at 0x7fc68b8360d0>)"]},"metadata":{},"execution_count":30}]},{"cell_type":"markdown","metadata":{"id":"zXoHf1r47yvC"},"source":["## Plots"]},{"cell_type":"code","metadata":{"id":"JpFNd3dSbFcE","colab":{"base_uri":"https://localhost:8080/","height":282},"executionInfo":{"status":"ok","timestamp":1633185246043,"user_tz":-330,"elapsed":1223,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"b39addd4-15e2-42ca-9aaf-99e1b4799ee2"},"source":["costs1 = []\n","costs3 = []\n","combined_cost = []\n","for i in range(10000):\n","    cost1 = leaf1.update(leaf2.vertex)\n","    cost3 = leaf3.update(leaf2.vertex)\n","    if i % bs == 0:\n","        costs1.append(cost1) \n","        costs3.append(cost3)\n","        combined_cost.append(cost1+cost3) \n","    \n","pd.Series(costs1).plot(kind='line')"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["<matplotlib.axes._subplots.AxesSubplot at 0x7fc68b78efd0>"]},"metadata":{},"execution_count":31},{"output_type":"display_data","data":{"image/png":"iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3dd3xUVf7/8dcnCST0GooEDU0EBEEivQlSFBZQVHAtoCCy0hRdV3fXddX97epaKCKsiAUbdWkiokgPkTKRXqRLEU3o0ovn98cM+42YmAkkucnk/Xw85pGZWzKf+7j65ubcc88x5xwiIhK6wrwuQEREspaCXkQkxCnoRURCnIJeRCTEKehFREJchNcFpKZ06dIuNjbW6zJERHKNxMTEA8656NTW5cigj42NxefzeV2GiEiuYWbfpbVOTTciIiFOQS8iEuIU9CIiIU5BLyIS4hT0IiIhTkEvIhLiFPQiIiEupIL+jXlbWb/vqNdliIjkKCET9EdOnuWTFbvpNjqBSb49XpcjIpJjhEzQFy+Yn1kDm1H/mhI8NWUtz0xdx5nzF7wuS0TEcyET9AClCkfywUMN+EOrKoxfsZu7//M1+46c8rosERFPhVTQA0SEh/GnDtfx1v312ZF8gk4jlrBka7LXZYmIeCaooDezXWa2zsxWm9mvRhszs3vNbG1gmwQzuyHYfbNK+1rlmDGgKWWKRPHAuysYOX8rP/+s+XFFJO/JyBX9zc65us65uFTW7QRaOudqAy8CYzKwb5apHF2Yaf2b0PmGq3j1yy30+cDH0ZPnsrMEERHPZUrTjXMuwTl3OPBxGRCTGb83MxTMH8Gw7nV5oUstlmxNptPIJeqCKSJ5SrBB74AvzSzRzPqms21v4POM7mtmfc3MZ2a+5OTMbVM3Mx5oHMvERxpz/oLjjtEJTFy5O1O/Q0QkpzLn0m+3NrMKzrl9ZlYGmAsMdM4tTmW7m4FRQDPn3MGM7JtSXFycy6qJRw4eP8PgCauJ33aAu+NieKHL9UTlC8+S7xIRyS5mlphW83hQV/TOuX2Bn0nANKBBKl9SBxgLdLkY8sHum51KFY5k3EMNGNi6KpN8e7ljVAK7D570siQRkSyVbtCbWSEzK3LxPdAOWH/JNlcDU4H7nXNbMrKvF8LDjCfaVefdXnHsO3KKjm8sYe7GH70uS0QkSwRzRV8WiDezNcAK4DPn3Bwz62dm/QLb/A0oBYy6pBtlqvtm8jFcttbXlWXWwGZcU6ogD3/g46XPN3P+ws9elyUikqmCaqPPblnZRp+a0+cu8MKsjXyyfDcNKpVk5D31KFM0Ktu+X0TkSl1xG32oi8oXzj9vr83rd9/A2r1HuG1EPF9vP5j+jiIiuYCCPoU7boxhRv9mFC0Qwb1jlzFq4TY9TSsiuZ6C/hLVyxVh5oBm3Fa7PP+e8y0Pf+DjyMmzXpclInLZFPSpKBwZwRv31OOFLrVYvDWZjiPiWbPniNdliYhcFgV9Gi4+TTu5XxMA7vxPAuMSdpETb16LiPwWBX066lYszmeDmtG8WjTPzdzAwPGrOH7mvNdliYgETUEfhOIF8zP2gTie6lCd2ev20/mNeDbtP+Z1WSIiQVHQBykszHi0VVXGP9yI42fO0/XNpUxcuVtNOSKS4ynoM6hh5VLMHtycm2JL8qf/ruOJyWs4eVZNOSKScynoL0PpwMBoj91SjWmr9tFl5FK2/viT12WJiKRKQX+ZwsOMx265lo96N+TwybN0HrmU/ybu9bosEZFfUdBfoaZVS/PZoObUiSnGE5PX8NSUNZw6e8HrskRE/kdBnwnKFo3i4z4NGXBzVSYn7qXrm0vZlnTc67JERAAFfaaJCA/jyfbVef/BBiQfP0PnkfFM/UZNOSLiPQV9Jmt5bTSzBzXn+grFGDJpDX+crKYcEfGWgj4LlCsWxSd9GjKwdVWmfLOXLm/Gq1eOiHhGQZ9FIsLDeKJddT54qAEHj/t75Uz27fG6LBHJgxT0Wax5tWg+H9ycGyoW449T1jJk0mpOaKwcEclGQQW9me0ys3WXzAebcr2Z2Qgz22Zma83sxhTreprZ1sCrZ2YWn1uUKRrFx30aMbiN/wGrziPj2fyDxsoRkeyRkSv6m51zddOYk/BWoFrg1RcYDWBmJYHngIZAA+A5MytxZSXnTuFhxuNtr+Xj3g05dvo8XUYu5ZPlGitHRLJeZjXddAE+cH7LgOJmVh5oD8x1zh1yzh0G5gIdMuk7c6UmVUsze1BzGlQqyZ+nrWPg+FX8dPqc12WJSAgLNugd8KWZJZpZ31TWVwBS3mncG1iW1vI8LbpIJOMebMAf21fn8/U/0HFEPGv3agYrEckawQZ9M+fcjfibaPqbWYvMLsTM+pqZz8x8ycnJmf3rc5ywMKP/zVWZ2LcR5y/8TLfRCbwTv1NNOSKS6YIKeufcvsDPJGAa/vb2lPYBFVN8jgksS2t5at8xxjkX55yLi46ODq76EBAXW5LZg5vT8toyvDhrI33G+Th8QpORi0jmSTfozayQmRW5+B5oB6y/ZLOZwAOB3jeNgKPOuf3AF0A7MysRuAnbLrBMUiheMD9vP1Cf535XkyVbD3Dr8CUs33HQ67JEJEQEc0VfFog3szXACuAz59wcM+tnZv0C28wGdgDbgLeBRwGcc4eAF4GVgdcLgWVyCTPjwaaVmPpoE6LyhXHP28sY/tVWLvysphwRuTKWE9uE4+LinM/3q+76ecbxM+f567R1TF/9PY0ql2RY93qUKxbldVkikoOZWWIa3d/1ZGxOVDgygqHd6/LKnXVYs+cotw5fzLxNP3pdlojkUgr6HMrMuCuuIrMGNaN8sQL0Hufj+U83cOa8RsIUkYxR0OdwVaILM/XRJvRqEst7S3dxx6gEdiRrUhMRCZ6CPheIyhfO3zvXYuwDcXx/5BSd3ohnSuJe9bkXkaAo6HORW2qW5fPBLahdoRhPTl7DYxNXa/gEEUmXgj6XKVcsik8ebsSQttfy6Zrv6TgintV7NHyCiKRNQZ8LhYcZg9pUY9Ijjbnws+PO0QmMXridn9XnXkRSoaDPxeJiSzJ7UHPa1yrHy3M288C7K0g6dtrrskQkh1HQ53LFCuZj5O/r8dIdtfF9d4gOw5eoz72I/IKCPgSYGT0aXM2sgc0oVzSK3uN8/H3mBk6fU597EVHQh5SqZYowrX8THmpaifcTdtH1zaVs+fEnr8sSEY8p6ENMZEQ4f/tdTd578CYOHD/D796I58Ovd6nPvUgepqAPUTdXL8Png1vQqHIpnp2xgYc/8HHw+BmvyxIRDyjoQ1h0kUje63UTf+tUk8VbDtBh+BKWbA392btE5JcU9CEuLMx4qFklpvdvSvEC+bj/nRX8Y9ZGDY4mkoco6POImlcVZeaAZtzX6GrGxu/k9jcT2JakG7UieYGCPg8pkD+cf3StzdgH4vjh2Gk6jojnw2Xf6UatSIhT0OdBt9Qsy5zBzWlQqSTPTl+vG7UiIU5Bn0eVKRrFuAcb8GzgRm37YUtY+G2S12WJSBYIOujNLNzMVpnZrFTWDTWz1YHXFjM7kmLdhRTrZmZW4XLlwsKM3s0qMWNAU0oVyk+v91bqiVqREBSRgW0HA5uAopeucM49fvG9mQ0E6qVYfco5V/eyK5QsV6N8UWYMaMpLn2/m/YRdJGw/wPAe9ahR/lenWkRyoaCu6M0sBugIjA1i83uA8VdSlGS/i7NYjXuoAYdPnqPLyKWMXbJDQx+LhIBgm26GAU8BP//WRmZ2DVAJmJ9icZSZ+cxsmZl1/Y19+wa28yUn66Eer7S8Npo5g5vTsno0//hsE/e/u5z9R095XZaIXIF0g97MOgFJzrnEIH5fD2CKcy5lI+81zrk44PfAMDOrktqOzrkxzrk451xcdHR0MLVLFilVOJIx99fnpTtq8813R+gwbAmfrd3vdVkicpmCuaJvCnQ2s13ABKC1mX2UxrY9uKTZxjm3L/BzB7CQX7bfSw51cejj2YObE1u6EP0/+YYhkzRHrUhulG7QO+eecc7FOOdi8Qf5fOfcfZduZ2bXASWAr1MsK2FmkYH3pfH/o7Exk2qXbFCpdCGm9GvMoDbVmL5qH7cOX8KKnYe8LktEMuCy+9Gb2Qtm1jnFoh7ABPfLxyxrAD4zWwMsAF5yzinoc5l84WEMaXstk/s1IcyM7mO+5uU5mzl7/jdv2YhIDmE58fH3uLg45/P5vC5DUnH8zHle/HQjE317qHVVUYZ1r0u1skW8LkskzzOzxMD90F/Rk7GSIYUjI3j5zjq8dX999h89Tac34nlv6U51wxTJwRT0clna1yrHF4+1oGnV0jz/6UZ6vreCH46e9rosEUmFgl4uW3SRSN7pGcc/b6+Nb9dh2g9bzMw133tdlohcQkEvV8TM+H1DfzfMytGFGDR+FQPHr+LIybNelyYiAQp6yRSVShdi8iONeaLttXy+bj/thy3WtIUiOYSCXjJNRHgYA9tUY9qjTSkcGcH976zguRnrOXVWo2GKeElBL5mudkwxPhvUnAebxjLu6+/oOGIJq/ccSX9HEckSCnrJElH5wnnud7X4uE9DTp+7QLfRCbw+dwvnLughK5HspqCXLNW0amnmPN6CLnWvYsS8rdwxKoGtP2pScpHspKCXLFc0Kh+v312X/9x3I/uOnKLjG/Ea614kGynoJdt0uL48XzzWgpbX+se6v+ftZew5dNLrskRCnoJeslV0Ef9Y96/cWYcN3x+jw7DFTFixm5w45pJIqFDQS7YzM+6Kq8icx5pTJ6Y4T09dx0Pvr+THYxpCQSQrKOjFMzElCvJxn4b8/Xc1Sdh+kHZD/UMo6OpeJHMp6MVTYWFGr6aVfjGEwoBPVnHohIZQEMksCnrJEapEF2byI415qkN1vtz4A+2GLuLLDT94XZZISFDQS44RER7Go62qMnNAM8oUiaLvh4kMmbSao6c0T63IlVDQS45To3xRpvdvyqA21Zix+nvaD13Mwm+TvC5LJNdS0EuOlD/CP0/ttEebUCQqgl7vreSZqWv56bSu7kUyKuigN7NwM1tlZrNSWdfLzJLNbHXg1SfFup5mtjXw6plZhUveUCemOJ8ObEa/llWYuHIPHYYtYem2A16XJZKrZOSKfjCw6TfWT3TO1Q28xgKYWUngOaAh0AB4zsxKXHa1kidF5Qvn6VuvY3K/JkRGhHHv2OX8dfo6Tpw573VpIrlCUEFvZjFAR2BsBn9/e2Cuc+6Qc+4wMBfokMHfIQJA/WtKMHtwc/o0q8THy3fTYfhivt5+0OuyRHK8YK/ohwFPAb81xmw3M1trZlPMrGJgWQVgT4pt9gaW/YqZ9TUzn5n5kpM1M5GkLipfOH/tVJNJjzQm3Ix73l7GczPWc/Ksru5F0pJu0JtZJyDJOZf4G5t9CsQ65+rgv2ofl9FCnHNjnHNxzrm46OjojO4uecxNsSX5fHCL/01ucuvwJSzfoat7kdQEc0XfFOhsZruACUBrM/so5QbOuYPOuTOBj2OB+oH3+4CKKTaNCSwTuWIF8vsnN5nYtxHOQfcxy/j7zA26uhe5RLpB75x7xjkX45yLBXoA851z96XcxszKp/jYmf+7afsF0M7MSgRuwrYLLBPJNA0rl2LOY83p1SSW9xN26epe5BKX3Y/ezF4ws86Bj4PMbIOZrQEGAb0AnHOHgBeBlYHXC4FlIpmqYP4I/t65FhN0dS/yK5YTRwqMi4tzPp/P6zIklzp59jz/nvMt7yfsomLJArzcrQ5NqpT2uiyRLGVmic65uNTW6clYCTkXr+4v9sz5/dv+fvfH1e9e8igFvYSsBpX8PXN6B/rdtx+6mPiteqpW8h4FvYS0AvnDebZTTab0a0xkRBj3vbOcZ6au5ZjGzJE8REEveUL9a0oye3BzHmlRmYkr99B+6GIWaERMySMU9JJnROUL55nbavDfPzShcGQED763kiGTVnPkpGazktCmoJc8p97VJZg1qBkDW1dlxurvaTt0MXPWazYrCV0KesmTIiPCeaJddWYOaEqZIpH0+yiR/h9/Q/JPZ9LfWSSXUdBLnlbrqmJM79+UP7avztyNP9J26CKmrdpLTny+RORyKeglz8sXHkb/m6vy2aBmVCpdiMcnruGh91fy/ZFTXpcmkikU9CIB1coWYUq/JjzbqSbLdhyi3dDFfLTsO37+WVf3krsp6EVSCA8zejerxBePteCGisX46/T13PP2MnYeOOF1aSKXTUEvkoqrSxXko94NeblbbTbuP0aHYYt5a9F2zl/4rbl3RHImBb1IGsyM7jddzVdDWtLy2mj+9flmbh+VwMbvj3ldmkiGKOhF0lG2aBRv3V+fUffeyP6jp+g8Mp5XvtjM6XMXvC5NJCgKepEgmBm31S7PV0Na0rVeBd5csJ3bRixhxU5NryA5n4JeJAOKF8zPq3fdwIe9G3D2/M/c/dbX/GXaOg2SJjmagl7kMjSvFs2Xj/uHQB6/YjftXl/M3I0/el2WSKoU9CKXqWD+CJ7tVJNpjzaleMF8PPyBj0c/TiTpp9NelybyC0EHvZmFm9kqM5uVyrohZrbRzNaa2TwzuybFugtmtjrwmplZhYvkFDdULM6nA5vxx/bV+WpTEre8togJK3ZrGAXJMTJyRT8Y2JTGulVAnHOuDjAF+HeKdaecc3UDr86p7y6Su10cRmHO4ObUKF+Up6euo8eYZexIPu51aSLBBb2ZxQAdgbGprXfOLXDOnQx8XAbEZE55IrlL5ejCjH+4Ef+6I/Cg1fAljJy/lbPn9aCVeCfYK/phwFNAMP+19gY+T/E5ysx8ZrbMzLqmtZOZ9Q1s50tOTg6yLJGcJyzMuKfB1cwb0pJbapTh1S+38Ls34vlm92GvS5M8Kt2gN7NOQJJzLjGIbe8D4oBXUiy+xjkXB/weGGZmVVLb1zk3xjkX55yLi46ODq56kRysTNEoRt1bn7cfiOPY6XN0G53AczPW85O6Yko2C+aKvinQ2cx2AROA1mb20aUbmdktwF+Azs65/83e4JzbF/i5A1gI1LvyskVyj7Y1yzJ3SEt6No7lg2Xf0fb1xXyxQTNaSfZJN+idc88452Kcc7FAD2C+c+6+lNuYWT3gLfwhn5RieQkziwy8L43/H42NmVi/SK5QODKCv3euxdQ/NKF4wXw88mEij3zo44ej6oopWe+y+9Gb2QtmdrEXzStAYWDyJd0oawA+M1sDLABecs4p6CXPqnd1CT4d2Iw/dbiOhd8mc8vrixiXsIsLGvNespDlxL6+cXFxzufzeV2GSJb67uAJ/jp9PUu2HqBuxeL8647a1Chf1OuyJJcys8TA/dBf0ZOxIh65plQhPnioAcO612XPoZN0eiOef32+iVNnNSqmZC4FvYiHzIyu9Sow74mW3FU/hrcW7aDt0EUs/DYp/Z1FgqSgF8kBihfMz0vd6jCxbyMiI8Lo9d5K+n/yDUnHdLNWrpyCXiQHaVi5FLMHN+eJttcyd+OPtHltER9+rZu1cmUU9CI5TGREOAPbVAtMUF6cZ2ds4I7RCWz4/qjXpUkupaAXyaEqlS7Eh739N2v3HT5J55FL+cesjZw4c97r0iSXUdCL5GAXb9Z+NaQld8fFMDZ+J7e8vkhP1kqGKOhFcoHiBfPzrzvqMKVfY4oV8D9Z22ecj72HT6a/s+R5CnqRXCQutiSfDmzGM7dex9JtB2j7+mLeWrSdcxc0DLKkTUEvksvkCw/jkZZVmDukBU2rluZfn2+m04h4fLsOeV2a5FAKepFcKqZEQcb2jGPM/fU5fuY8d/7na56asoZDJ856XZrkMAp6kVyuXa1yzB3SgkdaVmbqN/to89pCJq7czc/qey8BCnqREFAwfwTP3FqDzwY1p2qZwvzpv+u4662v2bT/mNelSQ6goBcJIdXLFWHSI4155c467Dxwgk5vxPPirI0cV9/7PE1BLxJizIy74ioy/4mW3B1XkXeX7qTNawuZtfZ7cuKw5JL1FPQiIcrf9742U//QhNKFIxnwySoeeHcFO5KPe12aZDMFvUiIq3d1CWYOaMbznWuxes8ROgxbwqtffKtx7/MQBb1IHhAeZvRsEsv8J1rRqU55Ri7Yxi2vL+LLDT+oOScPUNCL5CHRRSJ5vXtdJvZtRKHIcPp+mEjvcT6+O3jC69IkCwUd9GYWbmarzGxWKusizWyimW0zs+VmFpti3TOB5d+aWfvMKVtErkTDyqX4bFBz/tqxBst3HKTt0MUMnbuF0+fUnBOKMnJFPxjYlMa63sBh51xVYCjwMoCZ1QR6ALWADsAoMwu//HJFJLPkCw+jT/PKzHuiFe1rlWP4vK20HbqIeZt+9Lo0yWRBBb2ZxQAdgbFpbNIFGBd4PwVoY2YWWD7BOXfGObcT2AY0uLKSRSQzlSsWxRv31OOThxsSGRFO73E++oxbye6DGhkzVAR7RT8MeApIa4i8CsAeAOfceeAoUCrl8oC9gWW/YmZ9zcxnZr7k5OQgyxKRzNKkSmlmD2rOn2+7joTtB7ll6CI154SIdIPezDoBSc65xKwsxDk3xjkX55yLi46OzsqvEpE05I8Io2+LKsy/pDln7sYf1TsnFwvmir4p0NnMdgETgNZm9tEl2+wDKgKYWQRQDDiYcnlATGCZiORgKZtzoiLCefgDHw++v5KdB9Q7JzdKN+idc88452Kcc7H4b6zOd87dd8lmM4Gegfd3BrZxgeU9Ar1yKgHVgBWZVr2IZKkmVUoze7C/d45v12HaD13MK19s5uRZjZ2Tm1x2P3oze8HMOgc+vgOUMrNtwBDgaQDn3AZgErARmAP0d86pwU8kF7nYO2f+ky3pVKc8by7YTpvXFmnsnFzEcuKJiouLcz6fz+syRCQVvl2H+NuMDWzcf4zGlUvx9861qF6uiNdl5Xlmluici0ttnZ6MFZEMuThv7Ytdr2fj/mPcNmIJz3+6gaOnznldmqRBQS8iGRYeZtzf6BoWPNmK7jdV5P2EXbR+dSGTVu7RzFY5kIJeRC5byUL5+efttfl0QDMqlS7EU/9dy+2jlrJq92GvS5MUFPQicsWur1CMyf0aM6x7XfYfPc3toxJ4cvIakn467XVpgoJeRDKJmdG1XgXmP9mKR1pWZsbqfbR+dRFvL97B2fNpPVQv2UFBLyKZqnCkf6LyLx9vSYNKJfl/szfRYfhiFnyb5HVpeZaCXkSyRKXShXi310281+smcPDgeyt5SE/XekJBLyJZ6ubryjDnsRb8+bbrWLHzEO2GLuJfszfx02l1x8wuCnoRyXL/GyztyZZ0rVuBtxbv4OZXFzHJp+6Y2UFBLyLZpkyRKF656wZm9G/K1SUL8NSUtXQdtZTE7w55XVpIU9CLSLa7oWJx/vuHJgzrXpekY2foNvprBo1fxfdHTnldWkhS0IuIJ/6vO2ZLBrWuypwNP9D6tYUM+2oLp85q7MPMpKAXEU8VzB/BkHbVmTekJW2uK8uwr7bS5rWFzFi9T6NjZhIFvYjkCBVLFuTNe29kYt9GlCiUn8ETVtNtdAJr9hzxurRcT0EvIjlKw8qlmDmgGS93q83uQyfp8uZShkxczQ9HNZzC5VLQi0iOEx5mdL/pahY82Yp+Laswa+1+bn51ISPmbVX7/WVQ0ItIjlUkKh9P33odXw1pSavq0bw+d4va7y+Dgl5EcryrSxVk9H31mZCi/f6O0Ql8o+GQg5Ju0JtZlJmtMLM1ZrbBzJ5PZZuhZrY68NpiZkdSrLuQYt3MzD4AEck7GlUuxacDmvHKnXXYd/gUd4xKYND4Vew9fNLr0nK0dOeMNTMDCjnnjptZPiAeGOycW5bG9gOBes65hwKfjzvnCmekKM0ZKyLpOXHmPP9ZtJ0xi3cA0Kd5Jf7QqiqFIyM8rswbVzRnrPM7HviYL/D6rX8d7gHGZ7hKEZEMKBQZwRPtqjP/yVZ0uL4cby7YTqtXFjJhxW4uaPycXwiqjd7Mws1sNZAEzHXOLU9ju2uASsD8FIujzMxnZsvMrOtvfEffwHa+5OTkDByCiORlFYoXYHiPekx7tAnXlCrI01PX0XHEEpZsVY5clG7TzS82NisOTAMGOufWp7L+T0CMc25gimUVnHP7zKwy/n8A2jjntv/W96jpRkQuh3OOz9bt5+U5m9lz6BQ3V4/mLx1rULVMEa9Ly3JX1HSTknPuCLAA6JDGJj24pNnGObcv8HMHsBCol5HvFBEJlpnRqc5VfDWkJX++7Tp8uw7TftgS/jp9HQeOn/G6PM8E0+smOnAlj5kVANoCm1PZ7jqgBPB1imUlzCwy8L400BTYmDmli4ikLjIinL4tqrDoqZu5r+HVjF+xh1avLGTUwm2cPpf3HrgK5oq+PLDAzNYCK/G30c8ysxfMrHOK7XoAE9wv24JqAD4zW4P/L4GXnHMKehHJFiUL5ef5LtfzxWMtaFS5JP+e8y1tXlvE9FX78tSEJxlqo88uaqMXkayQsP0A/5y9ifX7jlG7QjH+0rEGjSqX8rqsTJFpbfQiIrlZkyqlmdm/Ga/ddQMHjp+hx5hl9BnnY1vS8fR3zsUU9CKSp4SFGd3qx7DgyVb8sX11lu04SPthi3l2+vqQvWGrphsRydMOHD/DiHlb+Xj5bgrkC6dfy8r0blaZAvnDvS4tQ9R0IyKShtKFI3mhy/V8+XgLmlQpxatfbuHmVxcyybcnZJ6wVdCLiABVogsz5oE4Jj3SmLLFonhqylo6jljCwm+Tcv2QyAp6EZEUGlQqyfRHmzDy9/U4efYCvd5byX3vLGf9vqNel3bZFPQiIpe4+ITt3CEt+Funmmz8/hid3ojnsQmr2HMo9w2JrJuxIiLpOHb6HKMXbufd+J04B/c3voYBN1elRKH8Xpf2P791M1ZBLyISpP1HTzF07hYmJ+6lcGQEj7aqyoNNY4nK530PHQW9iEgm+vaHn3h5zmbmb06ifLEoHm97Ld1ujCE8zDyrSd0rRUQyUfVyRXi3101M6NuIMkX9PXRuHb6YeZt+zJE9dBT0IiKXqVHlUkx/tAmj7r2Rcxccvcf56P7WMhK/y1mTlivoRUSugJlxW+3yfPl4C17sej07Dpyg2+gE+n7gY1vST16XB6iNXkQkU504c55343fy1uIdnPrihJEAAAZgSURBVDx7nrvqV+SxttUoX6xAln6vbsaKiGSzg8fPMHLBNj5a9h1hZvRqEssfWlWheMGs6ZKpoBcR8cieQycZOncL01bvo0hkBP1aVeHBJpUyfdA0Bb2IiMc27T/Gq198y7zNSZQpEsngW6pxd1xF8oVnzq1Sda8UEfFYjfJFeafXTUzu15irSxbkL9PW0/b1Rcxc832WT2uooBcRyUY3xZZkcr/GvNMzjsiIcAaNX0WnN+KzdJTMdIPezKLMbIWZrTGzDWb2fCrb9DKzZDNbHXj1SbGup5ltDbx6ZvYBiIjkNmZGmxplmT24OUO738Cx0+fo9d5KeoxZxqmzFzL9+yKC2OYM0No5d9zM8gHxZva5c27ZJdtNdM4NSLnAzEoCzwFxgAMSzWymcy5nPU0gIuKB8DDj9noxdKx9FRNW7mbDvmNZMrNVukHv/H9LXJw5N1/gFezfF+2Buc65QwBmNhfoAIzPeKkiIqEpf0QYDzSOzbLfH1QbvZmFm9lqIAl/cC9PZbNuZrbWzKaYWcXAsgrAnhTb7A0sS+07+pqZz8x8ycnJGTgEERH5LUEFvXPugnOuLhADNDCz6y/Z5FMg1jlXB5gLjMtoIc65Mc65OOdcXHR0dEZ3FxGRNGSo141z7giwAH/zS8rlB51zZwIfxwL1A+/3ARVTbBoTWCYiItkkmF430WZWPPC+ANAW2HzJNuVTfOwMbAq8/wJoZ2YlzKwE0C6wTEREskkwvW7KA+PMLBz/PwyTnHOzzOwFwOecmwkMMrPOwHngENALwDl3yMxeBFYGftcLF2/MiohI9tAQCCIiIUBDIIiI5GEKehGREJcjm27MLBn47jJ3Lw0cyMRycoO8eMyQN487Lx4z5M3jzugxX+OcS7Vveo4M+ithZr602qlCVV48Zsibx50Xjxny5nFn5jGr6UZEJMQp6EVEQlwoBv0YrwvwQF48Zsibx50Xjxny5nFn2jGHXBu9iIj8Uihe0YuISAoKehGREBcyQW9mHczsWzPbZmZPe11PVjGzima2wMw2BqZ2HBxYXtLM5gambJwbGEQupATmRVhlZrMCnyuZ2fLAOZ9oZvm9rjGzmVnxwBwPm81sk5k1DvVzbWaPB/7bXm9m4wPTmYbcuTazd80syczWp1iW6rk1vxGB419rZjdm5LtCIugDA669CdwK1ATuMbOa3laVZc4DTzjnagKNgP6BY30amOecqwbMC3wONYP5v5FRAV4GhjrnqgKHgd6eVJW1hgNznHPXATfgP/6QPddmVgEYBMQ5564HwoEehOa5fp9Lhnwn7XN7K1At8OoLjM7IF4VE0AMNgG3OuR3OubPABKCLxzVlCefcfufcN4H3P+H/H78C/uO9OOHLOKCrNxVmDTOLATrin+8AMzOgNTAlsEkoHnMxoAXwDoBz7mxgToiQPtf4R9UtYGYRQEFgPyF4rp1zi/GP9ptSWue2C/CB81sGFL9kePjfFCpBH/SUhaHEzGKBesByoKxzbn9g1Q9AWY/KyirDgKeAnwOfSwFHnHPnA59D8ZxXApKB9wJNVmPNrBAhfK6dc/uAV4Hd+AP+KJBI6J/ri9I6t1eUcaES9HmOmRUG/gs85pw7lnJdYEL3kOk3a2adgCTnXKLXtWSzCOBGYLRzrh5wgkuaaULwXJfAf/VaCbgKKMSvmzfyhMw8t6ES9HlqykIzy4c/5D92zk0NLP7x4p9ygZ9JXtWXBZoCnc1sF/5mudb4266LB/68h9A853uBvc655YHPU/AHfyif61uAnc65ZOfcOWAq/vMf6uf6orTO7RVlXKgE/UqgWuDOfH78N29melxTlgi0Tb8DbHLOvZ5i1UygZ+B9T2BGdteWVZxzzzjnYpxzsfjP7Xzn3L345y++M7BZSB0zgHPuB2CPmVUPLGoDbCSEzzX+JptGZlYw8N/6xWMO6XOdQlrndibwQKD3TSPgaIomnvQ550LiBdwGbAG2A3/xup4sPM5m+P+cWwusDrxuw99mPQ/YCnwFlPS61iw6/lbArMD7ysAKYBswGYj0ur4sON66gC9wvqcDJUL9XAPP45+Xej3wIRAZiucaGI//PsQ5/H+99U7r3AKGv2fhdmAd/l5JQX+XhkAQEQlxodJ0IyIiaVDQi4iEOAW9iEiIU9CLiIQ4Bb2ISIhT0IuIhDgFvYhIiPv/qdpbRc7ZfvYAAAAASUVORK5CYII=\n","text/plain":["<Figure size 432x288 with 1 Axes>"]},"metadata":{"needs_background":"light"}}]},{"cell_type":"code","metadata":{"id":"Nyl5xXrybFcE","colab":{"base_uri":"https://localhost:8080/","height":282},"executionInfo":{"status":"ok","timestamp":1633185246914,"user_tz":-330,"elapsed":894,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"e58ab367-c65b-44d0-fb5f-b72d48c857c6"},"source":["pd.Series(costs3).plot(kind='line')"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["<matplotlib.axes._subplots.AxesSubplot at 0x7fc68b693dd0>"]},"metadata":{},"execution_count":32},{"output_type":"display_data","data":{"image/png":"iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3dd3hVVb7G8e8vIQFCCS20UELHiBQJCCQ0AUWkKDYcFcXCoEgTHb1Mcbwz3quj0puIXayAgJVRBEINJEhv0osIofcSWPePHGe8TAIBTtg557yf58njOWevnP3bbn2fnbXXXsucc4iISOAL87oAERHxDwW6iEiQUKCLiAQJBbqISJBQoIuIBIl8Xu24VKlSLi4uzqvdi4gEpLS0tL3OuZistnkW6HFxcaSmpnq1exGRgGRmW7Pbpi4XEZEgoUAXEQkSCnQRkSChQBcRCRIKdBGRIKFAFxEJEhcNdDOraGYzzWy1ma0ys35ZtGllZofMbKnv5y+5U66IiGQnJ1foGcBA51w80ATobWbxWbSb45yr7/v5b79W+Rv7j53mhS9WceL02dzahYhIQLpooDvndjnnlvheHwHWALG5XVh25m3Yyzvzt9Bt3AL2HD7pVRkiInnOJfWhm1kc0ABIyWJzUzNbZmbfmNm1fqgtS53qlWfcAwn8tOconUfOY+XOQ7m1KxGRgJLjQDezwsAkoL9z7vB5m5cAlZ1z9YARwJRsvqOnmaWaWWp6evrl1ky7+DJM7NWMMIO7xi7g25W7Lvu7RESCRY4C3cwiyAzzCc65yedvd84dds4d9b3+Gogws1JZtBvnnEtwziXExGQ5t0yOxZcvypQnE6ldrgi9PljCqJkb0HJ6IhLKcjLKxYA3gTXOucHZtCnra4eZNfZ97z5/FpqV0kUK8NFjTbitfnlemb6OAZ8s5eQZ3SwVkdCUk9kWE4EHgBVmttT32SCgEoBzbixwJ/C4mWUAJ4Bu7ipdLheICGfIPfWpUaYIr0xfx9b9x3n9gYaULlLgauxeRCTPMK+6KRISEpy/p8/9ZsUunvp0GcWjIhjXPYE6sdF+/X4REa+ZWZpzLiGrbUH1pOgt15Xjs15NcWTeLP1mhW6WikjoCKpAB6gTG81U383SxycsYfiMn3SzVERCQtAFOvz7ZmnXBrEM/m49fT76UU+WikjQ82wJutxWICKc1+6uR82yRXj527Vs3Xeccd0bUi66oNeliYjkiqC8Qv+VmdGrZTXGd09g895jdBoxjyXbDnhdlohIrgjqQP9Vm2vKMPmJZkRFhtPt9YVMTNvhdUkiIn4XEoEOULNMEab2TqRh5eI8/dky/v7lajLOnvO6LBERvwmZQAcoXiiS9x5pzINNKzN+7mZ6vLOYQ8fPeF2WiIhfhFSgA0SEh/FClzr8b9frWLhpH7eNnseGPUe9LktE5IqFXKD/6t7GlfjwsSYcPnGG20fN44e1u70uSUTkioRsoAM0iivBtD5JVCoZxSPvpjJ6lmZsFJHAFdKBDhBbrCATezWjY93y/OPbdXoISUQCVsgHOkDByHCGd6vPs+1r89WKXdwxZj47Dhz3uiwRkUuiQPcxMx5vVY23HmzE9gPH6TxyHgs25vqU7iIifqNAP0/r2qWZ0juR4lER3P9mCu/O36J+dREJCAr0LFSLKcznvRNpXSuG56et4g8Tl2slJBHJ8xTo2ShaIIJxDyTQ98bqfJa2g3vGLeSXQye9LktEJFsK9AsICzOeuqkWY+9vyIbdR+g4Yi6pW/Z7XZaISJYU6DnQvk5ZpvROpEiBfNz7xkI+WLhV/eoikudcNNDNrKKZzTSz1Wa2ysz6XaBtIzPLMLM7/Vum92qUKcKU3ok0rxHDn6as5NlJ6lcXkbwlJ1foGcBA51w80ATobWbx5zcys3DgZeCf/i0x74guGMH47pn96p+m7uCe1xfw88ETXpclIgLkINCdc7ucc0t8r48Aa4DYLJr2ASYBe/xaYR7z//rV9xyl04i5LNyk8eoi4r1L6kM3szigAZBy3uexwO3AmIv8fk8zSzWz1PT09EurNI9pX6csU59MJDoqgvvGp/DW3M3qVxcRT+U40M2sMJlX4P2dc4fP2zwUeNY5d8EVI5xz45xzCc65hJiYmEuvNo+pXjqzX711rdL895erGfDJUs0DIyKeyVGgm1kEmWE+wTk3OYsmCcDHZrYFuBMYbWa3+a3KPCxzvHpDBrarydRlP9N1zHy27dM8MCJy9eVklIsBbwJrnHODs2rjnKvinItzzsUBE4EnnHNT/FppHhYWZvRpU4O3HmrEzwdP0GnkXGatC+pbCSKSB+XkCj0ReAC40cyW+n46mFkvM+uVy/UFlNa1SvPFk0mUL1aQHu8sZsSMnzh3Tv3qInJ1mFc38hISElxqaqon+85tJ06fZdDnK/j8x520vaY0r91dn+iCEV6XJSJBwMzSnHMJWW3Tk6K5oGBkOIPvrscLna9l1rp0uoycy9pfzr+PLCLiXwr0XGJmPNgsjo97NuH46bPcNmoeU37c6XVZIhLEFOi5LCGuBF/2TaJuhWL0/2Qpz09dyemMC47uFBG5LAr0q6B0kQJMePQGHk2qwrsLttJt3AJ2HdKUASLiXwr0qyQiPIw/dYxn1O+uZ90vR+g4fC7zN+71uiwRCSIK9Kvs1rrlmPpkIsULRXL/+BTGzNqoKQNExC8U6B6oXroIU3sn0uG6crz87Vp6vp/GoRNnvC5LRAKcAt0jhfLnY8S9DXi+Uzwz1+6h88i5rPr5kNdliUgAU6B7yMzokViFj3s24eSZs9w+ej6fLN7mdVkiEqAU6HlAQlwJvurbnEZxxXl20gqe+WyZVkMSkUumQM8jShXOz3sP30CfG6vzWdoObhs1j817j3ldlogEEAV6HhIeZgy8qRZv92jEL4dP0nnEXL5ducvrskQkQCjQ86DWtUrzZZ8kqsYUotcHS/jvL1br6VIRuSgFeh5VoXgUn/VqxkPN4nhr3ma6jdOC1CJyYQr0PCwyXxh/7XwtI3/XgPW7j3Lr8DlaOENEsqVADwAd65Zn2pOJlClagIfeXsyr09eRcVZdMCLy/ynQA0TVmMJM6Z1It0YVGTlzA/eNT2HP4ZNelyUieYgCPYAUiAjnpTvq8tpd9Vi+4xAdhs9h3gZN8CUimXKySHRFM5tpZqvNbJWZ9cuiTRczW+5bbzTVzJJyp1wBuKNhBaY9mUjxqEjufzOFId+t56zWLhUJeTm5Qs8ABjrn4oEmQG8ziz+vzQygnnOuPvAwMN6/Zcr5apQpwtQnE+naoALDZvzE/eNT2HNEXTAioeyige6c2+WcW+J7fQRYA8Se1+ao+/ccsIUAXS5eBVGR+Xjt7nq8cmddftx+gA7D5qoLRiSEXVIfupnFAQ2AlCy23W5ma4GvyLxKz+r3e/q6ZFLT09MvvVrJ0l0JFZn2ZBLFoiK4/80UBqsLRiQkWU4XVzCzwsBs4EXn3OQLtGsB/MU51/ZC35eQkOBSU1MvpVa5iOOnM/jzlFVMWrKDJlVLMKxbA8oULeB1WSLiR2aW5pxLyGpbjq7QzSwCmARMuFCYAzjnkoGqZlbqkiuVK/JrF8yrd9Vj2fZDdBg2h9nr9ZeQSKjIySgXA94E1jjnBmfTprqvHWZ2PZAf2OfPQiXn7mxYgS/6JFKqcH4efGsRL32zljN6EEkk6OXLQZtE4AFghZkt9X02CKgE4JwbC9wBdDezM8AJ4B6nhTI9Vb105iiYF75YzdjZG1m0eR/D721AheJRXpcmIrkkx33o/qY+9Ktn2rKfGTR5BWEG/7izHu3rlPW6JBG5TFfchy6BrXO98nzZJ4nKJQvR64M0/jJ1pVZEEglCCvQQEVeqEJMeb8YjSVV4b8FWbh89n43pR70uS0T8SIEeQiLzhfHnjvG8+WACvxw6QacRc5mYtgPd7hAJDgr0ENTmmjJ8068F18VG8/RnyxjwyVKOnsrwuiwRuUIK9BBVNroAHz7WhKfa1WTasp+5dfgclu846HVZInIFFOghLDzM6NumBp/8vilnMs5xx5j5jEveyDlNGyASkBToQqO4Enzdrzltapfhf75ey4NvL9LMjSIBSIEuABSLimTM/dfz4u11WLR5Px2Gaf1SkUCjQJd/MTPuu6EyX/RJomSh/Dz09mL+9uVqTmVozLpIIFCgy3+o6Vs848GmlXlz7ma6asy6SEBQoEuWCkSE80KXOozvnsDPB0/QcfhcPl60TWPWRfIwBbpcUNv4MnzbvwUNKxfnuckrePyDJRw8ftrrskQkCwp0uagyRQvw3sONGdShNjPW7qb90DnM36il7kTyGgW65EhYmNGzRTU+fyKRqMhw7hufwkvfrOV0huZZF8krFOhySerERvNl3yS6NarI2Nkb6Tpmnm6YiuQRCnS5ZFGR+fjfrnUZe39DdhzIvGH6kW6YinhOgS6XrX2dskz33TD9r8kr6Pl+GvuP6YapiFcU6HJFfr1h+qdbr2H2unRuHpqsJ0xFPKJAlysWFmY82rwqU3onUjwqgofeXsxfp63SqkgiV9lFA93MKprZTDNbbWarzKxfFm3uM7PlZrbCzOabWb3cKVfysvjyRZn2ZBI9EuN4Z/4WOo6Yy8qdh7wuSyRk5OQKPQMY6JyLB5oAvc0s/rw2m4GWzrnrgL8B4/xbpgSKAhHhPN/pWt57uDGHT5zh9tHzGDNrI2c1Ja9IrrtooDvndjnnlvheHwHWALHntZnvnDvge7sQqODvQiWwtKgZw/T+LWh7TRle/nYt945byPb9x70uSySoXVIfupnFAQ2AlAs0ewT4Jpvf72lmqWaWmp6efim7lgBUvFAko++7nlfvqsfqXYe5ZdgcJmkNU5FcYzn9n8vMCgOzgRedc5OzadMaGA0kOef2Xej7EhISXGpq6iWWK4Fq+/7jDPx0GYu27OeWOmV58fbrKFEo0uuyRAKOmaU55xKy2pajK3QziwAmARMuEOZ1gfFAl4uFuYSeiiWi+KhnE567pTbfr9nNzUOTmblWwxtF/Ckno1wMeBNY45wbnE2bSsBk4AHn3Hr/lijBIjzM6NWyGlN7J1EiKpIe7yxm0OcrOHYqw+vSRILCRbtczCwJmAOsAH6diWkQUAnAOTfWzMYDdwBbfdszsvuT4FfqcgltJ8+cZfB363ljziYqlYhi8N31aVi5uNdlieR5F+pyyXEfur8p0AVg4aZ9DPx0GbsOnaBXy2r0b1uTyHx63k0kO1fchy6SW5pULcm3/ZtzV8OKjJ61kS6j5rH2l8NelyUSkBTo4rkiBSJ4+c66vNE9gfQjJ+k8Qg8jiVwOBbrkGe3iyzC9fwvaXFOal79dy11j57N57zGvyxIJGAp0yVNKFs7P6PuuZ+g99dmw5yi3DEvm3flbOKerdZGLUqBLnmNm3NYgln8OaMkNVUry/LRVPPBWCjsPnvC6NJE8TYEueVbZ6AK806MR/3P7dfy47SDthyTz6eLtmjpAJBsKdMnTzIzf3VCJ6f1bEF++KH+YtJxH3k1l9+GTXpcmkuco0CUgVCwRxUePNeH5TvHM37iXdoNn8/mPmuhL5LcU6BIwwsKMHolV+Lpvc2qUKcKAT5bx+/fTSD9yyuvSRPIEBboEnKoxhfn0900Z1KE2s9an027IbKYu3amrdQl5CnQJSOFhRs8W1fi6bxKVSxai38dLefyDJbpal5CmQJeAVr10ESb1asqz7Wvzw9o93DRkNl8s+1lX6xKSFOgS8PKFh/F4q2p81TeJSiWi6PPRj/T6II09RzQSRkKLAl2CRo0yRZj0eDOeu6U2M9elc9OQZPWtS0hRoEtQyRceRq+WmX3rcb6+9cfeS2OPxq1LCFCgS1CqXjrzav2PHa5hzk/ptB08m4laoFqCnAJdglZ4mPFYi6p80685NcsU4enPlvHQ24s1J4wELQW6BL1fx63/tVM8izbv5+YhyUxI2aoZHCXo5GSR6IpmNtPMVpvZKjPrl0Wb2ma2wMxOmdnTuVOqyOULCzMeSqzC9P4tqFshmj9+vpLfjV/I1n2ab12CR06u0DOAgc65eKAJ0NvM4s9rsx/oC7zq5/pE/KpSySgmPHoDL3W9jlU7D3Pz0GTGz9mk1ZEkKFw00J1zu5xzS3yvjwBrgNjz2uxxzi0GzuRKlSJ+ZGZ0a1yJfz7VgsRqpfj7V2u4Y8x81u8+4nVpIlfkkvrQzSwOaACkXM7OzKynmaWaWWp6evrlfIWI35SLLsj4BxMY1q0+2/Yf59bhcxj6/XpOZ5zzujSRy5LjQDezwsAkoL9z7rKWZXfOjXPOJTjnEmJiYi7nK0T8yszoUj+W7wa04JY65Rj6/U90HDGHH7cd8Lo0kUuWo0A3swgyw3yCc25y7pYkcvWVLJyf4fc24K2HEjhyMoOuY+bzwherOHYqw+vSRHIsJ6NcDHgTWOOcG5z7JYl458baZfjngBbcf0Nl3p63hZuGJDN7vboHJTDYxZ6cM7MkYA6wAvi1c3EQUAnAOTfWzMoCqUBRX5ujQPyFumYSEhJcamrqFR+ASG5ZvGU/z01azsb0Y9zeIJY/d4ynRKFIr8uSEGdmac65hCy3efUotAJdAsGpjLOM+mEDY2ZvpEiBCP7SMZ4u9cuT+YeryNV3oUDXk6IiF5A/XzhP3VSLL/s0p3LJKPp/spQH317M9v3HvS5N5D8o0EVyoFbZIkzs1Yy/doonbct+bhqSzBvJm8g4qyGOknco0EVyKNw3fcB3T7UksXpJXvx6DV1GzWPFjkNelyYCKNBFLln5YgV5o3sCo++7nvQjp+gyai5/+3K1hjiK5xToIpfBzOhwXTm+e6ol9zauxJtzN3PTkGRmrNntdWkSwhToIlcgumAEL95+HRN7NSUqMpxH3k3liQlp7NYKSeIBBbqIHyTEleCrvs155uZazFizh7avzea9BVs0i6NcVQp0ET+JzBdG79bV+eeAFtSvVIy/TF1F1zHzWfWzbprK1aFAF/GzyiUL8d7DjRnWrT47Dxyn88h5/F03TeUqUKCL5IJfZ3Gc8VQr7k6oyPi5m2k7eDbTV/3idWkSxBToIrkoOiqC/+16HZMeb0Z0wQh+/34aj767mB0H9KSp+J8CXeQqaFi5OF/0SWJQh9rM27CPdoOTGTt7I2f0pKn4kQJd5CqJCA+jZ4tqfD+wJc1rlOKlb9Zy6/A5LNq83+vSJEgo0EWusthiBRnXPYHx3RM4duosd7++gIGfLmPv0VNelyYBToEu4pG28WX47qkWPN6qGlOX7uTGV2fxwcKtGrsul02BLuKhqMh8PNu+Nt/0a058+aL8acpKuo7WhF9yeRToInlAjTJF+OixJgy9pz47D56k86i5/HnKSg4dP+N1aRJAFOgieYSZcVuDWH54uiUPNo1jQspWbnxtFp+lbuecumEkBxToInlM0QIR/LXztUx7MolKJaN4ZuJy7n59Aat/znaJXhEgB4FuZhXNbKaZrTazVWbWL4s2ZmbDzWyDmS03s+tzp1yR0FEnNppJvZrxjzvrsmnvMTqOmMNfp63i0Al1w0jWcnKFngEMdM7FA02A3mYWf16bW4Aavp+ewBi/VikSosLCjLsTKjJzYCvuu6Ey7y3YQht1w0g2LhrozrldzrklvtdHgDVA7HnNugDvuUwLgWJmVs7v1YqEqOioCP52W53MbpgSmd0wd46dz8qdGg0j/3ZJfehmFgc0AFLO2xQLbP/N+x38Z+hjZj3NLNXMUtPT0y+tUhGhTmw0E33dMFv3HafTyLn8acoKDh4/7XVpkgfkONDNrDAwCejvnLusuzPOuXHOuQTnXEJMTMzlfIVIyPu1G+aHp1vxULM4Plq0ndavzmJCih5KCnU5CnQziyAzzCc45yZn0WQnUPE37yv4PhORXBJdMILnO13LV32TqFmmCH/8fCVdRs0lbavmhglVORnlYsCbwBrn3OBsmk0DuvtGuzQBDjnndvmxThHJRu2yRfm4ZxOG39uAvUdOc8eYBTz1yVL2aF3TkJMvB20SgQeAFWa21PfZIKASgHNuLPA10AHYABwHevi/VBHJjpnRuV552tQuzehZG3gjeTPTV/1CnzY16JEYR/584V6XKFeBOedNn1tCQoJLTU31ZN8iwW7rvmP87cvVfL9mD1VKFeIvHeNpXbu012WJH5hZmnMuIattelJUJAhVLlmI8Q824p0ejTCDHu8spsfbi9iUftTr0iQXKdBFglirWqX5tl8L/tjhGhZvOcDNQ5N58avVHD6pp02DkQJdJMhF5gvjsRZVmfl0K7o2qMD4uZu58dVZfLxom4Y5BhkFukiIiCmSn5fvrMsXTyYRV7IQz01eQeeRc0nZtM/r0sRPFOgiIaZObDSf9WrKiHsbcODYae4Zt5DeE5awff9xr0uTK6RAFwlBZkaneuWZMbAV/dvWYMba3bQZPJtXpq/l2KkMr8uTy6RAFwlhBSPD6d+2JjOfbkWHOmUZNXMjrV/VbI6BSoEuIpSLLsjQbg2Y/EQzyhcryDMTl9N5lPrXA40CXUT+5fpKxfn8iWYM61affUcz+9d7vZ/G1n3HvC5NckCBLiL/j5nRpX4sPwxsxcB2NUn+KZ12g5P5n6/XaLWkPE6BLiJZKhgZTp82NZj5dCu61C/PG3M20eqVmby3YAtnzp7zujzJggJdRC6oTNECvHJXPb54MonaZYvyl6mruHloMt+v3o1Xc0FJ1hToIpIjdWKj+fCxG3ijewI4ePS9VH73RoqWwctDFOgikmNmRrv4Mkwf0IIXOl/L2l8O02nkXJ76dCm7Dp3wuryQp+lzReSyHTpxhtGzNvD2vC0Y8GjzKvRqWY0iBSK8Li1oafpcEckV0QUj+K9brmHGUy25+drMB5NavTKL9xfoxqkXFOgicsUqlohi+L0NmPZkItVLF+bPU1dx85Bkvl35i26cXkUKdBHxm7oVivFxzyaM756AGfT6II27X1/Akm0HvC4tJORkkei3zGyPma3MZntxM/vczJab2SIzq+P/MkUkUJgZbePLML1/C168vQ6b9x6n6+j5PDEhjc179cRpbsrJFfo7QPsLbB8ELHXO1QW6A8P8UJeIBLh84WHcd0NlZj/TigFtazJrXTrtBs/mz1NWkn7klNflBaWLBrpzLhnYf4Em8cAPvrZrgTgzK+Of8kQk0BXKn49+bWsw+5nWdGtckQ8XbaPlKzMZ8t16jmqqXr/yRx/6MqArgJk1BioDFbJqaGY9zSzVzFLT09P9sGsRCRQxRfLz99uu47sBLWhVK4ZhM37611QCpzM0IsYfcjQO3czigC+dc//RP25mRcnsZmkArABqA48555Ze6Ds1Dl0ktP247QAvfbOWlM37qVwyiqdvqsWt15UjLMy8Li1Py9Vx6M65w865Hs65+mT2occAm670e0UkuDWoVJyPezbh7R6NKBgRTp+PfqTzqLkkr0/XUMfLdMWBbmbFzCzS9/ZRINk5d/hKv1dEgp+Z0bpWab7q25zBd9fjwLEzdH9rEfeNT2Hp9oNelxdwLtrlYmYfAa2AUsBu4HkgAsA5N9bMmgLvAg5YBTzinLvooFN1uYjI+U5lnOXDlG2M+GED+4+dpv21ZXn65lpUL13Y69LyjAt1uWguFxHJc46eymD8nE28kbyJE2fOcmfDCvRrW5PYYgW9Ls1zCnQRCUj7jp5i1MyNfLBwKwD3N6nME62rUapwfo8r844CXUQC2s6DJxj2/Xompu2gYEQ4jyRV4dEWVSkagrM6KtBFJChs2HOUId+t56sVuygWFUGvltV4sGkcBSPDvS7tqlGgi0hQWbnzEK9MX8fs9enEFMlPnxur061RJSLzBf98gwp0EQlKi7fs55Vv17Foy35iixWkX9sadG0QS77w4A12LXAhIkGpUVwJPvl9E959uDElC0fyh4nLaTckmalLd3LuXOg9nKRAF5GAZma0rBnD1N6JjHugIfnzhdHv46XcMmxOyC2woUAXkaBgZtx0bVm+7tucEfc24MzZc/T6II1OI+fyw9rdIRHsCnQRCSphYUaneuX554AWvHJnXQ6dOMPD76TSdcx85vwU3PPE6KaoiAS1M2fPMTFtByNm/MTPh07SKK44A9rVpFm1Ul6Xdlk0ykVEQt6pjLN8ung7I2duYPfhU9xQpQQD2tWkSdWSXpd2SRToIiI+J8+c5aNF2xg9ayPpR07RrFpJBrSrSaO4El6XliMKdBGR85w8c5YJKdsYM2sje4+eIql6Kfq1rZHng12BLiKSjROnzzIhZStjZ29k79HTeT7YFegiIhdx4vRZPli4ldeTM4M9sXpJ+rWpSeMqeSvYFegiIjn07yv2Tew9eoqmVUvSt00NmlbLGzdPFegiIpfoxOmzfLhoG2NnZ948bVylBP3a1KBZtZKYebeQtQJdROQynTxzlo8XbWPM7I3sPnyKhpWL0+fG6rSsGeNJsF/R5Fxm9paZ7TGzldlsjzazL8xsmZmtMrMeV1qwiEheUSAinIcSqzD7mdb87bY67Dp4gofeXsxto+bx3eq8NaVAThaJbgEcBd5zztXJYvsgINo596yZxQDrgLLOudMX+l5doYtIIDqdcY7JS3YwetZGtu0/zjXlitLnxuq0v7YsYWG5f8V+RVfozrlkYP+FmgBFLPNvj8K+thmXU6iISF4XmS+Mbo0r8cPAlrx2Vz1OnTnLExOWcNPQZD7/cQcZZ895Vps/JucaCVwD/AysAPo557w7IhGRqyBfeBh3NKzAd0+1ZMS9DQg3Y8Any7jxtdl8mLKNUxlnr3pN/gj0m4GlQHmgPjDSzIpm1dDMeppZqpmlpqen+2HXIiLeCvfN7vhNv+aMe6AhxaMiGPT5Clr+YxZvzd3M8dNXr8MiR6NczCwO+DKbPvSvgJecc3N8738AnnPOLbrQd6oPXUSCkXOOOT/tZeTMDSzavJ8ShSJ5JKkK9zepTHTBiCv+/txegm4b0Ma3ozJALWCTH75XRCTgmBktasbw6e+b8lmvptStEM0r09eR9NIP/OPbtew9eir39p2DUS4fAa2AUsBu4HkgAsA5N9bMygPvAOUAI/Nq/YOL7VhX6CISKlbuPMSYWRv5euUuIsPDeObmWjzavOplfaiaupEAAARuSURBVNeFrtDzXeyXnXP3XmT7z8BNl1WZiEgIqBMbzaj7rmdj+lFen72RCsUL5sp+LhroIiLiH9ViCvOPO+vl2vdrTVERkSChQBcRCRIKdBGRIKFAFxEJEgp0EZEgoUAXEQkSCnQRkSChQBcRCRKeLUFnZunA1sv89VLAXj+WEyhC8bhD8ZghNI87FI8ZLv24KzvnYrLa4FmgXwkzS81uLoNgForHHYrHDKF53KF4zODf41aXi4hIkFCgi4gEiUAN9HFeF+CRUDzuUDxmCM3jDsVjBj8ed0D2oYuIyH8K1Ct0ERE5jwJdRCRIBFygm1l7M1tnZhvM7Dmv68kNZlbRzGaa2WozW2Vm/XyflzCz78zsJ98/i3tda24ws3Az+9HMvvS9r2JmKb5z/omZRXpdoz+ZWTEzm2hma81sjZk1DYVzbWYDfP99rzSzj8ysQDCeazN7y8z2mNnK33yW5fm1TMN9x7/czK6/lH0FVKCbWTgwCrgFiAfuNbN4b6vKFRnAQOdcPNAE6O07zueAGc65GsAM3/tg1A9Y85v3LwNDnHPVgQPAI55UlXuGAd8652oD9cg89qA+12YWC/QFEpxzdYBwoBvBea7fAdqf91l25/cWoIbvpycw5lJ2FFCBDjQGNjjnNjnnTgMfA108rsnvnHO7nHNLfK+PkPk/eCyZx/qur9m7wG3eVJh7zKwCcCsw3vfegBuBib4mQXXcZhYNtADeBHDOnXbOHSQEzjWZS2AWNLN8QBSwiyA81865ZGD/eR9nd367AO+5TAuBYmZWLqf7CrRAjwW2/+b9Dt9nQcvM4oAGQApQxjm3y7fpF6CMR2XlpqHAH4BzvvclgYPOuQzf+2A751WAdOBtXzfTeDMrRJCfa+fcTuBVYBuZQX4ISCO4z/VvZXd+ryjjAi3QQ4qZFQYmAf2dc4d/u81ljjcNqjGnZtYR2OOcS/O6lqsoH3A9MMY51wA4xnndK0F6rouTeTVaBSgPFOI/uyVCgj/Pb6AF+k6g4m/eV/B9FnTMLILMMJ/gnJvs+3j3r39++f65x6v6ckki0NnMtpDZnXYjmf3LxXx/lkPwnfMdwA7nXIrv/UQyAz7Yz3VbYLNzLt05dwaYTOb5D+Zz/VvZnd8ryrhAC/TFQA3fnfBIMm+iTPO4Jr/z9Ru/Caxxzg3+zaZpwIO+1w8CU692bbnJOfdfzrkKzrk4Ms/tD865+4CZwJ2+ZkF13M65X4DtZlbL91EbYDVBfq7J7GppYmZRvv/efz3uoD3X58nu/E4DuvtGuzQBDv2ma+binHMB9QN0ANYDG4E/el1PLh1jEpl/gi0Hlvp+OpDZnzwD+An4Hijhda25+O+gFfCl73VVYBGwAfgMyO91fX4+1vpAqu98TwGKh8K5Bl4A1gIrgfeB/MF4roGPyLxPcIbMv8geye78AkbmSL6NwAoyRwHleF969F9EJEgEWpeLiIhkQ4EuIhIkFOgiIkFCgS4iEiQU6CIiQUKBLiISJBToIiJB4v8Aimb77xRP9FMAAAAASUVORK5CYII=\n","text/plain":["<Figure size 432x288 with 1 Axes>"]},"metadata":{"needs_background":"light"}}]},{"cell_type":"code","metadata":{"id":"_j2khUZ1bFcE","colab":{"base_uri":"https://localhost:8080/","height":282},"executionInfo":{"status":"ok","timestamp":1633185248847,"user_tz":-330,"elapsed":11,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"3f3e35d4-c6fe-4762-f26a-39e318594dc2"},"source":["pd.Series(combined_cost).plot(kind='line')"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["<matplotlib.axes._subplots.AxesSubplot at 0x7fc6921dd190>"]},"metadata":{},"execution_count":33},{"output_type":"display_data","data":{"image/png":"iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3dd3wVZb7H8c8vhYQWEAhgACnSBIUIoScUBRFEEEUEC+pSREFQLLtuvbq73qsiVYrAil1RRCkCCigkdEJXeifU0A1ICTz3jxzuzbJBAiSZnJPv+/U6r5wpzPyGwa+TZ555xpxziIiI/wvyugAREckaCnQRkQChQBcRCRAKdBGRAKFAFxEJECFe7bhEiRKuQoUKXu1eRMQvLV++/JBzLjKjZZ4FeoUKFUhMTPRq9yIifsnMdl5umZpcREQChAJdRCRAKNBFRAKEAl1EJEAo0EVEAoQCXUQkQCjQRUQChN8F+pGTZ3lt6jp+PXve61JERHIVvwv0+VsOMX7hdu4ftZDdR055XY6ISK7hd4HevnYU45+ox56jp7j3nfkkbE72uiQRkVzB7wIdoHm1kkx9NpbSEeE8/t5SRs3dit68JCJ5nV8GOkD54gWZ9Exj2t52I2/M3EDfT1dy8kyq12WJiHjGbwMdoEC+EIZ3vZ0/tq3OjJ/20XHkArYfOul1WSIinvDrQAcwM3o1vZkPf9eA5F/O0P6d+cxZf8DrskREcpzfB/pFsVVKMKVvLDcVK0D3DxIZPGsTFy6oXV1E8o6ACXSAcsUK8NXTjbm/ThmGztlMjw8TOX7qnNdliYjkiIAKdIDw0GDefrA2r3WoSfymZNqPmM/6fSe8LktEJNsFXKBDWrt6t0YVmPBUQ349e56OIxcwedUer8sSEclWARnoF9UtX4xp/WKpVaYo/T9fxatTf+bc+QtelyUiki0COtABShYO55OeDXiySQXGL9jBI2OXcPCX016XJSKS5QI+0AFCg4P42701GdolmrV7jtNu2HwSdxzxuiwRkSyVJwL9og7RZfi6T2MK5Aumy5jFjF+wXUMGiEjAyFOBDlC9dAST+8bSvFpJXp26jv6fr9KQASISEPJcoAMUyR/KmMfq8lLrakxbs5eOIxewLTnF67JERK5Lngx0gKAgo0+Lynz4uwYcSjlL+3cWMPOnfV6XJSJyzfJsoF8UW6UE056N5eaShej98Qpen76eVHVtFBE/lOcDHSCqaH6+eKohjza8iTHx23h4nLo2ioj/UaD7hIUE84/7bmNQ59qsSTpGu2HzWbpdXRtFxH8o0C9xf52yfNOnCQXDQug6djFj47epa6OI+AUFegbSujY2odUtpfjn9PU8/fEKTpzWqI0ikrtdMdDNrJqZrUr3OWFmz12yTnMzO55unb9mX8k5IyI8lFGP1uFPbW9h1voDtB+uURtFJHe7YqA75zY656Kdc9FAXeAU8HUGqyZcXM8591pWF+oFM6Nn00p81rMhp3yjNk5cnuR1WSIiGbraJpc7ga3OuZ3ZUUxuVb9i2qiN0eWK8uKXq3ll0hpOnzvvdVkiIv/magO9C/DZZZY1MrPVZjbDzGpmtIKZ9TKzRDNLTE5Ovspde6tk4XA+7t6APi1u5rOlu7l/5EJ2HtYLqUUk97DM9uAws3zAXqCmc+7AJcsigAvOuRQzawsMdc5V+a3txcTEuMTExGss21s/bDjA8xNWc8E53upUm7tvLe11SSKSR5jZcudcTEbLruYKvQ2w4tIwB3DOnXDOpfi+TwdCzazENVXrB+6oXoppz8ZSqURBen+8nH9MW6cXZ4iI564m0LtymeYWMyttZub7Xt+33cPXX17uVa5YAb7o3Yhujcozbv52uoxZzN5jv3pdlojkYZkKdDMrCLQCJqWb19vMevsmOwE/mdlqYBjQxeWBp3HCQoJ5rcOtDOt6Oxv2neCeYQnM3XjQ67JEJI/KdBt6VvPnNvSMbE1Ooc8nK9h44Bf6tqjMcy2rEhxkXpclIgEmq9rQ5TfcHFmIr59pQqc6ZRn+wxYe1QBfIpLDFOhZKH++YN56sDZvdarFyt1HaTt0Pgu3HvK6LBHJIxTo2eDBmHJM7hNLRP4QHh23hGFzNnP+QsDfUhARjynQs0m10oWZ2jeW9rWjGDRrE0+MX8qhlDNelyUiAUyBno0KhoUw+KFo/vv+21iy/QhthyawaGtA9+YUEQ8p0LOZmdG1/k1880wTCoWF8Mi4xQxXE4yIZAMFeg6pERXBlGdjaVcrirdnbeLx95aS/IuaYEQk6yjQc1ChsBCGdklrglm24whthyWoF4yIZBkFeg77vyaYPk0oHJ7WC2bobDXBiMj1U6B75JYbI5jaN5YO0WUYPHsT3d7Tg0gicn0U6B4qGBbCoM61efOBWizfeZS2QxNI2Oxf48SLSO6hQPeYmdG5Xjmm9I3lhgL56PbeUt76bgOpGo5XRK6SAj2XqFqqMFP6xtK5bjlG/LhVw/GKyFVToOci+fMF80anWgztEs36fSdoMzSBWev+430iIiIZUqDnQh2iyzCtXxzliuWn54eJ/NeUnzmTqpdSi8hvU6DnUhVLFOSrpxvzROMKvL9wB/ePXMj2Q3optYhcngI9FwsLCea/2tdkbLcY9hz7lXbDEvh6ZZLXZYlILqVA9wOtapRier84akYV4fkJq3nhi9WcPJPqdVkiksso0P1EVNH8fNqzAf3urMKklUncO3w+P+897nVZIpKLKND9SEhwEANaVeXTHg05eTaVjiMWMn7BdvLA+7hFJBMU6H6o0c3FmdG/KXFVSvDq1HX0/DCRIyfPel2WiHhMge6nihXMx7jHY/jbvTWI33SINkPjNXKjSB6nQPdjZsaTTSrydZ/GFAwL4ZFxS3jruw2c07ABInmSAj0A1IwqwrRnY+lUpywjftxK53cXsfvIKa/LEpEcpkAPEAXyhfDWg7UZ3vV2thxIoe3QBKas3ut1WSKSgxToAebe2lFM7x9H1dKF6ffZSl78cjUp6rMukico0ANQuWIFmNCrIf3uqMykFUm0G5bAmqRjXpclItlMgR6gQoKDGHBXNT7r2ZAzqRe4f+RCRs/bygW96k4kYCnQA1yDSsWZ0T+OVjVK8T8zNvDYe0vYf1yvuhMJRAr0PKBogXyMfKQObzxwGyt2HuPuofF89/N+r8sSkSx2xUA3s2pmtird54SZPXfJOmZmw8xsi5mtMbM62VeyXAsz46F6NzGtXyxlb8jPUx8t55VJazl1VjdMRQLFFQPdObfRORftnIsG6gKngK8vWa0NUMX36QWMyupCJWvcHFmISU834almlfh82S7aDZ/PT3s0yJdIILjaJpc7ga3OuZ2XzO8AfOjSLAaKmtmNWVKhZLl8IUG80uYWPu7egJNnUuk4cgFj4nXDVMTfXW2gdwE+y2B+GWB3uukk37x/Y2a9zCzRzBKTk5OvcteS1ZpULsHM/k25o3pJXp+uG6Yi/i7TgW5m+YD2wJfXujPn3BjnXIxzLiYyMvJaNyNZ6IaC+Rj9aN1/u2E6Y+0+r8sSkWtwNVfobYAVzrmMXkO/ByiXbrqsb574gYs3TL/tF8tNxQrw9CcreElPmIr4nasJ9K5k3NwCMAXo5uvt0hA47pzTZZ6fqRRZiK+ebkyfFjczcUUS9wxLYMWuo16XJSKZlKlAN7OCQCtgUrp5vc2st29yOrAN2AKMBZ7J4jolh4QGB/FS6+pM6NWI1POOB0cvYvCsTaRqSF6RXM+8en1ZTEyMS0xM9GTfkjknTp/jb5N/5uuVe4guV5QhD0VToURBr8sSydPMbLlzLiajZXpSVC4rIjyUwQ9FM7zr7WxLTqHtsAQmLNuld5iK5FIKdLmie2tHMfO5ptQuW5Tff7WWXh8t53DKGa/LEpFLKNAlU6KK5ueTHg34U9tbmLcxmdZDEvhxw0GvyxKRdBTokmlBQUbPppWY3LcJxQvm48n3l/HnbzQejEhuoUCXq3bLjRFM7tuEHrEV+XjxLtoNm8+q3XqBhojXFOhyTcJDg/lzuxp82qMBp8+d54FRCxkyexPn1L1RxDMKdLkujSuXYMZzTWlfO4ohszfTafQitiWneF2WSJ6kQJfrViR/WvfGEQ/XYefhk7QdlsCHi3aoe6NIDlOgS5a5p9aNfPdcUxpULM5fJ/9Mt/eWavRGkRykQJcsVSoinPefrMff77uVxB1HaT0knimr93pdlkieoECXLGdmPNawPNP7x1EpsiD9PltJ309XcOzUWa9LEwloCnTJNhVLFOTLpxrxUutqfPfzfu4aHM+PG/Uwkkh2UaBLtgoJDqJPi8p806cJNxTIx5Pjl/HKpLWc1FjrIllOgS45omZUEaY8+/8vp757aDxLtx/xuiyRgKJAlxwTFhLMK21u4YunGmEYD41ZxD+/Xcfpc+e9Lk0kICjQJcfVq1CMGf3jeLj+TYxN2E674fNZk6ShA0SulwJdPFEwLIR/dryND35Xn5TTqXQcuZBBszZxNlVDB4hcKwW6eKpZ1Ui+e74pHaKjGDZnMx1HLmDD/hNelyXilxTo4rki+UMZ1Dmadx+ry4ETp7l3+HxG/LhF7zEVuUoKdMk1WtcszXfPNeWuGqV567uNdBq9iC0HNdCXSGYp0CVXKV4ojBGP1GF419vZcfgk9wxLYFzCNs5f0EBfIleiQJdc6d7aUXz/fFPiqkTyj2/X89C7i9h+6KTXZYnkagp0ybVKFg5nbLe6DOpcm00HfqHN0HjGL9jOBV2ti2RIgS65mplxf52yfP98MxpVKs6rU9fRZexidh0+5XVpIrmOAl38Quki4bz3RD3e7FSL9XtP0HpIPB8s3KGrdZF0FOjiN8yMzjHl+H5AU+pXLMbfpvxMV12ti/wfBbr4nRuL5Of9J+vx5gO1WOe7Wn9fbesiCnTxT2ZG53rl+O75tKv1//K1re88rJ4wkncp0MWvRRX1Xa13qsX6fWlX6+/N19W65E0KdPF7F9vWZ/l6wrw2bR2d313EtmQ9ZSp5iwJdAsbFnjBvP3ix33oC787bqqdMJc/IVKCbWVEzm2hmG8xsvZk1umR5czM7bmarfJ+/Zk+5Ir/NzHigbllmD2hG06qR/PeMDdw/aiGbD/zidWki2S6zV+hDgZnOuepAbWB9BuskOOeifZ/XsqxCkWtQMiKcMY/VZVjX29l1+CT3DJvPOz9s5pxGcJQAdsVAN7MiQFPgXwDOubPOOb1eRnI9M6N97ShmDWhGq5qlGPj9Jjq8s4Cf9x73ujSRbJGZK/SKQDIw3sxWmtk4MyuYwXqNzGy1mc0ws5oZbcjMeplZopklJicnX0/dIplWolAYIx6uw+hH63LwlzO0f2cBA7/byJlUvctUAos599s3jMwsBlgMNHHOLTGzocAJ59xf0q0TAVxwzqWYWVtgqHOuym9tNyYmxiUmJl7/EYhchWOnzvLatHVMWrGHyiUL8cYDtahb/gavyxLJNDNb7pyLyWhZZq7Qk4Ak59wS3/REoE76FZxzJ5xzKb7v04FQMytxHTWLZIuiBfIxqHM045+sx6kzqXQavZBXp/7MqbOpXpcmct2uGOjOuf3AbjOr5pt1J7Au/TpmVtrMzPe9vm+7h7O4VpEs06JaSb4f0IxHG5Rn/IId3DU4nvmbD3ldlsh1yWwvl2eBT8xsDRANvG5mvc2st295J+AnM1sNDAO6uCu15Yh4rFBYCH+/71Ym9GpIaHAQj/5rCS9PXM3xU+e8Lk3kmlyxDT27qA1dcpPT584zZPZmxiZso1jBfPy9Q03uvvVGr8sS+Q/X24YuEvDCQ4P5Q5vqTO7ThMhCYfT+eAW9P1rOwROnvS5NJNMU6CLp3FqmCJP7NuHlu6vxw8aDtBw0jwnLdqEWRPEHCnSRS4QGB/FM88rM7B9H9Rsj+P1Xa3l47BJ26CXVkssp0EUuo1JkIT7v2ZB/dryVn/Ycp/WQeEbN3Uqqhg+QXEqBLvIbgoKMRxqUZ9aAZjSrGskbMzfQ/p0FrE3S8AGS+yjQRTKhdJFwxnSLYdQjdUhOOUOHEfP557fr9ECS5CoKdJGr0Oa2G5k9oBkP1buJsQnbaT0knvhNGpdIcgcFushVKpI/lP++/7a0B5KCguj23lKen7CKwylnvC5N8jgFusg1alCpONP7x9HvjspMW7OXloPmMXF5kro4imcU6CLXITw0mAF3VePbfnFUiizEi1+u5pFxS9iuLo7iAQW6SBaoWqowXz7ViH/cdytrk9K6OL7zw2bOpqqLo+QcBbpIFgkKMh5tWJ7ZLzSj5S0lGfj9JtoNT2D5ziNelyZ5hAJdJIuVighn5CN1+dfjMaScTuWBUYv409drOf6rRnGU7KVAF8kmd95SilkDmtE9tiKfLd1Fy0HzmLZmr26aSrZRoItko4JhIfylXQ2m9I2ldEQ4fT9dyRPjl7H7yCmvS5MApEAXyQG3linCN32a8Nd2NUjccYRWg+cxcu4WzmlcGMlCCnSRHBIcZPwutiKzX0gbF+bNmRu5Z1gCiTt001SyhgJdJIfdWCQ/7z4Ww7huMZw8c55Ooxfxh6/WcOzUWa9LEz+nQBfxSMsapfj++ab0jKvIl8uTuOPteXylJ03lOijQRTxUMCyEP91Tg6l9YylfvAAvfLmarmMXs+VgiteliR9SoIvkAjWiIviqd2Ne73gb6/aeoM3QeAZ+t5HT5857XZr4EQW6SC4RFGQ83OAmfnixOffWjuKdH7fQavA8ftxw0OvSxE8o0EVymRKFwhjUOZrPejYkX3AQT76/jN4fLWfvsV+9Lk1yOQW6SC7V6ObizOjflJdaV2PupoO0HDSPMfFb1XddLkuBLpKL5QsJok+Lysx6vhmNby7O69M3cM+wBJZuV991+U8KdBE/UK5YAcY9Xo+xvr7rnd9dxIAvVnFIb0mSdBToIn6kVY1SzB7QjGea38zU1Xu5Y+BcPlq0g/MX1HddFOgifid/vmBevrs6M/o35dYyRfjL5J+5b8QCVu0+5nVp4jEFuoifqlyyEJ/0aMCwrrdz4MRpOo5cwCuT1nD0pIYQyKsU6CJ+zMxoXzuKOS80o3uTinyRmESLt+fy2dJdXFAzTJ6TqUA3s6JmNtHMNpjZejNrdMlyM7NhZrbFzNaYWZ3sKVdEMlI4PJQ/t6vBt/1iqVqqMK9MWkvHUQtZk6RmmLwks1foQ4GZzrnqQG1g/SXL2wBVfJ9ewKgsq1BEMq166Qgm9GrIkIei2XvsVzqMWMAfv16rZpg84oqBbmZFgKbAvwCcc2edc5f+b78D8KFLsxgoamY3Znm1InJFZsZ9t5dhzgvN+F2TikxYtpsWb8/l0yW71BsmwGXmCr0ikAyMN7OVZjbOzApesk4ZYHe66STfvH9jZr3MLNHMEpOTk6+5aBG5sojwUP6Srhnmj1+vpePIBazcddTr0iSbZCbQQ4A6wCjn3O3ASeAP17Iz59wY51yMcy4mMjLyWjYhIlfpYjPM0C7R7D9+mo4jF/L7iWs4rIeSAk5mAj0JSHLOLfFNTyQt4NPbA5RLN13WN09EcgEzo0N0GX54sTlPNa3EVyuSaDFwLh8s3EGqxoYJGFcMdOfcfmC3mVXzzboTWHfJalOAbr7eLg2B4865fVlbqohcr0JhIbzS9hZmPhdHrbJF+duUn2k3fD6Ltx32ujTJApnt5fIs8ImZrQGigdfNrLeZ9fYtnw5sA7YAY4FnsrxSEckylUsW5qPu9Rn1SB1+OZ1KlzGLefazlew7riF6/Zl59f7CmJgYl5iY6Mm+ReT//Xr2PKPmbWX0vK2EBBl9WlSmR1xFwkKCvS5NMmBmy51zMRkt05OiInlc/nzBDGhVlTkDmhFXpQRvfbeRuwbHM2f9Ab2w2s8o0EUESBui993HYvioe31Cg4Po/kEiT4xfxtZkvbDaXyjQReTfxFWJZEb/OP58zy2s2HmU1oPjeX36en45fc7r0uQKFOgi8h9Cg4PoEVeJH15szgN1yjI2YRstBs7ji8TdGvQrF1Ogi8hlRRYO441OtZjcpwk3FcvPyxPXcN/IBSzfqadNcyMFuohcUa2yRfnq6cYMeSiaAydO88CohTw/YRX7j5/2ujRJR4EuIplycdCvH15oTt8Wlfl27T7ueHsu7/ywmdPnzntdnqBAF5GrVDAshBdbV2POgGY0rRLJwO830XLQPKav3adujh5ToIvINSlXrACjH6vLpz0bUCgshGc+WUGXMYv5ac9xr0vLsxToInJdGt9cgmnPxvKP+25l88EU7n1nPn/4ag3Jv2g0x5ymQBeR6xYSHMSjDcvz44vN6d6kIhOXp43mOHreVs6kqn09pyjQRSTLFMmf9m7T759vSsNKxfifGRtoNSiemT+pfT0nKNBFJMtViizEuMfr8VH3+oSHBtH7Y7Wv5wQFuohkm7gqkUzvF8ff07Wvv/Tlag6eUP/17KBAF5FsFRIcxGO+9vWecZX4ZtUemg+cy/A56r+e1RToIpIjiuQP5Y9tb2G2r//627M2ccfAuXyzco/Gh8kiCnQRyVHlixdk9GN1+bxXQ4oVysdzE1bRcdRCEncc8bo0v6dAFxFPNKxUnCl9Yhn4YG32H/+VTqMX8cwny9l1+JTXpfmtEK8LEJG8KyjI6FS3LG1vK82Y+G28O28bs9cd5PHG5enbogpFCoR6XaJf0RW6iHiuQL4QnmtZlbkvNee+26MYN387zQb+yPgF2zmbesHr8vyGAl1Eco1SEeG82ak2056NpWZUBK9OXcddg+fpwaRMUqCLSK5TM6oIH3dvwPgn6hEanPZgUud3F7Fq9zGvS8vVFOgikiuZGS2ql2RG/zhe73gb2w+d5L4RC+j76Qp2H9GN04yYV7/GxMTEuMTERE/2LSL+J+VMKu/O28rYhG1cuADdGpWn7x2VKVogn9el5SgzW+6ci8lwmQJdRPzJ/uOnGTRrI18uTyIiPJS+LSrTrXF5wkKCvS4tR/xWoKvJRUT8SukiaTdOZ/SPI7pcUf45fT13vj2Pyav0xKkCXUT8UvXSEXzwu/p83L0BEeGh9P98Fe1HzGfhlkNel+YZBbqI+LXYKmlvTBr8UG2OnjzHw+OW8MT4pWzYf8Lr0nKcAl1E/F5QkNHx9rLMeaEZr7SpzoqdR2kzNIEXvljN3mO/el1ejtFNUREJOMdOnWXk3K28v2AHGDzZuALPNK8cEEMJXHcvFzPbAfwCnAdSL92YmTUHJgPbfbMmOede+61tKtBFJLslHT3FoFmb+HrlHiLCQ+nT4ma6NapAeKj/9ojJqkCPcc5leLfBF+gvOufaZbYoBbqI5JR1e0/wxswNzNuUTFSRcJ5vVZX765QlOMi8Lu2qqduiiORpNaLSesR82rMBkYXDeGniGtoMjWfO+gMBNUZMZgPdAd+b2XIz63WZdRqZ2Wozm2FmNTNawcx6mVmimSUmJydfU8EiIteq8c0l+KZPE0Y8XIdz5x3dP0ik87uLWL4zMF6ukdkmlzLOuT1mVhKYBTzrnItPtzwCuOCcSzGztsBQ51yV39qmmlxExEvnzl9gwrLdDJm9mUMpZ2h5SylevrsaVUsV9rq033TdTS7OuT2+nweBr4H6lyw/4ZxL8X2fDoSaWYnrqlpEJBuFBgfxaMPyxL/cnJdaV2PJtsO0HhLPC1+sJumofw7+dcVAN7OCZlb44nfgLuCnS9YpbWbm+17ft93DWV+uiEjWKpAvhD4tKhP/cgt6xFZk6pq93DFwHq9NXcfhlDNel3dVMvMKulLA1768DgE+dc7NNLPeAM650UAn4GkzSwV+Bbq4QLrTICIB74aC+fjTPTV4sklFhs7ezPsLtzNh2S56xFWiR1xFCofn/j7serBIRCQDWw6m8Pb3G5nx035uKBBKnxaVebRhec/7sGv4XBGRa7Qm6RhvztzI/C2HiCoSTv+WVXigTllCgr3p9a1+6CIi16hW2aJ83KMBn/ZoQGREOL//ai13DY5n2pq9uW64XgW6iEgmNK5cgm+eacyYx+oSEmz0/XQl7YbP58cNB3PNw0kKdBGRTDIz7qpZmhn9mzL4odqknEnlyfeX8eDoRSze5n3HPrWhi4hco4sPJw3/YTMHTpwhrkoJXryrGrXLFc22feqmqIhINjp97jwfLdrJyLlbOHrqHK1qlOKFu6pSvXRElu9LgS4ikgNSzqTy3vztjI3fRsrZVO6tFcVzLatQKbJQlu1DgS4ikoOOnTrLmPhtjF+wgzOp53mgTln63VmFcsUKXPe2FegiIh44lHKGUXO38tHinTjneKheOfq2qELpIuHXvE0FuoiIh/Yd/5URP25hwrLdmBkvt65Gj7hK17QtPVgkIuKhG4vk5x/33cYPLzTnvugoyt5w/U0vGcnM4FwiIpIFyhUrwJudamfb9nWFLiISIBToIiIBQoEuIhIgFOgiIgFCgS4iEiAU6CIiAUKBLiISIBToIiIBwrNH/80sGdh5jX+8BHAoC8vxF3nxuPPiMUPePO68eMxw9cdd3jkXmdECzwL9ephZ4uXGMghkefG48+IxQ9487rx4zJC1x60mFxGRAKFAFxEJEP4a6GO8LsAjefG48+IxQ9487rx4zJCFx+2XbegiIvKf/PUKXURELqFAFxEJEH4X6GZ2t5ltNLMtZvYHr+vJDmZWzsx+NLN1ZvazmfX3zS9mZrPMbLPv5w1e15odzCzYzFaa2TTfdEUzW+I75xPMLJ/XNWYlMytqZhPNbIOZrTezRnnhXJvZ875/3z+Z2WdmFh6I59rM3jOzg2b2U7p5GZ5fSzPMd/xrzKzO1ezLrwLdzIKBEUAboAbQ1cxqeFtVtkgFXnDO1QAaAn18x/kHYI5zrgowxzcdiPoD69NNvwEMds5VBo4C3T2pKvsMBWY656oDtUk79oA+12ZWBugHxDjnbgWCgS4E5rl+H7j7knmXO79tgCq+Ty9g1NXsyK8CHagPbHHObXPOnQU+Bzp4XFOWc87tc86t8H3/hbT/wMuQdqwf+Fb7ALjPmwqzj5mVBe4BxvmmDbgDmOhbJaCO28yKAE2BfwE45846546RB841aa/AzG9mIUABYB8BeK6dc/HAkUtmX+78dgA+dGkWA0XN7MbM7svfAr0MsDvddJJvXocHZWIAAAIRSURBVMAyswrA7cASoJRzbp9v0X6glEdlZachwMvABd90ceCYcy7VNx1o57wikAyM9zUzjTOzggT4uXbO7QEGArtIC/LjwHIC+1ynd7nze10Z52+BnqeYWSHgK+A559yJ9MtcWn/TgOpzambtgIPOueVe15KDQoA6wCjn3O3ASS5pXgnQc30DaVejFYEooCD/2SyRJ2Tl+fW3QN8DlEs3XdY3L+CYWShpYf6Jc26Sb/aBi79++X4e9Kq+bNIEaG9mO0hrTruDtPblor5fyyHwznkSkOScW+KbnkhawAf6uW4JbHfOJTvnzgGTSDv/gXyu07vc+b2ujPO3QF8GVPHdCc9H2k2UKR7XlOV87cb/AtY75walWzQFeNz3/XFgck7Xlp2cc68458o65yqQdm5/cM49AvwIdPKtFlDH7ZzbD+w2s2q+WXcC6wjwc01aU0tDMyvg+/d+8bgD9lxf4nLndwrQzdfbpSFwPF3TzJU55/zqA7QFNgFbgT95XU82HWMsab+CrQFW+T5tSWtPngNsBmYDxbyuNRv/DpoD03zfKwFLgS3Al0CY1/Vl8bFGA4m+8/0NcENeONfAq8AG4CfgIyAsEM818Blp9wnOkfYbWffLnV/ASOvJtxVYS1ovoEzvS4/+i4gECH9rchERkctQoIuIBAgFuohIgFCgi4gECAW6iEiAUKCLiAQIBbqISID4X33RlO19YRV0AAAAAElFTkSuQmCC\n","text/plain":["<Figure size 432x288 with 1 Axes>"]},"metadata":{"needs_background":"light"}}]},{"cell_type":"code","metadata":{"id":"EnNn5u0xbFcF"},"source":["emb_length, lr, bs = 10, 1e-4, 100\n","leaves = [Vertex(emb_length, lr, bs) for i in range(100)]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"6EKibUn-bFcF"},"source":["leaves = [Leaf(v) for v in leaves]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"flNh5_jRbFcF"},"source":["tree = Tree.build_tree(leaves, emb_length, lr, bs)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"gma5jbSzbFcF"},"source":["chosen_leaf = leaves[20]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Pam4uPUBbFcG","colab":{"base_uri":"https://localhost:8080/","height":72},"executionInfo":{"status":"ok","timestamp":1633185274998,"user_tz":-330,"elapsed":23762,"user":{"displayName":"Sparsh Agarwal","photoUrl":"https://lh3.googleusercontent.com/a/default-user=s64","userId":"13037694610922482904"}},"outputId":"b97035cc-c4a5-4416-9915-911b8e5741ea"},"source":["#slow\n","costs = []\n","num_iter = 3000\n","epoch_costs = [] \n","for it in range(num_iter):\n","    for i in range(100):\n","        if i == 20:\n","            continue\n","        costs.append(leaves[i].update(chosen_leaf.vertex)) \n","    epoch_costs.append(np.mean(costs))\n","    costs = []\n","s = pd.Series(epoch_costs)\n","s.plot(kind='line')"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["<matplotlib.axes._subplots.AxesSubplot at 0x7fc68b6a80d0>"]},"metadata":{},"execution_count":38},{"output_type":"display_data","data":{"image/png":"iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAfo0lEQVR4nO3dd3RVVaLH8e9OJxAgQOiEXgWkRAgQEGkKiAUsoGBBQRSk6PieM773xjczzpsZHVEBKWIBKVIUUFAREYEIAQKE3nvvPRCSsN8fuTjIUG4gN+fcm99nrazc3HvJ+m1O+HGyz9nnGGstIiLiXkFOBxARkRtTUYuIuJyKWkTE5VTUIiIup6IWEXG5EF9802LFitkKFSr44luLiASk5cuXH7XWxlzrNZ8UdYUKFUhOTvbFtxYRCUjGmF3Xe01THyIiLqeiFhFxORW1iIjLqahFRFxORS0i4nIqahERl1NRi4i4nKuKesjcLazdd8rpGCIiruKaoj6ZepEJS3fz6IjFfL/2gNNxRERcwzVFXTgyjBn9mlG9ZBR9xq1g6E9b0E0NRERcVNQAxaMi+KJ3PA/VK807P2xmwBcpXEjPdDqWiIijfHKtj9sRERrM4MfrUbVEFO/8sIkdR88x6qmGlCqUz+loIiKOcNUe9WXGGPreU4WPesSx/chZHhj6Cyt2n3A6loiII1xZ1Je1qVWCaX2bkS80mK4jk5iSvMfpSCIiuc7VRQ1QrUQUM/o2I65CNK9NXc2fZ64nI/OS07FERHKN64saIDp/GGN7NuKZphX4OHEHz362jFOp6U7HEhHJFX5R1AAhwUG8+cAd/L1LHZK2H+PBYYlsPXzG6VgiIj7nN0V92eN3xTKxVzxn0zJ4aNgiftp4yOlIIiI+5XdFDRBXoQgz+iVQvmgkz41JZvjP27Q4RkQCll8WNUCZwvmY2qcpHeuU4u/fb2TgJC2OEZHA5LoFL9mRLyyYId3qU7NUQd6enbU4ZmQPLY4RkcDit3vUl/26OOapOLYd1uIYEQk8fl/Ul7XV4hgRCVABU9SgxTEiEpgCqqhBi2NEJPB4VdTGmAHGmLXGmHXGmIG+DnW7rl4c89CHv2hxjIj4rZsWtTGmNtALaATcCdxvjKni62A54fLimDMX0nl42CLmbTzsdCQRkWzzZo+6JrDEWptqrc0A5gOdfRsr51xeHBNbNJKeY5ZpcYyI+B1vinot0NwYU9QYEwl0AMpd/SZjTG9jTLIxJvnIkSM5nfO2XF4c00GLY0TED920qK21G4C/Az8A3wMpwL+1nLV2lLU2zlobFxMTk+NBb1e+sGCGdqvPa/dWZ0bKfh4buZgDp847HUtE5Ka8Ophorf3YWtvQWtsCOAFs9m0s39DiGBHxR96e9VHc8zmWrPnpCb4M5WtXL46Zunyv05FERK7L2/OovzTGrAe+Afpaa0/6MFOuuHJxzO+mrOIvWhwjIi7l1UWZrLXNfR3ECdH5wxjTsxFvzdrA6MQdbDp0hqHdGlAoMtTpaCIivwq4lYnZFepZHPO3zlocIyLulOeL+rKujWKZoMUxIuJCKuor3KXFMSLiQirqq2hxjIi4jV/f4cVXLi+OqXXFnWNG9YijZKEIp6OJSB6kPerruHpxTKehiVocIyKOUFHfhBbHiIjTVNRe0OIYEXGSitpLlxfHPNO0AqN15xgRyUUq6my4enFMp6GJrN9/2ulYIhLgVNS3oGujWL7o3YS0jEw6D/+FaSs1by0ivqOivkUNy0cz8+Xm3Fm2MIMmreKPM9ZyMUPz1iKS81TUtyEmKpxxzzfm+YSKjFm8i24fJXHo9AWnY4lIgFFR36bQ4CD+6/5aDOlWnw0HTnP/kESW7jjudCwRCSAq6hzS6c7STO/bjALhITzxURKfJO7QdUJEJEeoqHNQtRJRzOjXjHtqFOdPM9czcFIKqRcznI4lIn5ORZ3DCkaEMrJ7Q167tzpfr9pP5w8XsfPoOadjiYgfU1H7QFBQ1nVCxjzbiIOnL9BpaCJzNxxyOpaI+CkVtQ+1qBbDN/0SKF80kufGJPPuD5vIvKR5axHJHhW1j5UrEsnUPk15tGFZPvhpKz0/W8bJ1ItOxxIRP6KizgURocH845G6vPVwbRZtO0qnoYms3XfK6Vgi4idU1LnEGMOTjcsz+YUmpGdYugxfxJe6ZKqIeEFFncvqx0Yzs38C9WML8+qUVfz3dC09F5EbU1E7oFiBcMY915jeLSrxedIuuo5azMFTWnouItemonZISHAQf+hQk2FPNGDjwTPcP2QhSduPOR1LRFxIRe2wjnVLMaNvMwpGhPLk6CWMXrhdS89F5DdU1C5Q1bP0vE3N4vxl1gZenriSc2laei4iWVTULhEVEcqI7g35j/uq8+2aAzz84S/s0NJzEUFF7SrGGF5qWYWxPRtz5EwaDwxJZM56LT0XyetU1C6UULUYM/s3p2JMfnqNTead2Vp6LpKXeVXUxphBxph1xpi1xpiJxpgIXwfL68oUzsfkF5rQ9a5yDJ23lWc/W8aJc1p6LpIX3bSojTFlgP5AnLW2NhAMdPV1MMlaev63LnX5v851SNp2TEvPRfIob6c+QoB8xpgQIBLY77tIcrVujWKZ3KcJly5lLT2fkrzH6UgikotuWtTW2n3AO8Bu4ABwylr7w9XvM8b0NsYkG2OSjxw5kvNJ87h65QrzzcsJNCwfzWtTV/PGtDWkZWQ6HUtEcoE3Ux/RwINARaA0kN8Y0/3q91lrR1lr46y1cTExMTmfVChaIJyxPRvxwt2VGL9kN4+PTOLAqfNOxxIRH/Nm6qMNsMNae8Ramw58BTT1bSy5npDgIH7fvibDn2zAlkNnuP+DRBZu0W8wIoHMm6LeDcQbYyKNMQZoDWzwbSy5mfZ1SjGjXwJFC4Tx1CdLGTxns07hEwlQ3sxRLwGmAiuANZ4/M8rHucQLVYoXYHrfZnSuX5b3527hqU+WcORMmtOxRCSHGV9cACguLs4mJyfn+PeV65ucvIf/nr6WgvlCGdKtPvGVijodSUSywRiz3Fobd63XtDIxQDwWV44Z/ZoRFRHCEx8lMWzeVi5pKkQkIKioA0iNkgX5ul8CHeuW5u3Zm3j2s2Uc12pGEb+nog4wBcJD+KBrPf7yUG0WbztGxw8WsnzXcadjichtUFEHIGMM3ePL89VLTQkNDuLxkUmMWrBNNyQQ8VMq6gBWu0whZvZPoE3NEvz12430GrucU6npTscSkWxSUQe4ghGhDO/egD92qsX8zYfpOGQhq/acdDqWiGSDijoPMMbwbLOKTH6hCdbCIyMW8dkvOzQVIuInVNR5SP3YaGb1T6BF1Rje/GY9fSes4PQFTYWIuJ2KOo8pHBnGR0/F8fv2NZi97hCdhuga1yJup6LOg4KCDC/cXZkveseTln6JzsMXMX7JLk2FiLiUijoPu6tCEWb1T6BxxSK8MW0tAyelcC4tw+lYInIVFXUeV7RAOGOebcSrbavxzar9PDA0kU0HzzgdS0SuoKIWgoIML7euyrjnG3PqfAYPDktksm73JeIaKmr5VdPKxfh2QAL1yhXmP6auZtCkFM5qKkTEcSpq+Y3iURGMfz6egW2qMiNlHx0/WMjqvVogI+IkFbX8m+Agw8A21fiidxPSMy7R+cNFjFqwTZdNFXGIilquq1HFInw7oDmtaxbnr99u5OlPl3L4zAWnY4nkOSpquaHCkWGM6N6QvzxUm6U7jtPh/YXM36yb6YrkJhW13NTly6Z+3S+BIvnDePqTpfz12w1czLjkdDSRPEFFLV6rXjKKr/sl0D0+llELttNl+CJ2Hj3ndCyRgKeilmyJCA3mLw/VYUT3huw+nkrHDxYybeVep2OJBDQVtdyS+2qX5NsBzbmjdCEGTVrFKzrnWsRnVNRyy8oUzseEXo0Z2KYq01P2cb/OuRbxCRW13JaQ4KBfz7lOy7hEl+GL+GjBdp1zLZKDVNSSIxpVLMJ3A5rTqkZx3vp2A898towjZ9KcjiUSEFTUkmOuPOd6yfZjtH9/gc65FskBKmrJUTrnWiTnqajFJ6qXjGJG3wSebJx1zvUjI3TOtcitUlGLz+QLC+ath+swonsDdh49R8cPFjJ95T6nY4n4HRW1+Nx9tUvx3cAW1CpdkIGTUnhlss65FsmOmxa1Maa6MSblio/TxpiBuRFOAkeZwvmY2CueAa2rMn1l1jnXa/bq7uci3rhpUVtrN1lr61lr6wENgVRgms+TScAJCQ5iUNtqTOwVT1rGJToP/0XnXIt4IbtTH62BbdbaXb4II3lD40pFf3PO9bM651rkhrJb1F2Bidd6wRjT2xiTbIxJPnJE587KjV0+5/rPD9Vm8fZjtH9/IfM2HnY6logrGWu9+7XTGBMG7AfusNYeutF74+LibHJycg7Ek7xg48HTDJiYwqZDZ3iycSxvdKxJZFiI07FEcpUxZrm1Nu5ar2Vnj7o9sOJmJS2SXTVKFmRGv2b0blGJCUt30/GDRFbuPuF0LBHXyE5Rd+M60x4itysiNJg/dKjJhOfjuZhxiUdGLGbwnM2kZ2pFo4hXRW2MyQ+0Bb7ybRzJ65pULsp3A5vz4J2leX/uFh4ZvohtR846HUvEUV4VtbX2nLW2qLVWJ76KzxWMCOXdx+sx7IkG7PLcRebzxTvx9niKSKDRykRxrY51SzF7YAvuqlCE/56xjmc+Xcbh0xecjiWS61TU4molCkYwtmcj/vTgHSzZcYx731vAd2sOOB1LJFepqMX1jDE81aQCM19uTrkikbw4fgWvTE7h9IV0p6OJ5AoVtfiNKsUL8OWLTenfqgrTV+6j/XsLSdp+zOlYIj6noha/EhocxCvtqjP1xaaEBhu6fZTE/327gbSMTKejifiMilr8UoPYaGb1b063RrGMXLCdB4f+wsaDp52OJeITKmrxW/nDQ/jrw3X45Jk4jp69yANDdDU+CUwqavF7rWqUYPbA5rSsHsNb327gidFJ7D2R6nQskRyjopaAULRAOCN7NOQfj9Rlzd5TtH9vIV+t2KtFMhIQVNQSMIwxPBZXju8HtqBGqShembyKF8et4OhZXeta/JuKWgJOuSKRfNG7Cf95Xw1+2niYdoMXMGu1FsmI/1JRS0AKDjK82LIyM/snUDY6H30nrKDv+BUc0961+CEVtQS0aiWi+OrFprx2b3V+WH+QdoO1BF38j4paAl5IcBB976nCzJebU7pwPl4cv4J+E1Zw/NxFp6OJeEVFLXlG9ZJRfPVSU15tW43Z6w7SbvB8vl970OlYIjelopY8JTQ4iJdbV+XrfgmUKBhBn3HLGfDFSk5o71pcTEUteVLNUgWZ3rcZg9pUY9bqA7QdvIAf1mnvWtxJRS15VmhwEAPaZO1dF48Kp/fnyxk0KYWTqdq7FndRUUueV6t01t71gNZV+WbVftoNXsDcDYecjiXyKxW1CBAWEsSgttWY3rcZRfKH8dyYZF6ZnMKpVN2cQJynoha5Qu0yhfi6XwL9W1VhRsp+2g6ez2zNXYvDVNQiVwkLybo5wYy+zShWIJwXPl9O3wm6Zog4R0Utch21yxRiRr9mvHZvdeasO0Sbd+czbaWuyCe5T0UtcgOhnlWN3w5IoFKx/AyatIqeny1j/8nzTkeTPERFLeKFKsWjmNKnKf9zfy2Sth+n3eAFjEvapbvJSK5QUYt4KTjI0DOhIj8MasGd5QrxX9PX0u2jJHYcPed0NAlwKmqRbCpXJJJxzzXm713qsP7Aae59bwHD5m0lPfOS09EkQKmoRW6BMYbH74pl7it306p6cd6evYlOQxJZufuE09EkAKmoRW5D8YIRjOjRkJE9GnIyNZ3Owxfx5tfrOJuW4XQ0CSBeFbUxprAxZqoxZqMxZoMxpomvg4n4k3vvKMmcV1rQI748YxbvpO278/lxvZahS87wdo/6feB7a20N4E5gg+8iifinqIhQ/vRgbab2aUpURAjPj03mpfHLOXz6gtPRxM/dtKiNMYWAFsDHANbai9bak74OJuKvGpaPZubLzfldu2r8uOEwrd+dz/glOpVPbp03e9QVgSPAp8aYlcaY0caY/D7OJeLXwkKC6NeqKt8PaM4dpQvyxrS1PDZyMVsOnXE6mvghb4o6BGgADLfW1gfOAa9f/SZjTG9jTLIxJvnIkSM5HFPEP1WKKcDEXvH845G6bDl8lg4fLOSd2Zu4kJ7pdDTxI94U9V5gr7V2iefrqWQV929Ya0dZa+OstXExMTE5mVHErxljeCyuHHNfvZtOdUszdN5W7n1vAT9vOux0NPETNy1qa+1BYI8xprrnqdbAep+mEglAxQqE8+7j9ZjwfGOCgwzPfLqMPp8v13VD5KaMN1cCM8bUA0YDYcB24Flr7XXP7I+Li7PJyck5FlIk0KRlZDJ64Q6G/LSFIGMY0LoqPRMqEhqspQ15lTFmubU27pqv+eKSjSpqEe/sOZ7K/36znh83HKJq8QL8+aHaxFcq6nQsccCNilr/fYs4qFyRSEY/Hcfop+I4n55J11FJDJqUwuEzOvda/kVFLeICbWqVYM6gu3m5VRVmrT5A63fm89kvO8jQhZ4EFbWIa+QLC+bVdtX5fmBz6sUW5s1v1vPA0F9YoQs95XkqahGXqRRTgLE9GzHsiQYcO5dG5w8X8fqXqzlx7qLT0cQhKmoRFzLG0LFuKea+2pJezSsyZfleWv3zZ75YultL0fMgFbWIixUID+GNjrWY1T+BKsUL8PpXa+gyYhHr9p9yOprkIhW1iB+oUbIgk19owj8fvZPdx1LpNCSRP85Yy8lUTYfkBSpqET9hjKFLw7L89GpLnmxcns+TdtHynZ8Zs2inzg4JcCpqET9TKDKUPz9Um1n9m1OzZEH++PU62r+/kIVbdDG0QKWiFvFTNUsVZEKvxozo3pC0jEv0+Hgpz49ZpruiByAVtYgfM8ZwX+2s24D95301WLztGO0Gz+etWes5fSHd6XiSQ1TUIgEgPCSYF1tWZt5rLXm4fhlGJ+7gnrd/ZuLS3WTqdD6/p6IWCSDFoyL4xyN38nXfBCoWy8/vv1pDpyGJLNl+zOlochtU1CIBqE7ZQkzp04Qh3epzMvUij49K4qXxy9lzPNXpaHILVNQiAcoYQ6c7SzP31ZYMalONnzZm3Wj3ndmbOJeW4XQ8yQYVtUiAyxcWzIA2VZn3u5Z0qF2SofO20uqfP/PVir1aju4nVNQieUSpQvl4r2t9vnyxKSULRvDK5FU8/OEvmr/2AypqkTymYflopr3UjH8+eieHTqfx+Kgknh+TzNbDZ5yOJtehW3GJ5GEX0jP5OHEHw3/exvn0TB6/qxwD21SleFSE09HyHN0zUURu6NjZNIb8tJVxSbsICwmid4tK9GpeifzhIU5HyzNU1CLilZ1Hz/H27E3MWnOAmKhwBrWpxmNxZQnR3dF9Tje3FRGvVCiWn2FPNuCrl5pSoWgkf5i2hnvfW8Cc9YfwxU6deEdFLSL/pkFsNJNfaMKoHg2xQK+xyXQZvohF2446HS1PUlGLyDUZY2h3R0lmD2zBXx+uw4FTF3jioyU8OTqJlbrhbq7SHLWIeOVCeibjl+zmw3lbOXbuIm1qFueVttWpVbqg09ECgg4mikiOOZeWwWeLdjJy/jZOX8jg/rqlGNS2GpVjCjgdza+pqEUkx51KTeejhdv55JcdXEjPpEuDsgxoU5Wy0ZFOR/NLKmoR8ZmjZ9MY/vM2Pk/ahbWWJxrF0veeKhQvqEUz2aGiFhGfO3DqPB/M3cqU5D2EBBueblqBPi0qE50/zOlofkFFLSK5Ztexc7z34xamp+yjQFgIzzWvyHMJFYmKCHU6mqvddlEbY3YCZ4BMION63+wyFbWIbD50hnd/2Mz36w4SHRlKn7sr0z2+vJalX0dOFXWctdars91V1CJy2Zq9p3j7h00s2HyE6MhQnm9eiR5NylNQe9i/oSXkIuKYOmULMbZnI758sSn1yhXm7dmbSPjbT7w7ZzMnUy86Hc8veLtHvQM4AVhgpLV21I3erz1qEbmetftOMeSnLcxed4j8YcH0aFKB55tXpFiBcKejOSonpj7KWGv3GWOKA3OAl621C656T2+gN0BsbGzDXbt23X5yEQlYGw+eZti8bcxcvZ/wkCCeaFSeF+6uRIk8elpfjp71YYx5EzhrrX3neu/RHrWIeGvbkbMMm7eVGSn7CTaGx+4qS5+7K+e5hTO3VdTGmPxAkLX2jOfxHOBP1trvr/dnVNQikl27j6UyfP5Wpi7fi7XQuUEZXmpZhQrF8jsdLVfcblFXAqZ5vgwBJlhr37rRn1FRi8it2nfyPKPmb2Pisj1kZF6iQ51SvNCiMnXKFnI6mk9pwYuI+J3Dpy8wOnEHE5bs5mxaBvGVivBCi8q0rB6DMcbpeDlORS0ifuv0hXS+WLqbTxJ3cvD0BaqVKECv5pV4oF5pwkOCnY6XY1TUIuL3LmZcYubq/YxasJ2NB89QPCqcZ5tV5InGsRTK5/+LZ1TUIhIwrLUs3HKUUQu2k7j1KPnDgunaKJaeCRUpUzif0/FumYpaRALS2n2nGL1wO9+sPgBAp7ql6NWiEneU9r8DjypqEQlo+06e59PEHUxcuptzFzOJr1SEHvEVaHdHCUKD/eNKGSpqEckTTp1PZ+LS3YxL2sXeE+cpHhVOt0axdGsUS8lC7l7xqKIWkTwl85Jl/ubDfL54Fz9vPkKQMbSrVYIe8eVpUrmoK0/vu1FR68KwIhJwgoMMrWqUoFWNEuw+lsr4pbuYvGwP3609SOWY/HSPL0/nBmX95mwR7VGLSJ5wIT2TWasP8HnSLlL2nCRfaDAP1S9D9/hYVxx81NSHiMgV1uw9xbikXcxYtY8L6ZdoWD6aHvHlaV+npGOLaFTUIiLXcCo1nakr9jIuaRc7jp6jaP4wHrurHE80iqVckdy9ep+KWkTkBi5dsizadoyxi3fy44ZDWKBV9eL0aFKeFlVjCAry/cFHHUwUEbmBoCBDQtViJFQtxv6T55m4dDcTl+5h7qfLKFM4H10aluWRBmWJLerMNbK1Ry0icg0XMy4xe91BJifvIXHrUayFxhWL8GhcOdrXLpnjd1PX1IeIyG3Yf/I801buY0ryHnYeSyV/WDAd6pTi0bhy3FUhOkfOy1ZRi4jkAGsty3edYEryXmau3s+5i5mULxpJlwZlebh+mds6AKmiFhHJYakXM/h+7UGmJO9l8fZjQNbUyOfPNSYsJPvXF9HBRBGRHBYZFkLnBmXp3KAse0+kMiNlP3uOp95SSd+MilpE5DaVjY6k7z1VfPb9/eP6fyIieZiKWkTE5VTUIiIup6IWEXE5FbWIiMupqEVEXE5FLSLicipqERGX88kScmPMEWDXLf7xYsDRHIzjpEAZS6CMAzQWtwqUsdzOOMpba2Ou9YJPivp2GGOSr7fe3d8EylgCZRygsbhVoIzFV+PQ1IeIiMupqEVEXM6NRT3K6QA5KFDGEijjAI3FrQJlLD4Zh+vmqEVE5LfcuEctIiJXUFGLiLica4raGHOfMWaTMWarMeZ1p/N4wxiz0xizxhiTYoxJ9jxXxBgzxxizxfM52vO8McZ84BnfamNMA4ezf2KMOWyMWXvFc9nObox52vP+LcaYp100ljeNMfs82ybFGNPhitd+7xnLJmPMvVc87+jPoDGmnDFmnjFmvTFmnTFmgOd5v9suNxiLX20XY0yEMWapMWaVZxz/63m+ojFmiSfTJGNMmOf5cM/XWz2vV7jZ+LxirXX8AwgGtgGVgDBgFVDL6Vxe5N4JFLvquX8Ar3sevw783fO4A/AdYIB4YInD2VsADYC1t5odKAJs93yO9jyOdslY3gR+d4331vL8fIUDFT0/d8Fu+BkESgENPI+jgM2evH63XW4wFr/aLp6/2wKex6HAEs/f9WSgq+f5EcCLnscvASM8j7sCk240Pm9zuGWPuhGw1Vq73Vp7EfgCeNDhTLfqQWCM5/EY4KErnh9rsyQBhY0xpZwICGCtXQAcv+rp7Ga/F5hjrT1urT0BzAHu833637rOWK7nQeALa22atXYHsJWsnz/HfwattQestSs8j88AG4Ay+OF2ucFYrseV28Xzd3vW82Wo58MCrYCpnuev3iaXt9VUoLUxxnD98XnFLUVdBthzxdd7ufFGdQsL/GCMWW6M6e15roS19oDn8UGghOexP4wxu9ndPqZ+nimBTy5PF+AnY/H8ylyfrD04v94uV40F/Gy7GGOCjTEpwGGy/tPbBpy01mZcI9OveT2vnwKKcpvjcEtR+6sEa20DoD3Q1xjT4soXbdbvPH55/qM/Z/cYDlQG6gEHgH86G8d7xpgCwJfAQGvt6Stf87ftco2x+N12sdZmWmvrAWXJ2guukdsZ3FLU+4ByV3xd1vOcq1lr93k+HwamkbURD12e0vB8Pux5uz+MMbvZXTsma+0hzz+wS8BH/OvXTFePxRgTSlaxjbfWfuV52i+3y7XG4q/bBcBaexKYBzQha5op5BqZfs3reb0QcIzbHIdbinoZUNVzJDWMrEn4rx3OdEPGmPzGmKjLj4F2wFqycl8+yv40MMPz+GvgKc+R+njg1BW/zrpFdrPPBtoZY6I9v8K28zznuKvm/x8ma9tA1li6eo7OVwSqAktxwc+gZy7zY2CDtfbdK17yu+1yvbH423YxxsQYYwp7HucD2pI13z4PeMTztqu3yeVt9Qjwk+e3oOuNzzu5dfTUi6OrHcg6MrwNeMPpPF7krUTWUdxVwLrLmcmaj5oLbAF+BIrYfx09HuYZ3xogzuH8E8n61TOdrPmy524lO9CTrAMjW4FnXTSWzz1ZV3v+kZS64v1veMayCWjvlp9BIIGsaY3VQIrno4M/bpcbjMWvtgtQF1jpybsW+B/P85XIKtqtwBQg3PN8hOfrrZ7XK91sfN58aAm5iIjLuWXqQ0RErkNFLSLicipqERGXU1GLiLicilpExOVU1CIiLqeiFhFxuf8H9gmad2mX8dsAAAAASUVORK5CYII=\n","text/plain":["<Figure size 432x288 with 1 Axes>"]},"metadata":{"needs_background":"light"}}]},{"cell_type":"markdown","metadata":{"id":"AdYUmWzbbFcG"},"source":["This is an interesting result -- it seems a little unusual that we would see training loss going up, but some things to consider:\n","* In the \"real\" version, the leaf embeddings are (hopefully) going to have some relationship with the internal node model parameters. In this toy version, we've uniformly initialized all parameters and then trained the model on every single leaf for many iterations. It's basically learning how to optimize random noise.\n","* We're using plain vanilla batch GD here, with no learning rate annealing (or any of the wide number of GD enhancements that exist). It's very possible that we're getting gradient explosions / divergence towards the end here. "]},{"cell_type":"markdown","metadata":{"id":"4Zu0lhlHbFcG"},"source":["The goal of hierarchical softmax is to make the scoring function run in $O(logv)$ rather than $O(v)$ by organizing the nodes as a binary tree with a binary classifier at each internal node. At a high level, we follow these steps:\n","1. We identify a leaf that is contained within the window of our vertex within the current random walk\n","2. We take that leaf's parent and compute the probability of having followed the correct path (left or right) to the leaf we identified in step 1 by using the model parameters for this internal node combined with the features for the current vertex (which is a row in $\\Phi$).\n","3. We repeat step 2 for all internal nodes until we get to the root\n","4. The product of all of the internal probabilities gives us the probability of seeing a co-occurrence of the neighbor node given what we know about the node we're exploring\n","5. $-logPr(u_k|\\Phi(v_j))$ is our loss function, where $Pr(u_k|\\Phi(v_j))$ is the probability we calculated in step 4\n","6. We use the loss in step 5 to perform a gradient descent step updating both the parameters of our model and $\\Phi(v_j)$:\n","\n","$$\\theta \\leftarrow \\theta - \\alpha_\\theta * \\frac{\\partial J}{\\partial \\theta}$$\n","<br>\n","$$\\Phi \\leftarrow \\Phi - \\alpha_\\Phi * \\frac{\\partial J}{\\partial \\Phi}$$\n","\n","Where $\\theta$ represents all of the parameters of all of the models in the internal nodes of the tree, and $\\Phi$ represents the latent representation of the current vertex."]}]}