LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 7 (http://book.caltech.edu/bookforum/forumdisplay.php?f=136)
-   -   *ANSWER* Question 9 (http://book.caltech.edu/bookforum/showthread.php?t=4315)

Ziad Hatahet 05-27-2013 12:34 AM

*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


galo 04-06-2016 06:41 AM

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.

jakub 07-21-2017 07:15 AM

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.


All times are GMT -7. The time now is 11:24 AM.

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.