Комментарии 80

Я думаю развитие квантовых компьютеров это не остановит, а вот рекомендации станут лучше гораздо быстрее. Все в выигрыше!

У рекомендательных сервисов кроме проблемы вычисления рекомендаций есть ещё проблема накрутки. Она катастрофична для сервисов с открытыми рекомендациями (зная все рекомендации некоего заданного пользователя, бот-злоумышленник выставляет в точности такие же плюс рекомендацию рекламируемого предложения), но считалось, что при закрытых оценках такой проблемы нет. Зондирование же рекомендательных сервисов в поисках крупных групп единомышленников и их предпочтений раньше было ограничено вычислительной сложностью задачи.
Если теперь, благодаря Тану, эта сложность уменьшится, то как бы это не стало концом самой идеи рекомендательных сервисов. Заспамят же.
Теперь компьютеры как люди в свое время перейдут на расчеты логарифмами для уменьшения объема вычислений, то есть алгоритмом будет решать вопрос несовершенства железа, это никак не остановит развитие квантовых компьютеров.
На расчёты за что они перейдут логарифмами? За электроэнергию? Вы не спутали O большое с самими алгоритмами? (далеко не всё можно упростить по аналогии с рекомендациями).
Автор имел ввиду, что вместо того, чтобы компьютеры работали невероятно быстрее, программисты вынуждены писать быстрые алгоритмы. Вот только он не учёл, что для квантового алгоритмы ещё сложнее =)  Да и применимы только к некоторым задачам.

А по факту автор не прав, т. к. прогресс можно достигать двумя путями — улучшая железо и улучшая алгоритмы. Правда во втором случае это нужно делать много раз, но важно совмещать оба пути.
*важно совмещать оба пути, т. к. первый путь тоже непростой, и тоже требует алгоритмов. А по факту так, как подсказывает рыночная ситуация. Если дешевле сделать железку, можно взять и более медленный алгоритм, а деньги потратить на железку. Но, думаю, сделать алгоритм проще, чем сделать фантастическую железку.

Если производство железки позволит сэкономить на производстве алгоритмов, то можно делать железку (если она вообще возможна), и тогда она сама себя окупит. Но пока железку никто не делает, мы либо пишем алгоритмы, либо платим за железо (но чаще всего железо не спасёт).
Нет, похоже автор имел в виду всё же логарифмическую линейку, а не то, что вы написали.
Теперь компьютеры как люди в свое время перейдут на расчеты логарифмами для уменьшения объема вычислений

Да, когда-то инженеры использовали логарифмическую линейку или таблицы логарифмов, чтобы умножать за неимением калькулятора большие числа приближенно. И это никак не связано с логарифмической сложностью алгоритмов, кроме самой функции логарифма. Короче комментатор не в то небо пальцем попал.
Для сервисов рекомендаций можно было бы сделать по-другому. Просто попросить пользователей-старожилов после просмотра фильма перечислить, какие бы фильмы, на их взгляд, стоило бы посмотреть другим людям, которым этот фильм понравится. За это предложить им какой-нибудь маленький бонус. Всё!
не всё так просто. Это очень много данных, которые нужно обрабатывать правильно

Да, можно и так решать. Более того, таких рекомендаций от старожилов сколько угодно. Просто это решение менее качественное, оно не учитывает специфичные интересы. Старожил предложит похожий фильм по смыслу, например, а посетителю интересен какой-то герой второго плана.

Потому что проблема что старожилов, что алгоритма вместо них, в том, что анализируется выборка по критериям, заранее определённым кем-то другим, но не самим пользователем, которому собираются рекомендовать фильм. Вот и получается, что ему подбирают блокбастер/не блокбастер, а он лишь хотел увидеть конкретного эпизодического актёра.

У алгоритма нет такой проблемы. Во всяком случае не у любого.

Если пользователь знает что именно он хочет — он идет и пользуется поиском. Рекомендации нужны для случая когда не знаешь точно что нужно, либо когда активно не ищешь вообще. И в таких случаях нет проблемы "пользователь хотел эпизодического актера". А в случае когда человек фанатеет от конкретного актера, то это как раз алгоритм может выяснить если у него будет достаточно данных.

