Градиент потери шарнира

25

Я пытаюсь реализовать базовый градиентный спуск, и я тестирую его с функцией потери шарнира, т.е. . Тем не менее, я запутался в градиенте потери шарнира. У меня сложилось впечатление, что этоlhinge=max(0,1y xw)

wlhinge={y xif y xw<10if y xw1

Но разве это не возвращает матрицу того же размера, что и x ? Я думал, что мы хотим вернуть вектор длины w ? Очевидно, я где-то запутался. Может ли кто-то указать правильное направление здесь?

Я включил некоторый основной код на случай, если мое описание задачи было неясным

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-c(1,1,-1,-1)
    w<-matrix(0, nrow=ncol(x))

    print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w,collapse=',')))
    }
}
#Hinge loss
hinge<-function(w,x,y) max(1-y%*%x%*%w, 0)
d_hinge<-function(w,x,y){ dw<-t(-y%*%x); dw[y%*%x%*%w>=1]<-0; dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

Обновление: хотя приведенный ниже ответ помог мне понять проблему, выходные данные этого алгоритма все еще неверны для данных. Функция потерь уменьшается на 0,25 каждый раз, но сходится слишком быстро, и полученные веса не приводят к хорошей классификации. В настоящее время вывод выглядит как

#y=1,1,-1,-1
"loss: 1.000000, x.w: 0,0,0,0"
"loss: 0.750000, x.w: 0.06,-0.1,-0.08,-0.21"
"loss: 0.500000, x.w: 0.12,-0.2,-0.16,-0.42"
"loss: 0.250000, x.w: 0.18,-0.3,-0.24,-0.63"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
...  
Английское общество Красного Креста
источник
Градиент является вектором, так как ваша функция потерь имеет реальные значения.
Вок
3
Ваша функция не везде дифференцируема.
Робин Жирар
2
Как отмечает Робин, потеря шарнира не дифференцируема при x = 1. Это просто означает, что вам нужно использовать алгоритм
субградиентного

Ответы:

27

Чтобы получить градиент, мы дифференцируем потери по й составляющей .жiw

Перепишите потерю шарнира в терминах как где иf ( g ( w ) ) f ( z ) = max ( 0 , 1 - y z ) g ( w ) = xwwf(g(w))f(z)=max(0,1y z)g(w)=xw

Используя правило цепи мы получаем

wif(g(w))=fzgwi

Первый производный член оценивается при становящемся когда , и 0, когда . Второй производный член становится . Таким образом, в конце вы получаете - у йш < 1 хш > 1 х я F ( г ( ж ) )g(w)=xwyxw<1xw>1xi

f(g(w))wi={y xiif y xw<10if y xw>1

Так как охватывает компоненты , вы можете просмотреть вышеупомянутое как векторную величину и написать качестве сокращения длях ix (w(w1,w2,)

Ярослав Булатов
источник
Благодарность! Это проясняет ситуацию для меня. Теперь я просто должен сделать это правильно в практической обстановке. Вы случайно не представляете, почему вышеприведенный код не работает? Кажется, что он сходится за 4 итерации, при этом потери начинаются с 1 и снижаются каждый раз на 0,25 и сходятся на 0. Однако производимые им веса кажутся совершенно неправильными.
2010 г.
1
Вы можете проверить, какие прогнозы он дает вашим тренировочным данным. Если потери сводятся к нулю, все случаи должны быть классифицированы отлично
Ярослав Булатов
Это касается бинарной классификации. Не могли бы вы дать вывод для градиента мультиклассовой классификации с использованием потери шарнира?
Шямкхадка
12

Это на 3 года позже, но все еще может быть актуально для кого-то ...

Обозначим через выборку точек и множество соответствующих меток . Мы ищем, чтобы найти гиперплоскость , которая минимизировала бы общую потерю шарнира: Чтобы найти взять производную от общей потери шарнира. Градиент каждого компонента: SxiRdyi{1,1}ww l h i n g e

w=argmin wLShinge(w)=argmin wilhinge(w,xi,yi)=argmin wimax{0,1yiwx}
w
lhingew={0yiwx1yixyiwx<1

Градиент суммы является суммой градиентов. Пример Python, который использует GD для поиска следует оптимальная гиперплоскость с потерей шарнира (вероятно, это не самый эффективный код, но он работает)

LShingew=ilhingew
import numpy as np
import matplotlib.pyplot as plt

def hinge_loss(w,x,y):
    """ evaluates hinge loss and its gradient at w

    rows of x are data points
    y is a vector of labels
    """
    loss,grad = 0,0
    for (x_,y_) in zip(x,y):
        v = y_*np.dot(w,x_)
        loss += max(0,1-v)
        grad += 0 if v > 1 else -y_*x_
    return (loss,grad)

def grad_descent(x,y,w,step,thresh=0.001):
    grad = np.inf
    ws = np.zeros((2,0))
    ws = np.hstack((ws,w.reshape(2,1)))
    step_num = 1
    delta = np.inf
    loss0 = np.inf
    while np.abs(delta)>thresh:
        loss,grad = hinge_loss(w,x,y)
        delta = loss0-loss
        loss0 = loss
        grad_dir = grad/np.linalg.norm(grad)
        w = w-step*grad_dir/step_num
        ws = np.hstack((ws,w.reshape((2,1))))
        step_num += 1
    return np.sum(ws,1)/np.size(ws,1)

def test1():
    # sample data points
    x1 = np.array((0,1,3,4,1))
    x2 = np.array((1,2,0,1,1))
    x  = np.vstack((x1,x2)).T
    # sample labels
    y = np.array((1,1,-1,-1,-1))
    w = grad_descent(x,y,np.array((0,0)),0.1)
    loss, grad = hinge_loss(w,x,y)
    plot_test(x,y,w)

def plot_test(x,y,w):
    plt.figure()
    x1, x2 = x[:,0], x[:,1]
    x1_min, x1_max = np.min(x1)*.7, np.max(x1)*1.3
    x2_min, x2_max = np.min(x2)*.7, np.max(x2)*1.3
    gridpoints = 2000
    x1s = np.linspace(x1_min, x1_max, gridpoints)
    x2s = np.linspace(x2_min, x2_max, gridpoints)
    gridx1, gridx2 = np.meshgrid(x1s,x2s)
    grid_pts = np.c_[gridx1.ravel(), gridx2.ravel()]
    predictions = np.array([np.sign(np.dot(w,x_)) for x_ in grid_pts]).reshape((gridpoints,gridpoints))
    plt.contourf(gridx1, gridx2, predictions, cmap=plt.cm.Paired)
    plt.scatter(x[:, 0], x[:, 1], c=y, cmap=plt.cm.Paired)
    plt.title('total hinge loss: %g' % hinge_loss(w,x,y)[0])
    plt.show()

if __name__ == '__main__':
    np.set_printoptions(precision=3)
    test1()
Алекс Креймер
источник
Это касается бинарной классификации. Не могли бы вы дать вывод для градиента мультиклассовой классификации с использованием потери шарнира?
Шямкхадка
1

Я исправил твой код. Основная проблема - это ваше определение функций hinge и d_hinge. Они должны применяться один образец за один раз. Вместо этого ваше определение объединяет все выборки, прежде чем брать максимум.

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-t(t(c(1,1,-1,-1)))
    w<-matrix(0, nrow=ncol(x))


    print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w,collapse=',')))
    }
}

#Hinge loss
hinge<-function(w,xr,yr) max(1-yr*xr%*%w, 0)
d_hinge<-function(w,x,y){ dw<- apply(mapply(function(xr,yr) -yr * xr * (yr * xr %*% w < 1),split(x,row(x)),split(y,row(y))),1,sum); dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

Мне нужно n = 10000, чтобы сходиться.

[1] "потери: 0,090000, xw: 1,08999999999995,0,909999999999905, -1,190000000008, -1,69000000000011" [1] "потери: 0,100000, xw: 1,33999999999995,1,1199999999999, -0,900000000000075, -1,400000000, -1,400000000, -1,400000000, -1,400000000, -1,4000000, 10000000000, -1,400000000, 10000000000, 10000000000, 10000000000 0,939999999999948,0,829999999999905, -1,32000000000007, -1,77000000000011 [1] "потеря: 0,240000, XW: 1.49999999999995,1.2099999999999, -0,760000000000075, -1,33000000000011" [1] "потеря: 0,080000, XW: 1.09999999999995,0.919999999999905, -1,18000000000007, -1,68000000000011" [1] «потеря: 0,110000, XW: 1.34999999999995,1.1299999999999, -0,890000000000075, -1,41000000000011"[1] "потери: 0,210000, xw: 0,949999999999948,0,839999999999905, -1,31000000000007, -1,76000000000011" [1] "потери: 0,380000, xw: 1,65999999999995,1,2999999999999, -0,62000000000074: 0,0000: 1: 100: 100000000000000000000000000000000000000000000000000000000000000000 1,25999999999995,1,0099999999999, -1,04000000000008, -1,59000000000011 "[1]" Потеря: 0,000000, xw: 1,25999999999995,1,0099999999999, -1,04000000000008, -1,59000000000011 "

Джон Цзян
источник
3
Народы, градиентный спуск - это почти НАИБОЛЬШИЙ алгоритм оптимизации, который есть, и его следует использовать только тогда, когда нет выбора. Квазиньютоновский алгоритм поиска области доверия или поиска линии, использующий значение целевой функции и градиент, унесет градиентный спуск из воды и намного более надежно сходится. И не пишите свой собственный решатель, если вы не знаете, что делаете, что делают очень немногие.
Марк Л. Стоун
2
Я бы согласился с обоими утверждениями. Однако градиентный спуск с различными вариантами намного проще реализовать в распределенной среде, по крайней мере, в соответствии с доступными библиотеками с открытым исходным кодом.
Джон Цзян