# Perceptron Learning Algorithm: retorna vector de pesos de un perceptron

# parametros:
# X: matrix de N*(d+1) elementos, filas de X son puntos x_i
# y: vector de N*1 elementos, sus valores corresponden a la clasificacion de x_i
# max_iter: maximo numero de iteraciones. max_iter == 0 sin limite (opcional)
# random: random == 1 ssi se eligen (xt, yt) al azar (opcional)
# w: vector de pesos inicial (opcional)

# retorna:
# w: vector de pesos. Si datos son lineal% separables, sign(X*w) == y
# t: numero de iteraciones que realizo antes de detenerse
function [w, t] = pla(X, y, max_iter=0, random=0, w=zeros(size(X, 2), 1))
  N = size(X, 1);      # filas de X
  d = size(X, 2) - 1;  # total dimensiones
  t = 0;

  while 1
    t = t + 1;

    if t == max_iter  # supera el limite de iteraciones
      return
    end

    # escoger un par (xt, yt) tal que yt != sign(w' * xt)
    [xt, yt] = misclassified(X, y, N, w, random);

    Ein_tmp = sum(sign(X * w) != y) / N

    if ischar(xt)     # ugly hack: no hay puntos mal clasificados
      return
    end

    w = w + yt * xt;  # actualizar w
  end
end


# Funcion auxiliar: retorna punto mal clasificado por w

# parametros:
# X: matrix de N*(d+1) elementos, filas de X son puntos x_i
# y: vector de N*1 elementos, sus valores corresponden a la clasificacion de x_i
# N: total de filas de X (o y)
# w: vector de pesos tentativo, w(t)
# random: random == 0 ssi se elige (xt, yt) al azar entre todos los que cumplen

# retorna (xt, yt) tal que yt != sign(w'*xt)
# Si no hay tal punto, retorna ":-)" (string)
function [xt, yt] = misclassified(X, y, N, w, random)
  if random
    indices = randperm(N);  # permutacion de 1:N
  else
    indices = 1:N;          # 1:N en orden
  end

  for i = indices
    xt = X(i,:)';       # escoger x_i
    yt = y(i);          # escoger y_i correspondiente

    if sign(w' * xt) != yt
      return            # si xt esta mal clasificado, retornar (xt, yt)
    end
  end

  xt = ":-)";           # todos los puntos estan bien clasificados

end