LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 7

Reply
 
Thread Tools Display Modes
  #1  
Old 05-26-2013, 11:34 PM
Ziad Hatahet Ziad Hatahet is offline
Member
 
Join Date: Apr 2013
Location: San Francisco, CA
Posts: 23
Default *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.
Reply With Quote
  #2  
Old 04-06-2016, 05:41 AM
galo galo is offline
Junior Member
 
Join Date: Jan 2016
Posts: 7
Default 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.
Reply With Quote
  #3  
Old 07-21-2017, 06:15 AM
jakub jakub is offline
Junior Member
 
Join Date: Jul 2017
Posts: 1
Default 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.
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


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


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2017, 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.