Не понял комментарий. На каком множестве и для чего вы вводите топологию? На множестве предикатов? Строк? Можете дать ссылку на более формальную постановку? И, пожалуй, лучше не сюда а личным сообщением, т.к. совсем далеко от темы статьи.
Это известная проблема. Рассматривается в ответвлении машинного обучения под названием Algorithmic Learning Theory. Две постановки:
1. Найти минимальный DFA соответствующий конечному набору позитивных и негативных примеров. Для этой задачи не существует полиномиального алгоритма.
2. Найти минимальный DFA при наличии оракула, который может давать позитивные примеры, а также проверить выученный автомат, а иначе выдать контрпример. Не самая реалистичная постановка. Но здесь существует полиномиальный алгоритм.
Первая проблема называется «Minimum consistent DFA learning problem». Вторую можно погуглить по «Learning Regular Sets from Queries and Counter-Examples» Dana Angluin.
Есть еще один взгляд на проблему: identification in the limit. По сути первый формальный фреймворк машинного обучения. Но там постановка совсем далека от практических задач.
Про совсем свежие результаты сказать к сожалению не могу.
Вы все меня толкаете к формулировке функции потерь в явном виде. Так не интересно.
Вы хотите найти одно вещественное число, которое бы удовлетворяло… Чему? Как только вы ответите на этот вопрос, ваша норма выбрана.
Это верно. Но выбирая норму вы делаете неявное допущение о природе ошибки. В вашей задаче о линейке я бы предположил какое-то распределение ошибки, и потребовал чтобы модель, производящая точку, удовлетворяла бы принципу максимального правдоподобия.
Вы бы не смогли получить хорошую оценку в вашем примере с линейкой методом наименьших квадратов, если бы я добавил условие, что ошибка смещена. Скажем, у измерителя есть склонность к завышению.
Для предыдущего вопроса: L = E|f(xi) — yi| (E — математическое ожидание, i проходит по известным точкам)
Пусть будет полином третьей степени. Входные данные — пары <метка времени, курс>. Задача — восстановить функцию в тех точках времени, где нет значений курса. Классическая регрессия.
Вобщем, вы правильно сказали. Извините, запутался в терминологии с непривычки. Возведение в квадрат — это техническая штука.
Просто мне кажется важным, откуда вылезает евклидова норма.
Еще раз. Вы сказали что для расчета аппроксимирующей функции будете использовать квадрат L2. Но не дали обоснования, вообще. Я хочу это прояснить.
Пример задачи: я хочу предсказать значения курса доллара в те часы, когда мне он не был виден по доступным данным. L2? L1? может быть совершенно иная норма?
Это не ответ. Многие кусочно-линейные функции дадут вам строгое решение. Да и те что дадут множество, все равно будут минимизировать функцию. Почему вы считаете, что концепция центра масс здесь будет лучше работать?
Вы не правы. Оптимизация абсолютной длины ведет к другому оптимуму. Это не "технический" момент, а довольно принципиальный. Предполагая нормальную аддитивную ошибку вокруг для аппроксимирующей функции вы приходите к квадрату евклидовой нормы.
Возьмем линейную регрессию для функции f(a) = ax. Пусть для простоты будет всего лишь один параметр. Пусть даны точки (0,0), (1,1), (2,2), (3,9), (4,4).
Вы хотите сказать, что минимум функции
|a-1| + |2a-2| + |3a-9| + |4a-4|
будет эквивалентен минимуму
(a-1)^2+ (2a-2)^2 + (3a-9)^2 + (4a-4)^2?
Это не так. Можно вобщем-то показать аналитически, рассмотрев sum |ax+b-y| и sum (ax+b-y)^2 где индексы пробегают x,y и a,b — переменные. Я так и не научился на хабре формулы писать...
Она отлично работает, пока у вас нет выбросов. Строже говоря, пока ваши точки генерируются гауссовским распределением. Как только это нарушается, решение дает большие ошибки.
ax + b — тоже гладкая (если я не совсем забыл анализ). Но вы же не ее начали оптимизировать.
1. Найти минимальный DFA соответствующий конечному набору позитивных и негативных примеров. Для этой задачи не существует полиномиального алгоритма.
2. Найти минимальный DFA при наличии оракула, который может давать позитивные примеры, а также проверить выученный автомат, а иначе выдать контрпример. Не самая реалистичная постановка. Но здесь существует полиномиальный алгоритм.
Первая проблема называется «Minimum consistent DFA learning problem». Вторую можно погуглить по «Learning Regular Sets from Queries and Counter-Examples» Dana Angluin.
Есть еще один взгляд на проблему: identification in the limit. По сути первый формальный фреймворк машинного обучения. Но там постановка совсем далека от практических задач.
Про совсем свежие результаты сказать к сожалению не могу.
Но не сказал бы что что-то интересное или прорывное там было.
blog.aboutamazon.com/transportation/whats-next-for-amazon-scout
MLE оценка для черных лебедей (оцениваем матожидание mu):
mu = N_black / (N_white + N_black) = 0/100 = 0MAP оценка для черных лебедей, при условии бета-распределения на параметр mu B(alpha=5, beta=5):
mu = (N_black + alpha - 1) / (N_white + N_black + alpha + beta - 2) = (0 + 5 - 1) / (100 + 5 + 5 - 2) = 0.0370..То есть вероятность низка, но не нулевая.
ps спасибо за статью. Редко на хабре появляется байесовская статистика.
Это верно. Но выбирая норму вы делаете неявное допущение о природе ошибки. В вашей задаче о линейке я бы предположил какое-то распределение ошибки, и потребовал чтобы модель, производящая точку, удовлетворяла бы принципу максимального правдоподобия.
Вы бы не смогли получить хорошую оценку в вашем примере с линейкой методом наименьших квадратов, если бы я добавил условие, что ошибка смещена. Скажем, у измерителя есть склонность к завышению.
Для предыдущего вопроса: L = E|f(xi) — yi| (E — математическое ожидание, i проходит по известным точкам)
Про энергию не понял. Мы вроде как о других моделях.
Просто мне кажется важным, откуда вылезает евклидова норма.
Пример задачи: я хочу предсказать значения курса доллара в те часы, когда мне он не был виден по доступным данным. L2? L1? может быть совершенно иная норма?
Ну так почему евклидова норма? :)
Вы хотите сказать, что минимум функции
|a-1| + |2a-2| + |3a-9| + |4a-4|
будет эквивалентен минимуму
(a-1)^2+ (2a-2)^2 + (3a-9)^2 + (4a-4)^2?
Это не так. Можно вобщем-то показать аналитически, рассмотрев sum |ax+b-y| и sum (ax+b-y)^2 где индексы пробегают x,y и a,b — переменные. Я так и не научился на хабре формулы писать...
ax + b — тоже гладкая (если я не совсем забыл анализ). Но вы же не ее начали оптимизировать.