Расскажите случаи, когда вам действительно очень помогло знание алгоритмов
Определение квантилей по потоку данных (например, 95-й персентиль). Нельзя просто хранить все данные, потом сортировать — слишком много данных по сравнению с памятью. Недостаточно хранить среднее и стандартное отклонение — данные не следуют нормальному распределению. Персентили не обязаны быть идеально точными.
Определение стартового сигнала (писк примерно известной частоты и длительности) в оцифрованном звуке с микрофона.
Система рекомендаций. Есть длинный список товаров с разными признаками, длинный список пользователей с историей (кто какие товары покупал) и функция похожести одного товара на другой (по признакам товара). Реализация в лоб (сравнивать всех со всеми) дохнет при росте размера списков, потому что O(N^2).
Автодополнение текста поискового запроса. Есть словарь возможных слов и словосочетаний с весами и некоторыми правилами, разбитый по категориям, искать по которому надо быстро и даже при наличии опечаток в запросе.
Кажется, что это стандартные задачи и для них есть готовые решения, но на практике получалось что ни одно из них не подходит (не тот язык, слишком тяжёлое — много зависимостей, не хватает гибкости, слишком сложное — долго разбираться, лицензионная чистота и так далее).
Хорошо, давайте с другой стороны подойдём. Приведите пример нелинейной модели. А я таким же образом найду внутри неё линейную операцию и заявлю, что модель тоже линейная.
Вот например нейронная сеть с десятью уровнями и гиперболическим тангенсом в качестве функции активации — это линейная модель или нелинейная?
Похоже, что уже нет. Майкл Редмонд (очень сильный профессионал, который комментирует матчи) характеризует некоторые ходы AlphaGo как странные, и только дальше по ходу матча выясняется, какая от этих ходов польза.
Кроме того, человеческая стратегия отличается от компьютерной, и похоже что это одна из причин, которая позволяет AlphaGo показывать такой хороший результат. Например, AlphaGo не пытается нарастить своё преимущество. Выигрыш на камень с вероятностью 90% для неё лучше выигрыша на пять камней с вероятностью 89%. Человек обычно пытается выиграть с некоторым запасом.
Есть разница между "analogous to" и "is". Логистическая регрессия линейна только до линк-функции. Попробуйте посчитать коэффициенты логистической регрессии методом наименьших квадратов (который отлично работает для линейной модели) и посмотрите, что из этого получится.
Логистическая регрессиия — нелинейная модель. У линейной модели f(a+b) = f(a) + f(b). У логистической регрессии это свойство не выполняется из-за кривизны логисты.
Конечно подвержены. Берём обучающую выборку с 10 наблюдениями и 9 независимыми переменными, подгоняем линейную регрессию, получаем нулевую ошибку. Проверяем на другой выборке и видим, что ошибка совсем не нулевая.
если торпеда плывет правее чем нужно ей будут посылать команду повернуть влево до тех пор, пока траектория не выровняется
Именно так работала система наведения советских зенитных ракет, которые использовались во Вьетнаме против американских бомбардировщиков. А потом американцы начали слушать сигналы на частотах, используемых системой наведения, и передавать их обратно в эфир с задержкой. И так несколько раз.
Система наведения подаёт ракете команду "повернуть влево на один градус", а ракета слышит "повернуть влево на один градус, повернуть влево на один градус, повернуть влево на один градус".
Структурировать надо самостоятельно. Для этого реддит разбит на подреддиты. Умолчательный набор подреддитов интересен среднестатистическому пользователю, то есть мало кому.
К сожалению, подреддитов очень много и соотношение сигнал/шум низкое, поэтому приходится много времени потратить, чтобы найти приемлемое подмножество.
Ожидаемый результат, наблюдаем совместно действие двух законов:
Закон Меткалфа — полезность сети пропроциональна квадрату числа участников. Была полезность 1, поделили ресурс на три части, получили полезность 3 * (1/9) = 1/3.
Если вероятностное O(1) на вставку не устраивает, существует деамортизированный вариант: "In this work we follow Kirsch and Mitzenmacher and present a de-amortization of cuckoo hashing that provably guarantees constant worst case operations."
выдавать новым пользователям (при регистрации) и уже существующим сплит-группу в диапазоне от 1 до 2400 случайным образом.
лежат подводные грабли. Через какое-то время вы будете при тестировании новых фич видеть результаты предыдущих тестов, часто смешанных и запутанных.
Надо по крайней мере делать t-test перед началом каждого теста и постоянно гонять A/A тесты.
Ну и новый хеш посчитать для каждого нового теста не может быть неприемлемо долго. Ошибочные результаты тестирования из-за повторного использования сплит-групп обойдутся гораздо дороже.
Всё равно мало разнообразия. Тут все модели по сути одинаковые — одна и та же линейная регрессия, отличие только в коэффициентах. Можно посчитать корреляцию между коэффициентами и она наверняка получится весьма сильной, то есть предсказывают они почти одно и то же почти одинаковым способом.
А от ансамблей больше всего пользы, когда модели в ансамбле принципиально разные — регрессия, деревья, ближайший сосед, адабуст, экспертная оценка, больцмановские машины и так далее. Каждая сходит с ума по-своему, но на среднее значение заскоки отдельных моделей мало влияют.
Ансамбли хорошо работают не просто потому, что у них внутри много моделей, а потому что у них внутри много разных моделей. Например, в случайном лесе отдельные деревья специально выращивают на разных подмножествах независимых переменных.
Чем более кардинально отличаются модели в ансамбле, тем больше пользы от усреднения их результатов. У очень разных моделей ошибки скорее всего в разных местах, поэтому с добавлением новых моделей сигнал растёт пропорционально количеству моделей, а шум — пропорционально корню их количества, отсюда и выигрыш.
А если модели примерно одинаковые, то и ошибки у них тоже примерно одинаковые и сигнал с шумом растут вместе.
То, что вы описали, не очень похоже на усреднение. Даже если правильно переставить делали, кроме одного хорошего молотка получится два плохих. Чтобы выбрать из трёх молотков хороший, надо обладать знанием, которое модели недоступно.
Определение квантилей по потоку данных (например, 95-й персентиль). Нельзя просто хранить все данные, потом сортировать — слишком много данных по сравнению с памятью. Недостаточно хранить среднее и стандартное отклонение — данные не следуют нормальному распределению. Персентили не обязаны быть идеально точными.
Определение стартового сигнала (писк примерно известной частоты и длительности) в оцифрованном звуке с микрофона.
Система рекомендаций. Есть длинный список товаров с разными признаками, длинный список пользователей с историей (кто какие товары покупал) и функция похожести одного товара на другой (по признакам товара). Реализация в лоб (сравнивать всех со всеми) дохнет при росте размера списков, потому что O(N^2).
Автодополнение текста поискового запроса. Есть словарь возможных слов и словосочетаний с весами и некоторыми правилами, разбитый по категориям, искать по которому надо быстро и даже при наличии опечаток в запросе.
Кажется, что это стандартные задачи и для них есть готовые решения, но на практике получалось что ни одно из них не подходит (не тот язык, слишком тяжёлое — много зависимостей, не хватает гибкости, слишком сложное — долго разбираться, лицензионная чистота и так далее).
Вот например нейронная сеть с десятью уровнями и гиперболическим тангенсом в качестве функции активации — это линейная модель или нелинейная?
Кроме того, человеческая стратегия отличается от компьютерной, и похоже что это одна из причин, которая позволяет AlphaGo показывать такой хороший результат. Например, AlphaGo не пытается нарастить своё преимущество. Выигрыш на камень с вероятностью 90% для неё лучше выигрыша на пять камней с вероятностью 89%. Человек обычно пытается выиграть с некоторым запасом.
Конечно подвержены. Берём обучающую выборку с 10 наблюдениями и 9 независимыми переменными, подгоняем линейную регрессию, получаем нулевую ошибку. Проверяем на другой выборке и видим, что ошибка совсем не нулевая.
Можно, конечно, только не нужно. Специально для предсказания вероятности существует логистическая регрессия.
Линейная модель может выдать оценку вероятности меньше 0 или больше 1, и что потом с этим делать?
Именно так работала система наведения советских зенитных ракет, которые использовались во Вьетнаме против американских бомбардировщиков. А потом американцы начали слушать сигналы на частотах, используемых системой наведения, и передавать их обратно в эфир с задержкой. И так несколько раз.
Система наведения подаёт ракете команду "повернуть влево на один градус", а ракета слышит "повернуть влево на один градус, повернуть влево на один градус, повернуть влево на один градус".
К сожалению, подреддитов очень много и соотношение сигнал/шум низкое, поэтому приходится много времени потратить, чтобы найти приемлемое подмножество.
Закон Меткалфа — полезность сети пропроциональна квадрату числа участников. Была полезность 1, поделили ресурс на три части, получили полезность 3 * (1/9) = 1/3.
Откат к очень среднему значению — всё выдающееся рано или поздно перестаёт быть выдающимся.
лежат подводные грабли. Через какое-то время вы будете при тестировании новых фич видеть результаты предыдущих тестов, часто смешанных и запутанных.
Надо по крайней мере делать t-test перед началом каждого теста и постоянно гонять A/A тесты.
Ну и новый хеш посчитать для каждого нового теста не может быть неприемлемо долго. Ошибочные результаты тестирования из-за повторного использования сплит-групп обойдутся гораздо дороже.
А от ансамблей больше всего пользы, когда модели в ансамбле принципиально разные — регрессия, деревья, ближайший сосед, адабуст, экспертная оценка, больцмановские машины и так далее. Каждая сходит с ума по-своему, но на среднее значение заскоки отдельных моделей мало влияют.
Чем более кардинально отличаются модели в ансамбле, тем больше пользы от усреднения их результатов. У очень разных моделей ошибки скорее всего в разных местах, поэтому с добавлением новых моделей сигнал растёт пропорционально количеству моделей, а шум — пропорционально корню их количества, отсюда и выигрыш.
А если модели примерно одинаковые, то и ошибки у них тоже примерно одинаковые и сигнал с шумом растут вместе.