{ "cells": [ { "cell_type": "markdown", "source": [ "# [NTDS'18] milestone 4: graph signal processing\n", "[ntds'18]: https://github.com/mdeff/ntds_2018\n", "\n[Rodrigo Pena](https://people.epfl.ch/254838), [EPFL LTS2](http://lts2.epfl.ch)" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Students\n", "\n", "* Team: ``\n", "* Students: ``\n", "* Dataset: ``" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Rules\n", "\n", "* Milestones have to be completed by teams. No collaboration between teams is allowed.\n", "* Textual answers shall be short. Typically one to two sentences.\n", "* Code has to be clean.\n", "* You cannot import any other library than we imported.\n", "* When submitting, the notebook is executed and the results are stored. I.e., if you open the notebook again it should show numerical results and plots. We won't be able to execute your notebooks.\n", "* The notebook is re-executed from a blank state before submission. That is to be sure it is reproducible. You can click \"Kernel\" then \"Restart & Run All\" in Jupyter." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Objective\n", "\n", "The goal of this milestone is to do some Graph Signal Processing (GSP) on the data of your project.\n", "\n", "### A note about plotting\n", "\n", "There are several questions in this milestone that ask you to plot a signal on your network.\n", "There are several ways from which you could approach it.\n", "In all cases, compute the position of the nodes a single time at the beginning, as this is likely to be a costly operation.\n", "Using a single layout for all the graph plots will also make it easier to compare the plots.\n", "Indeed, the only thing changing between plots is the signal displayed.\n", "You can represent the features/labels lying on the graph via node **colors**.\n", "To do so, make sure to have a consistent color map throughout and remember to display a colorbar and scale in all plots, so that we can tell what numbers the colors represent.\n", "\n", "* An option is to use the **Laplacian eigenmaps** that you have seen in the previous milestone to embed your graph on the plane. For example:\n", " ```\n", " from matplotlib import pyplot as plt\n", " plt.scatter(eigenvectors[:, 1], eigenvectors[:, 2], c=signal, alpha=0.5)\n", " plt.colorbar()\n", " ```\n", "* Another option is to use the plotting capabilities of **[NetworkX](https://networkx.github.io)**.\n", " See the documentation of its [drawing methods](https://networkx.github.io/documentation/stable/reference/drawing.html).\n", " For example:\n", " ```\n", " import networkx as nx\n", " graph = nx.from_scipy_sparse_matrix(adjacency)\n", " coords = nx.spring_layout(graph) # Force-directed layout.\n", " coords = eigenvectors[:, 1:3] # Laplacian eigenmaps.\n", " nx.draw_networkx_nodes(graph, coords, node_size=60, node_color=signal)\n", " nx.draw_networkx_edges(graph, coords, alpha=0.3)\n", " ```\n", "* Another option is to use the plotting capabilities of the **[PyGSP](https://github.com/epfl-lts2/pygsp)**, a Python package for Graph Signal Processing.\n", " **Note that your are forbidden to use the PyGSP for anything else than plotting.**\n", " See the documentation of its [plotting utilities](https://pygsp.readthedocs.io/en/stable/reference/plotting.html).\n", " For example:\n", " ```\n", " import pygsp as pg\n", " graph = pg.graphs.Graph(adjacency)\n", " graph.set_coordinates('spring') # Force-directed layout.\n", " graph.set_coordinates(eigenvectors[:, 1:3]) # Laplacian eigenmaps.\n", " graph.plot_signal(signal)\n", " ```\n", "* Yet another option is to save your graph on disk, use **[Gephi](https://gephi.org)** externally, to visualize the graph, save the graph with the Gephi coordinates and finally load the nodes coordinates back into the notebook.\n", "\n", "We encourage you to try all the above methods before making your choice. Then be consistent and use only one throughout the milestone.\n", "NetworkX and PyGSP should already be installed in your environement. If that's not the case, install with `conda install networkx pygsp` (after activating the `ntds_2018` environment)." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 0 - Load your network" ], "metadata": {} }, { "cell_type": "code", "source": [ "%matplotlib inline" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "If you get a `No module named 'pyunlocbox'` error when running the below cell, install the [pyunlocbox](https://github.com/epfl-lts2/pyunlocbox) with `conda install pyunlocbox` (after activating the `ntds_2018` environment)." ], "metadata": {} }, { "cell_type": "code", "source": [ "import numpy as np\n", "from scipy import sparse\n", "import scipy.sparse.linalg\n", "from matplotlib import pyplot as plt\n", "from pyunlocbox import functions, solvers" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "For this milestone, all we will need is a set of features/labels for each of the nodes on the network, as well as the Laplacian, $L,$ and Gradient, $\\nabla_G,$ matrices that you have computed for your network while working on milestone 3.\n", "\n", "Import those objects in the cell below (or recompute the Laplacian and Gradient from your stored adjacency matrix, if you wish).\n", "\n_Note_: If your features/labels are not floating-point numbers, please convert them. For example, if your data has labels \"cat\" and \"dog\" for nodes that represent cats or dogs, respectively, you may assign the number `1.0` for the label \"cat\" and the number `-1.0` for the label \"dog\". " ], "metadata": {} }, { "cell_type": "code", "source": [ "laplacian = # Your code here.\n", "gradient = # Your code here.\n", "labels = # Your code here.\n", "n_nodes = # Your code here." ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "## 1 - Graph Fourier Transform\n", "\nIn this section we will observe how your feature/label vector looks like in the \"Graph Fourier\" domain." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Question 1\n", "\nCompute the Fourier basis vectors and the Laplacian eigenvalues. Make sure to order those from smaller to larger, $\\lambda_0 \\leq \\lambda_1 \\leq \\dots \\leq \\lambda_{N-1},$ and use the same ordering for the Fourier basis vectors." ], "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "code", "source": [ "e = # Ordered Laplacian eigenvalues.\n", "U = # Ordered graph Fourier basis." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot the first 3 and the last Fourier basis vectors as signals on your graph. Clearly indicate which plot belongs to which basis vector." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 2\n", "\nWhat can you observe in terms of local variations when comparing the basis vectors corresponding to the smallest eigenvalues to those corresponding to the largest eigenvalue? How would this justify the interpretation of the eigenvalues as \"graph frequencies\"?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Question 3\n", "\nImplement a function that returns the Graph Fourier Transform (GFT) of a given vector $x \\in \\mathbb{R}^{N},$ with respect to your graph, and a function that computes the corresponding inverse GFT (iGFT)." ], "metadata": {} }, { "cell_type": "code", "source": [ "def GFT(x):\n", " return # Your code here.\n", "\n", "def iGFT(x):\n", " return # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 4\n", "\nPlot your feature/label vector as a signal on your graph" ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot the absolute values of the GFT of your feature/label signal as a function of the graph eigenvalues. Make sure to add a marker indicating the position of each graph eigenvalue, and remember to properly name the axes." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "inputHidden": false, "outputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 5\n", "\nDiscuss the behavior of the GFT that you plotted in the last question via comparing the plot of your label signal and those of the Fourier basis of Question 1. Would you consider your labels a \"low-pass\" or \"high-pass\" signal, or yet something else entirely?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 2 - Filtering on graphs\n", "\nIn this section we will check how filtered Dirac impulses diffuse on your graph." ], "metadata": { "code_folding": [] } }, { "cell_type": "markdown", "source": [ "### Question 6 \n", "\n", "Implement the following three filter kernels and the graph filtering operation.\n", "\n", "- The **heat kernel** is supposed to take in a vector of eigenvalues `e` and a parameter `t` and output a vector of evaluations of the heat kernel at those eigenvalues (see the course slides for help).\n", "- The **inverse filter** kernel is supposed to take in a vector of eigenvalues `e` and a parameter `t` and implement spectrally the filter defined in the node domain by $f_{out} = (I + t L)^{-1} f_{in},$ where $f_{in}, f_{out} \\in \\mathbb{R}^{N}$ are, repectively, the input and output signals to the filter.\n", "- The **rectangle kernel** takes in a vector of eigenvalues `e` and parameters `l_min` and `l_max` and returns `1.0` at coordinates satisfying $(e[l] \\geq l_{min}) \\wedge (e[l] \\leq l_{max}),$ and `0.0` otherwise.\n", "- The **graph filtering** operation takes a graph signal $x \\in \\mathbb{R}^{N}$, a spectral graph `kernel` and a set of keyworded variables, and returns the corresponding filtered signal.\n", " - _Hint:_ Remember that you have implemented the `GFT` and `iGFT` operations in Question 3.\n", " - The `**kwargs` is a placeholder to collect supplementary pairs of keyword-values that are not known by the implementation before execution time.\n", " The `kwargs` variable is a dictionary whose keyes and values are the parameter names and values.\n", " This is useful to allow both `graph_filter(x, heat_kernel, tau=1.0)` and `graph_filter(x, rectangle_kernel, lambda_min=0.0, lambda_max=1.0)` to be valid calls from the same implementation.\n", " One can then defer the keyword-value assignment to the `kernel` call: `foo = kernel(bar, **kwargs)`." ], "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "code", "source": [ "def heat_kernel(e, t):\n", " return # Your code here.\n", "\n", "def inverse_kernel(e, t):\n", " return # Your code here.\n", "\n", "def rectangle_kernel(e, l_min, l_max):\n", " return # Your code here.\n", "\n", "def graph_filter(x, kernel, **kwargs):\n", " return # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 7\n", "\nPlot all three filter kernels in the spectral domain. Remember to properly name the axes and title the plots. Choose filter parameters that best approximate the behavior of the GFT of your feature/label signal (as seen in Question 4)." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 8\n", "\nConsider two Dirac impulses arbitrarily placed on your graph. Plot their filtered versions by the three filter kernels implemented in Question 6." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Comment on the \"diffusion\" of the Diracs induced by the filters. What does it say about the \"communication\" of information across your network? Relate that to the network connectivity measures that you analyzed during the previous milestones." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "## 3 - De-noising\n", "\nIn this section we will add some centered Gaussian noise to your feature/label signal and attempt to recover it." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Question 9\n", "\n", "In the cell below, set the noise variance $\\sigma^2$ by making sure that the signal-to-noise ratio $SNR = \\frac{\\operatorname{Var}(\\text{labels})}{\\sigma^2}$ is about $1.5$.\n", "\n_Note:_ Actually, you might want to play with the noise variance here and set it to different values and see how the denoising filters behave." ], "metadata": {} }, { "cell_type": "code", "source": [ "noise_variance = # Your code here.\n", "noisy_measurements = labels + noise_variance * np.random.randn(n_nodes)" ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 10\n", "\n", "In the denoising setting, a common graph signal processing assumption is that the signal $z$ that we want to recover is \"smooth\", in the sense that $\\|\\nabla_G z\\|_2 = \\sqrt{z^{\\top} L z}$ is small, while remaining \"close\" to the measurements that we start with. This leads to denoising by solving the following optimization problem:\n", "\n", "$$\n", "z^\\star = \\text{arg} \\, \\underset{z \\in \\mathbb{R}^{N}}{\\min} \\, \\|z - y\\|_2^2 + \\gamma z^{\\top} L z, \n", "$$\n", "\n", "where $y \\in \\mathbb{R}^{N}$ is the vector of noisy measurements.\n", "\nDerive the close form solution to this problem giving $z^\\star$ as a function of $y$, $\\gamma$ and $L$. Does this solution correspond to any graph filtering operation that you know?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Question 11\n", "\nNow, denoise the noisy measurements by passing them through the filters that you implemented in Question 6. Choose the filter parameters based on the behavior of the GFT of your original label signal (this is the prior knowledge that you input to the problem)." ], "metadata": {} }, { "cell_type": "code", "source": [ "z_heat_denoised = # Your code here.\n", "z_inv_denoised = # Your code here.\n", "z_rect_denoised = # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot, on your graph, the original label signal, the noisy measurements, and the three denoised version obtained above. Report on each plot the value of the corresponding relative error \n", "$$\n", "\\text{rel-err} = \\frac{\\|\\text{labels} - z \\|_2}{\\|\\text{labels}\\|_2},\n", "$$\n", "where $z$ is the plotted signal." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Finally, overlay on the same plot the GFT of all five signals above." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 12\n", "\nComment on which denoised version seems to best match the original label signal. What is the underlying assumption behind the three filtering approaches? Do you think it holds for your label signal? Why?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## 4 - Transductive learning\n", "\n", "It is often the case in large networks that we can only afford to query properties/labels on a small subset of nodes. Nonetheless, if the underlying labels signal is \"regular\" enough, we might still be able to recover a good approximation of it by solving an offline variational problem, with constraints on the values of the measured nodes. \n", "\n", "In this section, we will be interested in solving such transductive learning problems by minimizing a (semi-) p-norm of the graph gradient applied to the signal of interest:\n", "\n", "$$\n", "\\text{arg} \\, \\underset{z|_S = y}{\\min} \\|\\nabla_G z\\|_p^p,\n", "$$\n", "\n", "where $S$ is the set of measured nodes.\n", "\n", "In English, we can say that we are looking for solutions with small \"aggregated local variations\", as measured by $\\|\\nabla_G z\\|_p^p = \\sum_{i=1}^{n} \\sum_{j=1}^{n} \\left( \\sqrt{W_{ij}} |z[i] - z[j]| \\right)^p,$ while satisfying the measurement constraints $z[i] = y[i]$ for $i \\in S.$\n", "\n", "We will work with two cases, according to the choices $p=1$ or $p=2.$ For $p=1,$ the problem is known as \"interpolation by graph total-variation minimization,\" whereas for $p=2$ it is sometimes called \"interpolation by Tikhonov regularization\".\n", "\nIn order to solve these variational problems with the black-box solver provided to you, you will use the [pyunlocbox](https://pyunlocbox.readthedocs.io). This toolbox implements iterative solvers based on so-called [\"proximal-splitting\"](https://en.wikipedia.org/wiki/Proximal_gradient_method) methods." ], "metadata": { "ExecuteTime": { "end_time": "2018-08-31T13:05:59.301384Z", "start_time": "2018-08-31T13:05:59.297336Z" } } }, { "cell_type": "markdown", "source": [ "### Question 13\n", "\nThroughout this section, we will consider only a binarized version of your label signal. If your variable `labels` currently has values other than $\\{-1, 1\\},$ threshold them so that those are the only values taken in this vector. This can be done for example by choosing a number $t \\in \\mathbb{R}$ and then setting $\\text{labels_bin}[i] = 1$ if $\\text{labels}[i] \\geq t$ and $\\text{labels_bin}[i] = 0$ otherwise." ], "metadata": {} }, { "cell_type": "code", "source": [ "labels_bin = # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Now, subsample this binarized label signal by $70\\%$ by choosing, uniformly at random, $30\\%$ of the nodes whose labels we will keep.\n", "\nYou will do this by computing a \"measurement mask\" vector `w` with `1.0`'s at the measured coordinates, and $0.0$'s otherwise." ], "metadata": {} }, { "cell_type": "code", "source": [ "mn_ratio = 0.3\n", "m = int(mn_ratio * n_nodes) # Number of measurements.\n", "\nw = # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot the subsampled signal on the graph. _Hint:_ you might want to set to `numpy.nan` the values of the un-measured nodes for a cleaner plot." ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Interlude\n", "\n", "For the solution of the variational problems you can use the following function as a \"black-box\". \n", "\nYou will just need to provide a `gradient` matrix (which you should already have from Section 0), and an orthogonal projection operator `P` onto the span of the measured coordinates (made precise in the next question)." ], "metadata": {} }, { "cell_type": "code", "source": [ "def graph_pnorm_interpolation(gradient, P, x0=None, p=1., **kwargs):\n", " r\"\"\"\n", " Solve an interpolation problem via gradient p-norm minimization.\n", "\n", " A signal :math:`x` is estimated from its measurements :math:`y = A(x)` by solving\n", " :math:`\\text{arg}\\underset{z \\in \\mathbb{R}^n}{\\min}\n", " \\| \\nabla_G z \\|_p^p \\text{ subject to } Az = y` \n", " via a primal-dual, forward-backward-forward algorithm.\n", "\n", " Parameters\n", " ----------\n", " gradient : array_like\n", " A matrix representing the graph gradient operator\n", " P : callable\n", " Orthogonal projection operator mapping points in :math:`z \\in \\mathbb{R}^n` \n", " onto the set satisfying :math:`A P(z) = A z`.\n", " x0 : array_like, optional\n", " Initial point of the iteration. Must be of dimension n.\n", " (Default is `numpy.random.randn(n)`)\n", " p : {1., 2.}\n", " kwargs :\n", " Additional solver parameters, such as maximum number of iterations\n", " (maxit), relative tolerance on the objective (rtol), and verbosity\n", " level (verbosity). See :func:`pyunlocbox.solvers.solve` for the full\n", " list of options.\n", "\n", " Returns\n", " -------\n", " x : array_like\n", " The solution to the optimization problem.\n", "\n", " \"\"\"\n", " \n", " grad = lambda z: gradient.dot(z)\n", " div = lambda z: gradient.transpose().dot(z)\n", "\n", " # Indicator function of the set satisfying :math:`y = A(z)`\n", " f = functions.func()\n", " f._eval = lambda z: 0\n", " f._prox = lambda z, gamma: P(z)\n", "\n", " # :math:`\\ell_1` norm of the dual variable :math:`d = \\nabla_G z`\n", " g = functions.func()\n", " g._eval = lambda z: np.sum(np.abs(grad(z)))\n", " g._prox = lambda d, gamma: functions._soft_threshold(d, gamma)\n", "\n", " # :math:`\\ell_2` norm of the gradient (for the smooth case)\n", " h = functions.norm_l2(A=grad, At=div)\n", "\n", " stepsize = (0.9 / (1. + scipy.sparse.linalg.norm(gradient, ord='fro'))) ** p\n", "\n", " solver = solvers.mlfbf(L=grad, Lt=div, step=stepsize)\n", "\n", " if p == 1.:\n", " problem = solvers.solve([f, g, functions.dummy()], x0=x0, solver=solver, **kwargs)\n", " return problem['sol']\n", " if p == 2.:\n", " problem = solvers.solve([f, functions.dummy(), h], x0=x0, solver=solver, **kwargs)\n", " return problem['sol']\n", " else:\n", " return x0" ], "outputs": [], "execution_count": null, "metadata": {} }, { "cell_type": "markdown", "source": [ "### Question 14\n", "\n", "During the iterations of the algorithm used for solving the variational problem, we have to make sure that the labels at the measured nodes stay the same. We will do this by means of an operator `P` which, given a vector $a \\in \\mathbb{R}^{N},$ returns another vector $b \\in \\mathbb{R}^{N}$ satisfying $b[i] = \\text{labels_bin}[i]$ for every node $i$ in the set $S$ of known labels, and $b[i] = a[i]$ otherwise. Write in the cell below the function for this orthogonal projection operator `P`.\n", "\n_Hint:_ remember you have already computed the mask `w`." ], "metadata": {} }, { "cell_type": "code", "source": [ "def P(a):\n", " # Your code here.\n", " return b" ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 15\n", "\n", "Solve the variational problems for $p = 1$ and $p = 2$. Record the solution for the $1-$norm minimization under `sol_1norm_min` and the one for $2-$norm minimization under `sol_2norm_min`.\n", "\nCompute also binarized versions of these solutions by thresholding the values with respect to $0$, that is, non-negative values become `1.0`, while negative values become `-1.0`. Store those binarized versions under `sol_1norm_bin` and `sol_2norm_bin`, respectively." ], "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "code", "source": [ "sol_1norm_min = # Your code here.\n", "\n", "sol_2norm_min = # Your code here.\n", "\n", "threshold = 0\n", "\n", "sol_1norm_bin = # Your code here.\n", "\nsol_2norm_bin = # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot, on your graph, the original `labels_bin` signal, as well as the solutions to the variational problems (both binarized and otherwise). Indicate on each plot the value of the relative error $\\text{rel-err} = \\frac{\\|\\text{labels_bin} - z\\|_2}{\\|\\text{labels_bin}\\|_2}$, where $z$ is the signal in the corresponding plot." ], "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 16\n", "\n", "Now that you have got a feeling for the sort of solutions that the transductive learning problems studied can give, we will see what is the effect of the number of measurements on the accuracy of both $p-$norm minimization problems.\n", "\n", "Towards this goal, you will write a `phase_transition()` function. This function will basically go over all the procedures that you have implemented in this section, but for varying numbers of measurements and thresholding values. It will also compute the relative error, $\\text{rel-err},$ of the solutions and average them over a number of trials.\n", "\n", "The output of the `phase_transition()` function has to be a matrix with `len(mn_ratios)` columns and `len(thresholds)` rows. Each pixel $(i,j)$ in the output matrix has to contain the average, over `n_trials` trials, of the relative error $\\text{rel-err}$ in the binarized (with threshold `thresholds[i]`) solution given by `graph_pnorm_interpolation()` from observing an `mn_ratios[j]` fraction of nodes. The randomness comes from a different choice of mask `w` at each trial, hence the averaging.\n", "\nThe interest of this phase transition matrix is to assess what level of recovery error one could expect for a certain fraction of measurements and a certain threshold level." ], "metadata": {} }, { "cell_type": "code", "source": [ "def phase_transition(mn_ratios, thresholds, n_trials, labels_bin, p):\n", "\n", " # Create sample mask.\n", " \n", " # Solve p-norm interpolation.\n", " \n", " # Aggregate.\n", " \n", " return pt_matrix" ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 17\n", "\nPick 5 \"m/n\" ratios in $(0, 1)$ and 5 threshold levels in $(-1, 1)$ and run the `phase_transition()` function with `n_trials` = 20, for both $p = 1$ and $p = 2$." ], "metadata": {} }, { "cell_type": "code", "source": [ "mn_ratios = # Your code here.\n", "\n", "thresholds = # Your code here.\n", "\n", "pt_matrix_1norm = # Your code here.\n", "\npt_matrix_2norm = # Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "Plot both phase transition matrices as images with a colorbar. Make sure to properly name the axes and title the images. " ], "metadata": {} }, { "cell_type": "code", "source": [ "# Your code here." ], "outputs": [], "execution_count": null, "metadata": { "collapsed": false, "outputHidden": false, "inputHidden": false } }, { "cell_type": "markdown", "source": [ "### Question 18\n", "\nDo the phase transition plots above provide any justification for choosing one $p-$norm interpolation over the other? Why?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "**Your answer here.**" ], "metadata": {} } ], "metadata": { "kernel_info": { "name": "python3" }, "kernelspec": { "name": "python3", "language": "python", "display_name": "Python 3" }, "language_info": { "name": "python", "version": "3.6.5", "mimetype": "text/x-python", "codemirror_mode": { "name": "ipython", "version": 3 }, "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "file_extension": ".py" }, "latex_envs": { "report_style_numbering": false, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "LaTeX_envs_menu_present": true, "autocomplete": true, "autoclose": true, "eqNumInitial": 1, "bibliofile": "biblio.bib", "latex_user_defs": false, "current_citInitial": 1, "eqLabelWithNumbers": true, "labels_anchors": false, "cite_by": "apalike", "user_envs_cfg": false }, "nteract": { "version": "0.12.3" }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }