Стандартная библиотека C++ (2015)

Разумеется, но чуть позже.

Говорят, что бедные студенты группы 3.1 никак без примера даже приступить к решению задачи не могут. Ну, я расстарался. НО в связи с тем, что спать хочется ого-го как, я полагаю, что качество могло пострадать :smile: Пример советую визуализировать на плоскости.

PS: Советую для отлова ошибок и сравнения иметь и параллельную версию программы и последовательную. В ejudge отправляем только параллельную!

Я потестил, и получилось очень интересная штука: нужно уточнить, как вычислять частную производную от максимума. (например, f(x,y) = max(0, ax+by))

Если брать (пусть по x) что-то такое:

if ax+by > 0: return a else: return 0

Получается один выход (у меня - все нули) Если строгое неравенство заменять на нестрогое, получается совершенно другой результат, подходящий под ответ (все единицы). Добавление всяких проверок точности дает третий, отличающийся результат (единицы и нули перемешано) :slight_smile:

И значения функции потерь тоже скачут лихо из-за этого.

clang++ -stdlib=libc++ -o solution src/SVM.o src/Matrix.o src/main.o /usr/bin/ld: src/Matrix.o: undefined reference to symbol ’pthread_setspecific@@GLIBC_2.2.5’ //lib/x86_64-linux-gnu/libpthread.so.0: error adding symbols: DSO missing from command line clang: error: linker command failed with exit code 1 (use -v to see invocation)

Вроде -lpthread не хватает в строке компиляции.

Ага, питон детектед! Писать прототип на питоне - разумный шаг.

Теперь перейдем к проблеме. Думаю, это вопрос реализации. Строго говоря, должно быть сравнение вещественных чисел на больше. А значит, д.б. что-то типа +эпсилон. Но давайте договоримся, что в этой проверке должно быть строгое неравенство ровно так как написано у Димы.

Поясню свое решение. Дело в том, что процесс должен сходиться к некоторому решению. Причем очевидно, что если Вы слегка меняете параметры, то минимум все равно должны найти тот же (с некоторой точностью). Тут, конечно, еще от невязки матрицы кое-что зависит (проходили по численным методам?) Но для нас важна воспроизводимость результатов. Именно поэтому я начальное приближение задаю, а не предлагаю Вам генерировать случайно. И потому же, мы зафиксируем эту особенность алгоритма.

PS: Спасибо, треды добавлю.

По-моему, от погрешности тут как раз-таки очень и многое слетает.

Написал одно и тоже на питоне (с numpy) и плюсах (с самопальными матрицами). На первых шагах матрицы совпадают, совпадает значение функции потерь и градиенты.

На тысячном шаге матрицы различаются уже в четвертом знаке каждой компоненты. После 5000 шагов матрицы различаются во втором(третьем) знаках. И норма разности получилась 0.08

Значения функции потерь отличаются почти в два раза в этих двух реализациях и почти в десять раз относительно того, что указано в примере (в меньшую сторону).

В общем, беда какая-то, но предсказывает верно и для других примеров: (6, 6) -> 0; (8,7) -> 0

Не знаю, как будет с воспроизводимостью результатов, но такие различия в значениях целевой функции мне не нравятся.

Дима, Вы драматизируете. Есть теория сходимости, которая учитывает понятие погрешности. Если метод хорошо сходится, то нужна очень большая погрешность, чтобы ему помешать.

Что касается нашего случая, то разница между плюсами и питоном может быть обусловена кучей факторов: настройки FPU, реализация операций, использованные Вами разные операции на том и другом языке. Нет, смысла сейчас в этом копаться и хорошо, что Вы сейчас с этим столкнулись в жизни. Предупрежден - значит вооружен )))

Я подозревал наличие такой проблемы. Именно поэтому я написал, что значение функции ошибки сравнивать не буду. И мы всегда можем добавить пару тысяч шагов для лучшей сходимости.

Градиент по просьбе трудящихся:

def grad(W, X, Y, lmbd):
        ret = np.ndarray(W.shape) # градиент - матрица того же размера, что и W
        tmp = np.dot(W,X)  # перемножим матрицы W и X, чтобы брать (W*x_i)j
 
        for i, y in enumerate(Y): # итерация по вектору ожидаемых классов для соответствующих образов
            for j, line in enumerate(tmp): # итерация по строкам матрицы tmp
                if j != y and line[i] - tmp[y][i] > -1:
                    for p, x in enumerate(X): # итерация по строкам матрицы распознаваемых образов
                        ret[j][p] += x[i]
                        ret[y][p] -= x[i]
    
        return ret / len(Y) + W * (2*lmbd)

UPD: поправлено

а можно на плюсах пожалуйста?

Не надо на плюсах. Я просил Вас вообще самостоятельно вывести формулу. Хотя бы с питона переложите, самостоятельно!

Сегодня с 15:00 буду на мехмате. До этого времени доделываю тесты и формулирую все до конца.

Цикл вычисления градиента:

dL = np.zeros_like(W) # initialize the gradient as zero 
for i in xrange(num_samples):
        scores = W.dot(X[:,i])
        correct_class_score = scores[y[i]]
        mask = np.zeros(num_classes)
        for j in xrange(num_classes):
            if j == y[i]:
                continue
            margin = scores[j] - correct_class_score + 1. # note delta = 1
            if margin > 0:
                mask[j] = 1
        for c in xrange(num_classes): 
            if y[i] == c:
                dL[c, :] -= X[:, i] * np.sum(mask)
            else:
                dL[c, :] += X[:, i] * mask[c]
    dL /= float(num_samples)
    dL += 2* self.lambda_param * W  

PS: третий курс, возьмите курс по матану в следующем году

Так граждане, я смогу только в субботу. Записываемся сюда.

Сейчас внесу последние изменения в условие на ejudge. Связаны они с тем, что сделать даже 1 нормальный пример оказалось целой исследовательской работой. Времени нет ни у меня, ни у Вас, так что будем упрощать.