Подобных ошибок можно избежать, если фильм довольно популярный. Но фильм, от которого я помню маленький отрывок, я так и не нашёл.
Это классическая задача многокритериального выбора. Она не имеет строгих решений. Вернее решений может быть много, в зависимости от того, какой базисный набор приоритетов выбрать. Дело в том, что у пользователей нет строго определенной системы приориетов. Кроме того, выделенные нами формальные критерии — это не те критерии, которыми на самом деле руководствуется пользователь. Пользователь опирается на некоторую суперпозицию критериев, в том числе тех, которые мы не выделяли, причем он сам не отдаёт себе в этом отчета. То есть матрицу коэффициентов ни у какого пользователя не выведать.

Зато можно провести кластеризацию координат пользователей в n-мерном пространстве, где n — это количество фильмов, которые смотрели все пользователи из некоторой выборки (пусть N — полное число всех фильмов: n<<<N). Берём k пользователей, каждый из которых смотрел все n конкретных фильмов, кластеризуем их в n-мерном пространстве с использованием какой-нибудь нормирующей функции (например по Евклидовому расстоянию) и ищем к какой группе ближе всего по такой же норме наш пользователь. Когда опрелеим его группу, можно семело рекомендовать ему всё, что понраилось его группе, и чего он еще не видел.
Я так понимаю, что людей много (K>>>k), фильмов много и у каждого человека свой уникальный набор фильмов. Однако людей с очень похожим набором фильмов не так много, всегда есть tradeoff в размере выборки 1..N. Очевидно, что все N фильмов не смотрел вообще никто, а выборка из 1 фильма очевидно не будет показательной.

Честно сказать в этой статье не хватает именно объяснения суть проблемы, и почему здесь хотели применять квантовые вычисления.
Ага и тысяча старожилов порекомендуют пятьсот разных фильмов :) большая часть из которых пользователю даже не интересна. А надо оценить выборку что понравилось пользователю и на чью выборку из старожилов она похожа, и рекомендовать не просмотренные фильмы из этой выборки. Вот эту задачу и ускорил Тан.
Ну в общем-то логично. Если у вас настолько низкие запросы, что вам понравилось «Боку но Пико», то вам зайдёт вообще что угодно.
Дайте угадаю, вы уже прошли тот самый опрос, за который обещают несколько десятков тысяч ₽ в русскоязычном спаме?
А почему мнение старожил весомее новичков? Мой имхо, но когда посмотрел кучу фильмов, вкус уже сильно отличается от новичков, и советовать им эффективно уже не получится, тут наоборот новички должны советовать новичкам.
Задача сервиса — втягивать пользователей в некую деятельность и показывать им рекламу. А вы всё разрушаете… айяйяй…
Подросток из Техаса
Ювин Тан
Шутка про то, что его система рекомендаций использует не столь удачливых соотечественников, оставшихся на родине и рекомендующих тысячу фильмов за два доллара, уже была?
НЛО прилетело и опубликовало эту надпись здесь
отдает расизмом
Широко известный факт в сфере компьютерной техники:
Computers are racist / компьютеры - расисты

Если бы мне давали пенни и спрашивали, какой фильм стоит посмотреть — разве это не удача?


В обычной жизни и бесплатно никому не навяжешь...

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


попахивает… не очень…

Какая разница, как это "попахивает", если в итоге он выдал строгое доказательство? Он же верил, что его можно найти и искал, а не говорил "я верю и этого достаточно, вам тоже нужно просто верить".

для того, чтобы что-то открыть, нужно верить, что это что-то можно открыть.
Неверящий сделает мало или ни одной попытки
Верящий — сделает очень много попыток, зависит от фанатизма и веры. Фанатик будет долбится об один и тот же метод, даже если он неверен, творческий человек придумает, в том числе, другие методы, креативный человек один метод по-разному приспособит, специалист по продажам или проповедник заставит верить других людей, чтобы они делали попытки.
И т.д.
Чем отличается творческий человек от креативного?
Мороженное в вафельном стаканчике разрезать по диагонали — креативно, но никакого особого творчества, зато дизайн, наценка и продажи.
Изобрести лекарство от рака — творческая задача, но не креативная.

Словарь Ожегова-Шведовой определяет творчество как «создание новых по замыслу культурных или материальных ценностей». В этом определении объединены как духовные, моральные, высокие, так и материальные, бытовые ценности.

