Комментарии 80
Я думаю развитие квантовых компьютеров это не остановит, а вот рекомендации станут лучше гораздо быстрее. Все в выигрыше!
Если теперь, благодаря Тану, эта сложность уменьшится, то как бы это не стало концом самой идеи рекомендательных сервисов. Заспамят же.
А по факту автор не прав, т. к. прогресс можно достигать двумя путями — улучшая железо и улучшая алгоритмы. Правда во втором случае это нужно делать много раз, но важно совмещать оба пути.
Если производство железки позволит сэкономить на производстве алгоритмов, то можно делать железку (если она вообще возможна), и тогда она сама себя окупит. Но пока железку никто не делает, мы либо пишем алгоритмы, либо платим за железо (но чаще всего железо не спасёт).
Теперь компьютеры как люди в свое время перейдут на расчеты логарифмами для уменьшения объема вычислений
Да, когда-то инженеры использовали логарифмическую линейку или таблицы логарифмов, чтобы умножать за неимением калькулятора большие числа приближенно. И это никак не связано с логарифмической сложностью алгоритмов, кроме самой функции логарифма. Короче комментатор не в то небо пальцем попал.
Да, можно и так решать. Более того, таких рекомендаций от старожилов сколько угодно. Просто это решение менее качественное, оно не учитывает специфичные интересы. Старожил предложит похожий фильм по смыслу, например, а посетителю интересен какой-то герой второго плана.
У алгоритма нет такой проблемы. Во всяком случае не у любого.
Если пользователь знает что именно он хочет — он идет и пользуется поиском. Рекомендации нужны для случая когда не знаешь точно что нужно, либо когда активно не ищешь вообще. И в таких случаях нет проблемы "пользователь хотел эпизодического актера". А в случае когда человек фанатеет от конкретного актера, то это как раз алгоритм может выяснить если у него будет достаточно данных.
Зато можно провести кластеризацию координат пользователей в n-мерном пространстве, где n — это количество фильмов, которые смотрели все пользователи из некоторой выборки (пусть N — полное число всех фильмов: n<<<N). Берём k пользователей, каждый из которых смотрел все n конкретных фильмов, кластеризуем их в n-мерном пространстве с использованием какой-нибудь нормирующей функции (например по Евклидовому расстоянию) и ищем к какой группе ближе всего по такой же норме наш пользователь. Когда опрелеим его группу, можно семело рекомендовать ему всё, что понраилось его группе, и чего он еще не видел.
Я так понимаю, что людей много (K>>>k), фильмов много и у каждого человека свой уникальный набор фильмов. Однако людей с очень похожим набором фильмов не так много, всегда есть tradeoff в размере выборки 1..N. Очевидно, что все N фильмов не смотрел вообще никто, а выборка из 1 фильма очевидно не будет показательной.
Честно сказать в этой статье не хватает именно объяснения суть проблемы, и почему здесь хотели применять квантовые вычисления.
Подросток из Техаса
Ювин ТанШутка про то, что его система рекомендаций использует не столь удачливых соотечественников, оставшихся на родине и рекомендующих тысячу фильмов за два доллара, уже была?
Я начал верить в существование классического алгоритма
попахивает… не очень…
Какая разница, как это "попахивает", если в итоге он выдал строгое доказательство? Он же верил, что его можно найти и искал, а не говорил "я верю и этого достаточно, вам тоже нужно просто верить".
Неверящий сделает мало или ни одной попытки
Верящий — сделает очень много попыток, зависит от фанатизма и веры. Фанатик будет долбится об один и тот же метод, даже если он неверен, творческий человек придумает, в том числе, другие методы, креативный человек один метод по-разному приспособит, специалист по продажам или проповедник заставит верить других людей, чтобы они делали попытки.
И т.д.
Изобрести лекарство от рака — творческая задача, но не креативная.
Словарь Ожегова-Шведовой определяет творчество как «создание новых по замыслу культурных или материальных ценностей». В этом определении объединены как духовные, моральные, высокие, так и материальные, бытовые ценности.
Творчество создает, а креатив — продает.
Но некоторые считают, что креатив больше значит, чем творчество. В современном мире, где деньги правят балом — умение продать ценится выше умения создать.
— Пойдёшь ко мне в штат?
Татарский ещё раз посмотрел на плакат с тремя пальмами и англоязычным обещанием вечных метаморфоз.
— Кем? — спросил он.
— Криэйтором.
— Это творцом? — переспросил Татарский. — Если перевести?
Ханин мягко улыбнулся.
— Творцы нам тут на хуй не нужны, — сказал он. — Криэйтором, Вава, криэйтором.
Ну, это не самый плохой запах, потому что за верой лежит интуиция. Если вы не верите в свою интуицию — ну, беда…
Интуиция помогла найти ответ, а вера в свои силы помогла его искать.
Все еще плохо пахнет?
NB! Я написал вера, а не религия.
Мы предполагаем, что матрица A — низкого ранга. По-человечески, это означает, что все строки матрицы A[:,j] (что есть оценки человека j выставленные всем существующим фильмам) являются линейной комбинацией небольшого набора «фенотипов», A[:, j] = a1 * v1 + a2 * v2 +… + aN * vN, где «a» — какие-то коэффициенты, а «v» — вектора, характеризующие «типичного любителя блокбастеров», «типичного любителя комедий» и т. п. Ключевое предположение — что N много меньше и фильмов и людей, а каждый анонимус выставляет уникальный, но типичный и предсказуемый набор оценок.
Под решением задачи понимается нахождение «a» и «v». Это можно сделать классически за линейное время O(Ni, Nj) и квантово — за логарифмическое O(log(Ni), log(Nj)). Очевидно, нахождение всех элементов матрицы A возможно не меньше, чем за линейное время, но, похоже, это не требуется по условиям задачи. Чтобы рекомендовать конкретный фильм конкретному пользователю, будут использоваться какие-то другие приближения.
ИМХО многие специалисты из самых разных областей посмеются этой возне с линейной-логарифмической сложностью, поскольку большая часть задач, которые нам хочется решить, имеют экспоненциальную сложность.
А то, что пишется во введении — это личное мнение автора, так к этому и относитесь.
Предложите ему заняться проблемой антигравитации.
– и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.
а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных.
Видимо да. И да, из булки тоже можно сделать троллейбус :)
а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных
Так нет же! Именно квантовый алгоритм, на основании которого проводилась работа, расчитан на нахождение не наилучшего решения, а "достаточно неплохого" и именно поэтому квантовый алгорим теоретически был экспоненциально быстрее. Об этом прямо в статье так и написано.
Процитированное вами упрощение алгоритма было сделано как раз в квантовой версии. Насколько я понял, версия Тана не уступает по качеству рекомендаций
Получить паспорт можно и в полтора года (загранпаспорт вроде с года дают), ни к подростковости, ни к тинейджерству, ни к совершеннолетию это отношения не имеет. Уголовная ответственность — тем более.
Подростком и совершеннолетним быть, наверное, нельзя (хотя подросток не имеет точного возрастного определения, это во многом культурально-обусловленное понятие). Тинейджером и совершеннолетним — почему нет?
Хотя так редко говорят разве что по приколу.
Юноша бледный со взором горящим
Ныне тебе я даю три совета…
teenager
13 — thirteen
…
19 — nineteen
20 — twelve
Все это очень сильно похоже на обычный метод ближайших соседей (nearest neighbors, https://en.m.wikipedia.org/wiki/Nearest_neighbor_search). Есть алгоритмы, которые обеспечивают точный поиск ближайших соседей, но это очень ресурсоемко. А есть алгоритмы приближенного поиска, время работы которых как раз логарифмически зависит от количества входных данных. Но и результат получается не точный, а приближенный. Есть куча фреймворков, которые давно уже умеют это делать.
Позже одни компании только на суде признаются, что они намеренно замедляли квантовые процессоры до уровня калькуляторов; другие компании будут запрещать публиковать результаты бенчмарков; третьи будут искать и таки находить критичные уязвимости, когда квантовые процессоры могут получить «случайное квантовое запутывание» во время производства или во время транспортировки, причем это будет работать как квантовая связь с третьими лицами без возможности засечь и все данные будут оказываться у
Игроделы также не будут отставать — полностью забьют на оптимизацию и будут выпускать игры с 16М-текстурами даже иконок, которые еле заметны на самых лучших мониторах 32к! Если пользователей игра будет лагать и жутко тормозить — попросят приобрести более новое железо.
Короче, процветание индустрии. И где-то я это уже видел…
Серьёзному успеху в квантовых вычислениях помешал подросток