$4$ Iterative Reweighted Least Squares

Implement the IRLS algorithm

See the slides for the algorithm description.

The algorithm should perform Newton's step itercnt times using the given weights w as the starting point.

The algorithm should return the updated weights w$,$ and arrays err and misclass of length itercnt $+1.$

misclass $[$i$]$ is the misclassification rate $($normalized between $0$ and $1)$ after i iterations. misclass $[0]$ is

the misclassification rate with initial w$.$ If $w^{T}x=0($that is $x$ is at the decision boundary$),$ then the classifier

should predict $1.$ If you use the sign function, be aware that sign$(0)$ returns $0.$

err $[$i$]$ is the loss $(=$negative log$-$likelihood$)$ after i iterations. err $[0]$ is the loss with initial w$.$ I will give the python code where you have to fill the blanks. Also I am attaching the python code which automatically corrects the answer. Answer: "import sys

import numpy as np

def irls$($X$,$ labels, w$,$ itercnt$)$:

$"""$

IRLS algorithm

Parameters

$----------$

X : an array of size $($n$,$ k$)$

training input data for the classifier

labels : an array of size n

training labels for the classifier, elements must be $0/1$

w : an array of size k

initial weights

itercnt : int

number of iterations

Returns

$-------$

w : an array of size k

weights after itercnt iterations

err: an array of size itercnt $+1$

ith element correspongs to the error $($objective function minimized in

logistic regression$)$ after the ith iteration. The $0$th entry is the

error with the initial weights.

misclass: an array of size itercnt $+1$

ith element correspongs to the misclassification proportion after the

ith iteration. The $0$th entry is the misclassification proportion with

the initial weights.

$"""$

err $=$ np$.$zeros$($itercnt $+1)$

misclass $=$ np$.$zeros$($itercnt $+1)$

y $=$ labels$*2-1$ # label $0->$ y $=-1,$ label $1->$ y $=1$

# place your code here

return w$,$ err, misclass

def main$($argv$)$:

D $=$ np$.$loadtxt$($argv$[1])$

labels $=$ D$[$:$,0].$copy$()$ # copy is needed, otherwise next line will mess up the splice

D$[$:$,0]=1$ # replace the label column of D with constant, now the first feature gives us the bias term

itercnt $=$ int$($argv$[2])$

w $=$ np$.$zeros$($D$.$shape$[1])$

w$,$ err, misclass $=$ irls$($D$,$ labels, w$,$ itercnt$)$

print$(\text{'}$weights:$\text{'})$

print$($w$)$

print$(\text{'}$error:$\text{'})$

print$($err$)$

print$(\text{'}$misclassification rate:$\text{'})$

print$($misclass$)$

# This allows the script to be used as a module and as a standalone program

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

if len$($sys$.$argv$)!=3$:

print$(\text{'}$usage: python $\%$s filename' $\%$ sys$.$argv$[0])$

else:

main$($sys$.$argv$)"$ Automatically correcting python code: $"$#$!/$usr$/$bin$/$env python$3$

import sys

import unittest

from tmc import points

from tmc$.$utils import load, get$\_$out

import numpy as np

from $.$utils import errormsg, ApproxTest

@points$(\text{'}2\mathrm{.}2\mathrm{.}1\text{'},\text{'}2\mathrm{.}2\mathrm{.}2\text{'},\text{'}2\mathrm{.}2\mathrm{.}3\text{'},\text{'}2\mathrm{.}2\mathrm{.}4\text{'},\text{'}2\mathrm{.}2\mathrm{.}5\text{'})$

class IrlsTester$($ApproxTest$)$:

def test$\_$irls$($self$)$:

irls $=$ load$(\text{'}$src$.$irls', 'irls'$)$

D $=$ np$.$loadtxt$(\text{'}$test$/$toy$.$txt$\text{'})$

labels $=$ D$[$:$,0].$copy$()$ # copy is needed, otherwise next line will mess up the splice

D$[$:$,0]=1$ # replace the label column of D with constant, now the first feature gives us the bias term

w $=$ np$.$zeros$($D$.$shape$[1])$

w$,$ err, misclass $=$ irls$($D$,$ labels, w$,10)$

w$1=$ np$.$array$([$

$14\mathrm{.}2225575,-3\mathrm{.}83007457,3\mathrm{.}9215949,-2\mathrm{.}73087605,0\mathrm{.}9907367,-1\mathrm{.}9727234,$

$-0\mathrm{.}2329434,-1\mathrm{.}76999314,-5\mathrm{.}60257676,-0\mathrm{.}11626992,-5\mathrm{.}22387472])$

err$1=$ np$.$array$([$

$138\mathrm{.}62943611,51\mathrm{.}57260799,31\mathrm{.}2257094,21\mathrm{.}52724814,16\mathrm{.}25098254,$

$13\mathrm{.}29340328,11\mathrm{.}87038151,11\mathrm{.}4422655,11\mathrm{.}38955273,11\mathrm{.}38827445,$

$11\mathrm{.}38827308])$

misclass$1=$ np$.$array$([0\mathrm{.}5,0\mathrm{.}04,0\mathrm{.}035,0\mathrm{.}035,0\mathrm{.}03,0\mathrm{.}025,0\mathrm{.}025,0\mathrm{.}025,0\mathrm{.}025,0\mathrm{.}025,0\mathrm{.}025])$

self.assertApprox$($w$1,$ w$,$ errormsg$("$Incorrect weights $($input toy.txt$,$ w $=0,$ itercnt $=10)",$ w$1,$ w$))$

self.assertApprox$($err$1,$ err, errormsg$("$Incorrect error $($input toy.txt$,$ w $=0,$ itercnt $=10)",$ err$1,$ err$))$

self.assertApprox$($misclass$1,$ misclass, errormsg$("$Incorrect misclassication rate $($input toy.txt$,$ w $=0,$ itercnt $=10)",$ misclass$1,$ misclass$))"$