Творчество создает, а креатив — продает.
Но некоторые считают, что креатив больше значит, чем творчество. В современном мире, где деньги правят балом — умение продать ценится выше умения создать.
Generation „П“:
— Пойдёшь ко мне в штат?
Татарский ещё раз посмотрел на плакат с тремя пальмами и англоязычным обещанием вечных метаморфоз.
— Кем? — спросил он.
— Криэйтором.
— Это творцом? — переспросил Татарский. — Если перевести?
Ханин мягко улыбнулся.
— Творцы нам тут на хуй не нужны, — сказал он. — Криэйтором, Вава, криэйтором.
Это типичная проблема перевода с английского, в котором слово «believe» переводится не только как «верить», но и как «пологать» или «считать».
Это типичная проблема перевода с английского, что значение перевода из словаря — можно выкинуть и забыть. Believe — это очень много всего. Во всех случаях, полагаете вы, или считаете — если вы believe, это значит, что у вас нет подтверждений или доказательств, но вы не знаете ни опровержений, ни доказательств обратного. Очень мощный юридическо-лингвистический казус. Когда вроде бы вы что-то обещаете, но не несете никакой ответственности, если ваши обещания не будут выполнены.
Igor_O, т.о. если это слово не подразумевает мыслительный процесс, то только «верить»? Ведь слово «доверять» в английском имеет свой собственный корень.
Попахивает верой?
Ну, это не самый плохой запах, потому что за верой лежит интуиция. Если вы не верите в свою интуицию — ну, беда…

Интуиция помогла найти ответ, а вера в свои силы помогла его искать.

Все еще плохо пахнет?

NB! Я написал вера, а не религия.
В статье ни слова о задаче, поэтому просто оставлю это здесь.
Постановка задачи
Идея состоит в том, чтобы (к примеру) описать понравившиеся фильмы некоей матрицей A[i,j], где i-фильмы, j-люди. (К примеру,) можно считать, что A — оценки, выставленные пользователем j фильму i. Всех значений матрицы мы не знаем, но хотели бы угадать.

Мы предполагаем, что матрица 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 возможно не меньше, чем за линейное время, но, похоже, это не требуется по условиям задачи. Чтобы рекомендовать конкретный фильм конкретному пользователю, будут использоваться какие-то другие приближения.

ИМХО многие специалисты из самых разных областей посмеются этой возне с линейной-логарифмической сложностью, поскольку большая часть задач, которые нам хочется решить, имеют экспоненциальную сложность.
Конечно можно посмеяться, только потом надо вспомнить, что количество фильмов порядка десятков тысяч, а количество активных пользователей того же нетфликса больше ста миллионов.
Сто миллионов это жалкие 1e8. Да и дело не в этом, просто при добавлении ещё ста миллионов пользователей в рамках этой задачи нужно, всего лишь, удвоить вычислительные мощности, что вполне реально. Если же вы удвоите показатель степени и получите 1e16, то ваши проблемы окажутся совсем другого характера.
Это какие же экспоненциальные задачи нам хочется решить :)? Просто в статье утверждается что задач имеющих практическое значение, для которых существуют квантовые алгоритмы быстрее чем классические, не так уж и много. Было бы интересно узнать, какие задачи имеют быстрое квантовое решение и нужны в жизни (не синтетические задачи).
Берёте комбинаторику и находите на свой вкус: задача коммивояжера, задача сравнения графов (хотя, вроде, появилось доказательство существования полиномиального алгоритма). В науке вся численная квантовая химия, численная квантовая физика, все эти сворачивания белков. Алгоритм Шора и все эти простые числа. Отсутствие квантового превосходства доказано в считанных случаях, все остальные ждут своего квантового симулятора.

А то, что пишется во введении — это личное мнение автора, так к этому и относитесь.
Мне вот интересно, а какие задачи ему еще предложили решить? Мне кажется что, этот паренёк просто благодаря своему таланту и гибкости ума, решил бы любую задачу, просто выразив сомнение в истинности постулатов.
Это не самая интересная проблема в программировании. ;-)
На мой взгляд предложенный алгоритм решает задачу так скажем не точно,
– и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.

а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных.

Видимо да. И да, из булки тоже можно сделать троллейбус :)

а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных

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

Процитированное вами упрощение алгоритма было сделано как раз в квантовой версии. Насколько я понял, версия Тана не уступает по качеству рекомендаций

