L2 SVM.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using LIBLINEAR, SparseArrays, ProgressMeter, LinearAlgebra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solvers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "function mengdi3(A,b,maxiters,C,M)\n",
    "    n = size(A)[1]\n",
    "    m = Int(size(A)[2])\n",
    "    w = zeros(m)\n",
    "    ξ = spzeros(n)\n",
    "    for i = 1:maxiters\n",
    "        α = 1/(i+10)\n",
    "        w -= α*w\n",
    "        #ξ -= α*ξ/C\n",
    "        \n",
    "        I = zeros(M)\n",
    "        for s = 1:M\n",
    "            I[s] = Int(ceil(rand()*n))\n",
    "        end\n",
    "        for r = 1:M\n",
    "            z = zeros(M)\n",
    "            \n",
    "            for s = 1:M\n",
    "                j = Int(I[s])\n",
    "                a = A[j,:]\n",
    "                θ = ((a' * w)[1] - 1 + ξ[j])/(sum(a.^2))\n",
    "                c = min(θ,z[s])\n",
    "                w -= c .* a\n",
    "                z[s] -= c\n",
    "                if z[s] < 1e-15\n",
    "                    z[s] = 0\n",
    "                end\n",
    "            end\n",
    "        end\n",
    "        \n",
    "        if i%100 == 0\n",
    "            accVal = sum(yval .== sign.(Xval*w))/length(yval)\n",
    "            acc = sum(y .== sign.(X*w))/length(y)\n",
    "            @show((acc,accVal))\n",
    "            flush(stdout)\n",
    "        end\n",
    "        \n",
    "    end\n",
    "    \n",
    "    return w\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "function mengdi(A,b,maxiters,C,M)\n",
    "    n = size(A)[1]\n",
    "    m = Int(size(A)[2])\n",
    "    w = rand(m)\n",
    "    ξ = spzeros(n)\n",
    "    for i = 1:maxiters\n",
    "        α = 1/(i+10)\n",
    "        w̃ = w - α*w\n",
    "        #ξ -= α*ξ/C\n",
    "        \n",
    "        w′ = copy(w̃) \n",
    "        θmax = 0\n",
    "        jmax = 0\n",
    "        max = 0\n",
    "        for s = 1:M\n",
    "            j = Int(ceil(rand()*n))\n",
    "            a = A[j,:]\n",
    "            θ = ((a' * w̃)[1] + ξ[j])/(sum(a.^2))\n",
    "            if θ < 0\n",
    "                ŵ = w - θ .* a\n",
    "                if norm(ŵ-w̃) > max\n",
    "                    max = norm(ŵ-w̃)\n",
    "                    w′ = ŵ\n",
    "                    θmax = θ\n",
    "                    jmax = j\n",
    "                end\n",
    "            end\n",
    "        end\n",
    "        \n",
    "        w = w′\n",
    "        #ξ[jmax] -= θmax/C\n",
    "        \n",
    "        if i%100 == 0\n",
    "            accVal = sum(yval .== sign.(Xval*w))/length(yval)\n",
    "            acc = sum(y .== sign.(X*w))/length(y)\n",
    "            @show((acc,accVal))\n",
    "            flush(stdout)\n",
    "        end\n",
    "        \n",
    "    end\n",
    "    \n",
    "    return w\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "function SVM(A,b,maxiters,tol,C)\n",
    "    n = size(A)[1]\n",
    "    m = Int(size(A)[2])\n",
    "    z = spzeros(n)\n",
    "    z′ = spzeros(n)\n",
    "    w = zeros(m)\n",
    "    ξ = spzeros(n)\n",
    "    maxD = tol + 1\n",
    "    count = 0\n",
    "    A = b.* A\n",
    "    for i = 1:maxiters\n",
    "        j = Int(ceil(rand()*n))\n",
    "        a = A[j,:]\n",
    "        θ = ((a' * w)[1] - 1 + ξ[j])/(sum(a.^2)+1/C)\n",
    "        c = min(θ,z[j])\n",
    "        w -= c .* a\n",
    "        ξ[j] -= c/C\n",
    "        z[j] -= c\n",
    "        if z[j] < 1e-15\n",
    "            z[j] = 0\n",
    "        end\n",
    "        if abs(c) > maxD\n",
    "            maxD = abs(c)\n",
    "        end\n",
    "            \n",
    "        c = min(z′[j],ξ[j])\n",
    "        ξ[j] -= c\n",
    "        z′[j] -= c\n",
    "        \n",
    "    end\n",
    "\n",
    "    return w\n",
    "end       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generate Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 10000000\n",
    "d = 100\n",
    "X = 1*randn(N,d)\n",
    "Xval = 1*randn(N,d)\n",
    "w = randn(d)\n",
    "y = sign.(X*w)\n",
    "yval = sign.(Xval*w)\n",
    "X += randn(N,d);\n",
    "Xval += randn(N,d);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(abs.(y - sign.(X*w)))/N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Xnew = X'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Use LibLinear\n",
    "\n",
    "setting solver_type=Cint(2) switches to the primal solver. Removing this defaults to the dual solver. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@time model = linear_train(y, X', eps=0.001, C=1000, verbose=true, solver_type=Cint(2));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(predicted_labels, decision_values) = linear_predict(model, Xval');\n",
    "sum((predicted_labels .== yval))/length(yval)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Using Project and Forget"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "@time w2 = SVM(X,y,10000,0.1,1000)\n",
    "accVal = sum(yval .== sign.(Xval*w2))/length(yval)\n",
    "acc = sum(y .== sign.(X*w2))/length(y)\n",
    "@show((acc,accVal))\n",
    "flush(stdout)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Using Mengdi algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@time mengdi(X,y,10000000,1000,100)"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.4.1",
   "language": "julia",
   "name": "julia-1.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.4.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}