<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experiment: classification with learned graph filters\n",
    "\n",
    "We want to classify data by first extracting meaningful features from learned filters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np\n",
    "import scipy.sparse, scipy.sparse.linalg, scipy.spatial.distance\n",
    "import sklearn\n",
    "from sklearn import datasets, linear_model, metrics, cross_validation\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tauR = 1e0\n",
    "tauF = 1e0\n",
    "F = 6\n",
    "K = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dataset\n",
    "\n",
    "* Two digits version of MNIST with N samples of each class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mnist(a, b, N):\n",
    "    \"\"\"Prepare data for binary classification of MNIST.\"\"\"\n",
    "    mnist = datasets.fetch_mldata('MNIST original', data_home='.')\n",
    "\n",
    "    assert N < min(sum(mnist.target==a), sum(mnist.target==b))\n",
    "    M = mnist.data.shape[1]\n",
    "    \n",
    "    X = np.empty((M, 2, N))\n",
    "    X[:,0,:] = mnist.data[mnist.target==a,:][:N,:].T\n",
    "    X[:,1,:] = mnist.data[mnist.target==b,:][:N,:].T\n",
    "    \n",
    "    y = np.empty((2, N))\n",
    "    y[0,:] = -1\n",
    "    y[1,:] = +1\n",
    "\n",
    "    X.shape = M, 2*N\n",
    "    y.shape = 2*N, 1\n",
    "    return X, y\n",
    "\n",
    "X, y = mnist(5, 1, 1000)\n",
    "\n",
    "M, N = X.shape\n",
    "print('Dimensionality: N={} samples, M={} features'.format(N, M))\n",
    "\n",
    "X -= 127.5\n",
    "print('X in [{}, {}]'.format(np.min(X), np.max(X)))\n",
    "\n",
    "def plot_digit(nn):\n",
    "    m = int(np.sqrt(M))\n",
    "    fig, axes = plt.subplots(1,len(nn), figsize=(15,5))\n",
    "    for i, n in enumerate(nn):\n",
    "        n = int(n)\n",
    "        img = X[:,n]\n",
    "        axes[i].imshow(img.reshape((m,m)))\n",
    "        axes[i].set_title('Label: y = {:.0f}'.format(y[n,0]))\n",
    "\n",
    "plot_digit([0, 1, 1e2, 1e2+1, 1e3, 1e3+1])\n",
    "\n",
    "#M, N = 784, 1000\n",
    "#X = X[:M, :N]\n",
    "#y = y[:N]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regularized least-square\n",
    "\n",
    "## Loss and gradient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def L(w, b=0):\n",
    "    return np.linalg.norm(X.T @ w + b - y)**2 / N + tauR * np.linalg.norm(w)**2\n",
    "\n",
    "def dL(w, nn=None):\n",
    "    N = len(y)\n",
    "    return 2 / N * X @ (X.T @ w - y) + 2 * tauR * w\n",
    "\n",
    "def print_perf(w, L, dL):\n",
    "    print('L({}) = {}'.format(w, L(eval(w))))\n",
    "    print('|dL({})| = {}'.format(w, np.linalg.norm(dL(eval(w)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reference: sklearn ridge regression\n",
    "\n",
    "* With regularized data, the objective is the same with or without bias."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "clf = linear_model.Ridge(alpha=tauR*N, fit_intercept=False)\n",
    "clf.fit(X.T, y)\n",
    "w_skl = clf.coef_.T\n",
    "\n",
    "print('L(w_skl) = {}'.format(L(w_skl, clf.intercept_)))\n",
    "print_perf('w_skl', L, dL)\n",
    "\n",
    "# Normalized data: intercept should be small.\n",
    "print('bias: {}'.format(abs(np.mean(y - X.T @ w_skl))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "w_d = np.linalg.inv(X @ X.T + tauR * N * np.identity(M)) @ X @ y\n",
    "print_perf('w_d', L, dL)\n",
    "np.testing.assert_allclose(w_d, w_skl, atol=1e-8)\n",
    "del M, N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},<commit_msg>Suppress normalization by N<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experiment: classification with learned graph filters\n",
    "\n",
    "We want to classify data by first extracting meaningful features from learned filters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np\n",
    "import scipy.sparse, scipy.sparse.linalg, scipy.spatial.distance\n",
    "import sklearn\n",
    "from sklearn import datasets, linear_model, metrics, cross_validation\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tauR = 1e-3\n",
    "tauF = 1e-3\n",
    "F = 6\n",
    "K = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dataset\n",
    "\n",
    "* Two digits version of MNIST with N samples of each class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mnist(a, b, N):\n",
    "    \"\"\"Prepare data for binary classification of MNIST.\"\"\"\n",
    "    mnist = datasets.fetch_mldata('MNIST original', data_home='.')\n",
    "\n",
    "    assert N < min(sum(mnist.target==a), sum(mnist.target==b))\n",
    "    M = mnist.data.shape[1]\n",
    "    \n",
    "    X = np.empty((M, 2, N))\n",
    "    X[:,0,:] = mnist.data[mnist.target==a,:][:N,:].T\n",
    "    X[:,1,:] = mnist.data[mnist.target==b,:][:N,:].T\n",
    "    \n",
    "    y = np.empty((2, N))\n",
    "    y[0,:] = -1\n",
    "    y[1,:] = +1\n",
    "\n",
    "    X.shape = M, 2*N\n",
    "    y.shape = 2*N, 1\n",
    "    return X, y\n",
    "\n",
    "X, y = mnist(5, 1, 1000)\n",
    "\n",
    "print('Dimensionality: N={} samples, M={} features'.format(X.shape[1], X.shape[0]))\n",
    "\n",
    "X -= 127.5\n",
    "print('X in [{}, {}]'.format(np.min(X), np.max(X)))\n",
    "\n",
    "def plot_digit(nn):\n",
    "    M, N = X.shape\n",
    "    m = int(np.sqrt(M))\n",
    "    fig, axes = plt.subplots(1,len(nn), figsize=(15,5))\n",
    "    for i, n in enumerate(nn):\n",
    "        n = int(n)\n",
    "        img = X[:,n]\n",
    "        axes[i].imshow(img.reshape((m,m)))\n",
    "        axes[i].set_title('Label: y = {:.0f}'.format(y[n,0]))\n",
    "\n",
    "plot_digit([0, 1, 1e2, 1e2+1, 1e3, 1e3+1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regularized least-square\n",
    "\n",
    "## Loss and gradient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def L(w, b=0):\n",
    "    return np.linalg.norm(X.T @ w + b - y)**2 + tauR * np.linalg.norm(w)**2\n",
    "\n",
    "def dL(w):\n",
    "    return 2 * X @ (X.T @ w - y) + 2 * tauR * w\n",
    "\n",
    "def print_perf(w):\n",
    "    print('L(w) = {}'.format(L(w)))\n",
    "    print('|dL(w)| = {}'.format(np.linalg.norm(dL(w))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reference: sklearn ridge regression\n",
    "\n",
    "* With regularized data, the objective is the same with or without bias."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "clf = linear_model.Ridge(alpha=tauR, fit_intercept=False)\n",
    "clf.fit(X.T, y)\n",
    "w = clf.coef_.T\n",
    "\n",
    "print('L(w_skl) = {}'.format(L(w, clf.intercept_)))\n",
    "print_perf(w)\n",
    "\n",
    "# Normalized data: intercept should be small.\n",
    "print('bias: {}'.format(abs(np.mean(y - X.T @ w))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "w = np.linalg.inv(X @ X.T + tauR * np.identity(X.shape[0])) @ X @ y\n",
    "print_perf(w)\n",
    "w = np.linalg.solve(X @ X.T + tauR * np.identity(X.shape[0]), X @ y)\n",
    "print_perf(w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
{'fraction_non_alphanumeric': 0.24635155739490308, 'fraction_numerical': 0.012524504465258114, 'mean_word_length': 2.2726300784034215, 'pattern_counts': {'":': 114, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7285947', 'n_tokens_mistral': 4020, 'n_tokens_neox': 3886, 'n_words': 713}