Я по заголовку подумал, что этот подросток сломал квантовый компьютер или сорвал эксперимент, а оказалось, он научную работу написал. Молодец.
Пардон, конечно, но до какого возраста он будет подростком? Учитывая, что он к этому времени уже закончил университет…
teenager же. До 20 по определению. Только я бы тинейджера как подростка не перевел, для нашего понимания (12-16 лет) есть adolescent или juvenile
Извините за занудство, где такое определение? В 14 лет паспорт получить можно, уголовная ответственность уже светит, в 18 — совершеннолетие. Как можно быть одновременно и подростком, и совершеннолетним?
В большинстве штатов Cша совершеннолетие наступает в 18 лет, но в Алабаме, Вайоминге и Небраске – в 19, в Миссисипи и штате Нью-Йорк – в 21
Но многим совершеннолетним нельзя алкоголь (крепкий или некрепкий, не знаю, но крепкий точно нельзя до 21-го, как я понимаю)?
определение в Webster
Получить паспорт можно и в полтора года (загранпаспорт вроде с года дают), ни к подростковости, ни к тинейджерству, ни к совершеннолетию это отношения не имеет. Уголовная ответственность — тем более.
Подростком и совершеннолетним быть, наверное, нельзя (хотя подросток не имеет точного возрастного определения, это во многом культурально-обусловленное понятие). Тинейджером и совершеннолетним — почему нет?

JFI: Загранпаспорт сразу после свидетельства о рождении можно получить

Тинейджер — teenager. Человек, возраст которого заканчивается на '-teen'. Это прямо в этом слове вот прямо так и написано, даже определения дополнительного не нужно.
Ближе всего по сути юноша см. ru.m.wiktionary.org/wiki/юноша
Хотя так редко говорят разве что по приколу.
Юноша бледный со взором горящим
Ныне тебе я даю три совета…
Да, -teen в age есть только с 13 по 19, потому для неанглоязычных не всегда понятно. Но в US это важный рубеж, можно увидеть, например, в мультике Гравити Фолз.
> Извините за занудство, где такое определение?
teenager
13 — thirteen

19 — nineteen
20 — twelve

Все это очень сильно похоже на обычный метод ближайших соседей (nearest neighbors, https://en.m.wikipedia.org/wiki/Nearest_neighbor_search). Есть алгоритмы, которые обеспечивают точный поиск ближайших соседей, но это очень ресурсоемко. А есть алгоритмы приближенного поиска, время работы которых как раз логарифмически зависит от количества входных данных. Но и результат получается не точный, а приближенный. Есть куча фреймворков, которые давно уже умеют это делать.

Ясно, что перевод, но все же заголовок желтоват. Существование быстрого классического алгоритма не опровергает более раннюю работу Керенидиса и Пракаша, а скорее дополняет ее. Если бы «подросток» Тан нашел там ошибки или сорвал какой-нибудь эксперимент — другое дело.
А ссылка на статью, пример кода\псевдокода есть? Интересно посмотреть, что за алгоритм.
Как же надоели эти рекомендации. Стоит послушать несколько песен и поставить несколько оценок, как сервис начинает тебя одолевать своими «рекомендациями».
… и нафига ломать голову придумывая алгоритмы, занимаясь оптимизацией… А давайте будем строить квантовый процессор, а все имеющиеся не-квантовые процессоры просто объявим слишком маломощными для наших задач. И можно с умным видом надувать щеки, и вещать что мы супер умные и все пишем правильно, вот когда появится квантовый процессор, то это сразу станет понятно. А пока жрите что дают…
Дальше выпустят программы, которые даже 2+2 без квантового процессора складывать не умеют и обязательно будут требовать квантовый процессор именно последней, а не предпоследней модели. И помимо обновления ПО придется обновлять и железо.
Позже одни компании только на суде признаются, что они намеренно замедляли квантовые процессоры до уровня калькуляторов; другие компании будут запрещать публиковать результаты бенчмарков; третьи будут искать и таки находить критичные уязвимости, когда квантовые процессоры могут получить «случайное квантовое запутывание» во время производства или во время транспортировки, причем это будет работать как квантовая связь с третьими лицами без возможности засечь и все данные будут оказываться у АНБ злоумышленников практически мгновенно, а заплатки не смогут избавить от утечек, только замедлить квантовую связь на порядок и злоумышленник получит данные не через секунде, а через 10 секунд, но заплатки будут вызвать 90%-падение производительности.
Игроделы также не будут отставать — полностью забьют на оптимизацию и будут выпускать игры с 16М-текстурами даже иконок, которые еле заметны на самых лучших мониторах 32к! Если пользователей игра будет лагать и жутко тормозить — попросят приобрести более новое железо.
Короче, процветание индустрии. И где-то я это уже видел…
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.