LFD Book Forum *ANSWER* Question 9
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
05-26-2013, 11:34 PM
 Ziad Hatahet Member Join Date: Apr 2013 Location: San Francisco, CA Posts: 23
*ANSWER* Question 9

I wanted to confirm my answer with what others are getting.

I coded up the solution in MATLAB. I seem to have gotten somewhat lucky when I answered [d] for this question, since the ratio from one of the runs was 0.61, which is closer to 70% than 50%.

However, I was re-running the code after submission, and it seems that the result fluctuates around 0.6, sometimes dropping below that.

My code follows. I would appreciate if anyone has insights as to where I am going wrong. It is most likely in the % Quadratic Programming % section, since PLA is lifted straight from the previous assignments I coded.

Code:
```clear all
clc

N = 100;
Ntest = 1000;
TRIALS = 1000;
better = 0;
sv_count = 0;

for ii = 1:TRIALS
% Generate random line
p1 = 2*rand(2, 1) - 1;
p2 = 2*rand(2, 1) - 1;
% Possibility of divide by 0. Better to just use w0 + x1*w1 + x2*w2 form.
slope = (p2(2) - p1(2)) / (p2(1) - p1(1));
intercept = p1(2) - slope*p1(1);
line = [slope intercept];

% Generate random points
% points are (x, y) coords
points = 2*rand(N, 2) - 1;
y = sign(points(:, 2) - polyval(line, points(:, 1)));
X = [ones(size(points, 1), 1) points]; % Add extra dimension

% PLA
wpla = zeros(3, 1);
while true
% Classify
yfit = sign(X*wpla);
combined = [X y];
bad = combined(yfit ~= y, :);

if size(bad, 1) == 0
break;
end

i = randi(size(bad, 1), 1);
wpla = wpla + bad(i, 4)*bad(i, [1:3])';
end

% Quadratic programming
X_svm = X(:, [2:3]); % Discard the constant term
H = (y*y').*(X_svm*X_svm');
f = ones(N, 1)*-1;
A = y';
b = 0;
lb = zeros(N, 1);
ub = 1e6*ones(N, 1);
options = optimset('Algorithm','interior-point-convex','MaxIter',1500, 'Display', 'off');

alpha = quadprog(H, f, [], [], A, b, lb, ub, [], options);
wquad = zeros(3, 1);
wquad(2) = sum(X_svm(:, 1).*(alpha.*y));
wquad(3) = sum(X_svm(:, 2).*(alpha.*y));

% Get index of maximum alpha
[maxval, maxind] = max(alpha);
wquad(1) = 1/y(maxind) - X_svm(maxind, :)*wquad(2:3);

% Eout
points = 2*rand(Ntest, 2) - 1;
X = [ones(size(points, 1), 1) points];
y = 2*[points(:, 2) > polyval(line, points(:, 1))] - 1;

e_pla = sum(sign(X*wpla) ~= y)/size(X, 1);
e_svm = sum(sign(X*wquad) ~= y)/size(X, 1);
better = better + (e_svm < e_pla);

% SVM
sv_count = sv_count + sum(alpha > 0.001); % Floating point tolerance
end

(better/TRIALS) * 100
sv_count/TRIALS```

Last edited by Ziad Hatahet; 05-27-2013 at 01:27 AM. Reason: Pasted code incorrectly.
#2
04-06-2016, 05:41 AM
 galo Junior Member Join Date: Jan 2016 Posts: 7
Re: *ANSWER* Question 9

I had the same situation happened in Python. I'm pretty sure I checked everything for errors. The thing that I changed is, instead of doing
Code:
`better = better + (e_svm < e_pla);`
I did
Code:
`better = better + (e_svm <= e_pla);`
This made the percentage go consistently over 60%. I see this as saying that the SVM algorithm is better whenever the PLA is not. I agree, it's a bit of a stretch and a tweak made only because I saw the answer, but it works.
#3
07-21-2017, 06:15 AM
 jakub Junior Member Join Date: Jul 2017 Posts: 1
Re: *ANSWER* Question 9

Hi,

Sorry for being somewhat late (3 years?) in joining this discussion.

I don't have Matlab to verify it, but I've run into a similar problem using Python and CVXOPT. The solution was to increase the number of test points from 10^3 to 10^4, assuming that's the method you use to calculate which result is closer to f.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 03:04 AM.

 Contact Us - LFD Book - Top

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.