Comments 33
Надежный алгоритм классификации "свой-чужой", да еще без ангажированного обучения, - это большое открытие, которое может изменить мир во многих сферах за пределами МП.
Дейтинг уже упомянули, и его можно обобщить до всех видов межличностного взаимодействия. Например, по совокупному профилю соцсетей определять политические предпочтения людей (населяемых ими регионов).
В плане товарки можно сравнивать не (с)только описательные характеристики товаров, но и отзывы/вопросы, взаимодействия (просмотры, клики, шеры и т.д.). Это поможет продавцам улучшить предложение и тем самым усилить позиции МП в сравнении с другими МП и с офлайном.
В медицине можно ожидать более уверенную, например, диагностику по набору имеющихся данных. При тотальном дефиците врачей (настоящих, а не занимающих место), такой инструмент позволил бы поднять качество медицинских услуг на совершенно новый уровень.
И вообще диагностика, не только в медицине. Например, на таком массовом рынке, как авторемонт.
В рекрутинге можно отделять реально полезных людей от талантливых очковтирателей)
Вот в науке пишут, что ее огромная часть - фейк для удовлетворения кпи. Можно находить статьи, имеющие и не имеющие научной ценности или в отношении научных работников - настоящий ученый (врач, педагог, президент) или случайный человек)
В общем - бомба)
Было бы здорово, если бы из этого сделали публичный сервис. Или опенсорс)
У продавцов есть задача определения объема рынка разных модификаций товара.
А теперь тоже самое к дейтинг сервисам примените))) и вы получите Тиндер. жалко что стартапы в этом направлении с матчастью не знакомы.
Характеристики товаров довольно объективны: функции, форма, размер, цвет, комплектация, материал и т.д.
А как определять тождественность людей?
А точно ли успех отношений зависит от степени тождественности людей?
В патенти Тиндера описано довольно много параметров завязанных на поведении: соотношение лайков и дизлайков профиля, соотношение лайк-лайк / лайк-дизлайк, глубина просмотра анкеты, время просмотра анкеты, факт переписки о ключевых темах: политика, животные, спорт, путешествия, факт обмена контактной информаией, длительность просмотра сообщений от их длинны, факт перефитывания сообщений, факт инициации переписок, факт мертных метчей и их количество, факт физической близости устройств, время и место контактов, вероятность секса (так называемая верифицированная выборка) и т.д.
Думаю, что в основе дейтинг-сервисов скорее лежат немного другие алгоритмы, как написали выше. Поиск "идентичных" профилей может помочь с выявлением фрода, в частности, находить фейковые аккаунты.
Сам же дейтинг скорее базируется на алгоритмах ранжирования, рекомендаций и т. д. Например, можно показывать пользователю анкеты, анализируя фотографии и описание профилей понравившихся ему людей
Позвольте полюбопытствовать, в своей практике, вы часто полсматриваете патенты амазона? Может вдохновляетесь? Там довольно таки много интересных решений. Без осуждения, я только за такую практику.
Я человек простой. Вижу графы, алгоритмы - ставлю лайк. Недавно приходилось решать задачу мерчендайзинга - автоматизация планограммирования. Это про рассчитать товары на стеллажах оптимальным образом. Задача сводилась к NP полной - одномерной упаковке. Генетические алгоритмы и все такое. Вы не рассматривали метаэвристические стратегии? Эволюционные или роевые алгоритмы, может.
Алгоритмы распространения меток, в некотором смысле, схожи с генетическими. Думаю, что вопрос в интерпретации их шагов и в различных модификациях алгоритма
Есть публикация, в которой предлагается еще одна вариация алгоритма распространения меток и как раз приводится ее интерпретация с точки зрения генетического алгоритма:
https://doi.org/10.1016/j.eswa.2016.12.039
Боюсь, что ничего общего между ними нет кроме использования множества решения. Это совершенно разного класса алгоритмы. Статья по ссылке также не про это. Это гибридный алгоритм. LP как простая стратегия хороша из-за низкой временной сложности и встроить как вспомогательный инструмент в другие алгоритмы удобно.
Здравствуйте. Не могли бы вы сформулировать постановку одномерной упаковки?
P.S. Если под одномерной упаковкой подразумевать т.н. задачу упаковки одномерных предметов в минимальное число одинаковых контейнеров (раскрой при изготовлении пластиковых окон, упаковка в вагоны металлопроката), то она прекрасно решается FFD-алгоритмом, см. Гэри, Джонсон Вычисл. техника и трудно решаемые задачи.
Светлана, напишите, пожалуйста, критерий оценки алгоритма. Как вы пришли к оценке "прекрасно"? Не в обиду Гэри Джонсону, но это примитивный жадный алгоритм, даётся студентам на лабораторной. Я его лично не знаю, но скорее всего, он просто, как и прочие авторы, приводил все алгоритмы подряд, как пример очередной простой стратегии. У любых NP-задач есть полно различных алгоритмов для решения, и все они как правило, основаны на одной простой эвристике и относятся к классу жадных стратегий.
Для FFD-алгоритма доказана верхняя оценка погрешности. Решение, полученное FFD-алгоритмом (для задачи одномерной упаковки), отличается от оптимального не более, чем на 22%. Нужно понимать, что эти 22% достигаются на специально сконструированных "плохих" примерах (откройте Гэри, Джонсона и посмотрите, какой они сконструировали плохой пример). А на наборах реальных данных FFD часто даёт оптимальное решение. Вот такой редкий уникальный случай: задача NP-hard в сильном смысле, и решается простым FFD-алгоритмом. Что же касается, например, генетических алгоритмов, то для них нет оценки погрешности, вы не знаете, насколько ваше решение может отклониться от оптимального.
Светлана, я прекрасно знаком с жадными стратегиями для различных NP задач, это моя специализация. 22% - это фейл в мире оптимизации. Из Ваших же утверждений логично следует (но это и без них понятно), что неизвестно как сильно отклониться от оптимимума примитивный жадный алгоритм. То ли 22%, то ли меньше. Борьба, как правило, идет за 0-1%, а FFD в научных статьях могут упоминать только в качестве сравнения и в учебной литературе.
Попробуйте ознакомиться с другой литературой, в частности по оптимизации. Изучите методы ИИ, эволюционные подходы. Почитайте Курейчика В.М., Лебедева Б.К., Гладкова Л.А. и т.д. Да хоть любую зарубежную статью с бенчмарками - FFD у всех показывает худший результат. Есть мастодонты и в России, не только за бугром все хорошо. Попробуйте реализовать в конце концов генетический алгоритм. Единственный плюс простых алгоритмов, которые приводят ТОЛЬКО для примера - это скорость.
Я уже молчу о том, что одномерная упаковка - это упрощенная модель реальной задачи, а в реальности критериев гораздо больше, что делает пространство поиска гораздо сложнее и не гладкой, а у жадных стратегий строго одна эвристика по одному критерию.
В контексте бизнес-задачи важно было показать, что упрощение и сведение к одномерной упаковке имеет место быть и это доказывает NP-полноту задачи, отсюда можно смело переходить к методам ИИ.
Давайте по пунктам. 1. Вы сказали, что ваша задача сводится к одномерной упаковке. По факту одномерная упаковка к ней сводится как подзадача. Эта разные вещи. 2. Разумеется, бизнес-задачи обычно содержат комплекс NP- трудных задач. Я про это уже знаю, т.к. делала (в качестве математика-постановщика), например, задачу по размещению и отгрузке готовой листопрокатной продукции. Все опубликовано, могу в личку дать соответствующие ссылки, если интересно. 3.NP -hard в производственной размерности не решаются точными алгоритмами, только приближенными и эвристическими (нет верхней оценки погрешности), о каких сотых долях процентах вы пишете? 4. Про генетические алгоритмы я уже читала. Где-то они, видимо, хорошо работают, но для оперативного планирования производства (а размещение на складе относится к оперативному планированию) они не подходят, по моему опыту.
1-2. Нет, речь не шла о подзадаче, это многокритериальная задача, эту задачу нельзя разбить на подзадачи (если речь не о пространстве поиска), можно только выделять дополнительные критерии.
3.
NP -hard в производственной размерности не решаются точными алгоритмами
Зачем писать, что белое - это белое? Возможно, для какой-то аудитории это новость. Это курс дискретной математики 2 курса технического ВУЗа.
о каких сотых долях процентах вы пишете?
Если не риторический вопрос, почитайте статьи с экспериментальными сравнениями, бенчмаркинг, все в цифрах дают. Особенно в зарубежных любят цифры.
4.
Про генетические алгоритмы я уже читала
...
они не подходят, по моему опыту
Извините, "читала" - это не опыт. Это отсутствие опыта. Погуглите "решение задачи одномерной упаковки", у Вас на первой же странице вывалятся статьи с именами авторов, в том числе вышеуказанных (не Гэри) и почти все про ГА или рой. На своем веку написал не менее 300 ГА, хотя мой основной профиль - роевые методы. Редко подводят, лучше иногда роевые бывают (муравьиные, пчелиные и т.д.).
На счет оперативности, вернусь к кейсу с управлением роботов. Весьма сложная задача, к тому же с динамически меняющиейся средой. Лучший алгоритм в мире, среди тысяч талантливых программистов. Знаете сколько время отклика алгоритма для принятия решения? 50мс. 50 миллисекунд. Это было жесткое ограничение соревнования, так что 50 мс это достоверно известное время отклика, и никакая быстрая эвристика не могла противостоять. Проблема ГА - высокий порог входа. Не написав пару сотен ГА, не появится навык проектирования эффективных ГА. Так что не спешите аппелировать к опыту, ограниченному лишь чтением. По моему опыту, даже матерые грантоежки со степенями не способны писать эффективный ГА.
Если правильно понял, то для решения задачи об одномерной упаковки использовали генетические алгоритмы. Именно их из-за того, что они чаще находят оптимальное решение? Есть ли ещё какие-то преимущества?
И если не секрет, среди генетических алгоритмов какие у вас показали лучший результат?
Выбор обоснован проекцией моего опыта работы с бионспирированными алгоритмами (эволюционные, роевые). Роевые я отсек интутивно, так как они красиво кладутся на другие задачи, у них механика поиска слишком узкая в отличие от ГА, но дают более эффективные решения там, где их можно приложить. ГА же можно применять в любой непонятной ситуации. К примеру в международном чемпионате по программировани ИИ для роботов с 4-5 тысячами участников 1 место занял кодер, написавший ГА для робота.
В NP-задачах в контексте ГА речь всегда заходит об их модификации. ГА сам по себе - подход эволюционного моделирования, именно подход, а не пошаговый алгоритм. Операторы кроссинговера, мутации и отбора сильно зависят от выбранного способа кодировки хромосомы (решения) и контекста задачи (двигателя эволюции). Поэтому нет точного пошагового определения ГА, это про подход, можно максимум уточнить, какую модель использует ГА - Де Фриза, Ламарка, Дарвина и т.д. Но этого недостаточно для реализации, способ кодировки хромосомы каждый сам для себя определяет, а оттуда все операторы зависят.
Хорошо, спасибо!
А в какого типа задачах чаще роевые алгоритмы лучше себя показывают?
Задач огромное множество. Для пространственных хороши.
Муравьиные алгоритмы: больше для транспортных задач (TSP, VRP и их модификации) подходят. Но это медленный алгоритм, нужно аккуратно применять настройки.
Пчелиные: разбиение графа, размещение и т.д. В целом быстрый алгоритм. Алгоритм интересен разноролевыми агентами. В некоторых задачах эта технология проецируется очень классно. Об этом ниже.
Не все роевые алгоритмы применял, каждый год парочка новых, и на практике не впечатлили большинство.
Основной инструмент роевых алгоритмов - технология взаимодействия многоагентной системы и часто разноролевые агенты, поэтому очень любят применять в групповом управлении автономными системами. Например, дроны. Там им равных нет. Разве что ГА, но это если один дрон, а не группа.
Надежный алгоритм классификации "свой-чужой", да еще без ангажированного обучения, - это большое открытие, которое может изменить мир во многих сферах за пределами МП.
Дейтинг уже упомянули, и его можно обобщить до всех видов межличностного взаимодействия. Например, по совокупному профилю соцсетей определять политические предпочтения людей (населяемых ими регионов).
В плане товарки можно сравнивать не (с)только описательные характеристики товаров, но и отзывы/вопросы, взаимодействия (просмотры, клики, шеры и т.д.). Это поможет продавцам улучшить предложение и тем самым усилить позиции МП в сравнении с другими МП и с офлайном.
В медицине можно ожидать более уверенную, например, диагностику по набору имеющихся данных. При тотальном дефиците врачей (настоящих, а не занимающих место), такой инструмент позволил бы поднять качество медицинских услуг на совершенно новый уровень.
И вообще диагностика, не только в медицине. Например, на таком массовом рынке, как авторемонт.
В рекрутинге можно отделять реально полезных людей от талантливых очковтирателей)
Вот в науке пишут, что ее огромная часть - фейк для удовлетворения кпи. Можно находить статьи, имеющие и не имеющие научной ценности или в отношении научных работников - настоящий ученый (врач, педагог, президент) или случайный человек)
В общем - бомба)
Круто, недавно погрузился в изучение алгоритмов, пробовал несколько сам реализовать (Apriori и Eclat на R), и очень нравится читать подобные, хорошо написанные статьи с примерами на коде/псевдокоде -- помогает в понимании, спасибо!
"Наша команда разрабатывает алгоритмы поиска одинаковых товаров на сайте. Это позволяет покупателям находить более выгодные предложения, экономя время и деньги. "
Исходя из моего опыта, для решения этой задачи надо выбрать другую площадку.
Много раз натыкался на варианты, когда одни и тот же продавец на один товар, на разных площадках ставит разную цену. И самая высокая на ОЗОН.
Получается что ваша работа бесполезна на фоне политики руководства озона.
Привет!
Вы правильно процитировали «поиск одинаковых товаров на сайте».
В статье речь про поиск одинаковых товаров от разных продавцов на Ozon.
Как вы логически перешли к «один и тот же продавец на один товар, на разных площадках ставит разную цену» не уловил
Для меня тут, ключевое слово покупатель. Которые в моём лице желают "находить более выгодные предложения, экономя время и деньги."
Про поиск, как оценить работу алгоритма?
Правильно.
Сравнив его результаты, с другими алгоритмами на других площадках.
По результатам задачи "находить более выгодные предложения, экономя время и деньги." для меня, как конечного пользователя, алгоритмы на других площадках дают лучшие решение.
Так понятнее?
Вы сами себе противоречите
Говорите, что «один и тот же продавец на один товар, на разных площадках ставит разную цену»
При том предлагаете оценить качество алгоритма: «Про поиск, как оценить работу алгоритма? Правильно. Сравнив его результаты, с другими площадками.»
(вообще говоря, поиск и матчинг это разные задачи)
Как матчинг влияет на ценовую политику продавца?
Экономия времени и денег покупателя происходит за счет того, что предложения от разных продавцов на сайте находятся в общей карточке товара, и покупатель может быстрее выбрать более подходящее предложение. Надеюсь, что статью вы прочитаете, а не будете просто «накидывать», потому что в статье это подробно описано, с картинками. Вероятно, после прочтения и комментарии будут по сути статьи
Спасибо за статью, интересная идея! Используете ли ещё в компании где-то алгоритмы на графах? Звучит как достаточно перспективный подход.
Спасибо за статью, очень полезно и, что нельзя не отметить, красиво (особенно графы)!
Подскажите, в вашей статье речь идёт про неориентированные графы. Работают ли эти алгоритмы в случае ориентированных? Применяете ли вы их на практике?
Спасибо за отзыв и полезный вопрос! :)
Да, рассмотренные алгоритмы работают в том числе и с ориентированными графами.
В случае первых двух алгоритмов изменения коснутся матрицы смежности графа, она станет несимметричной. Матричный элемент A_{ij} будет = 1, если есть ребро из вершины i в вершину j, иначе 0. При том для ребер с заданным направлением A_{ij} != A_{ji}
Для последнего алгоритма при выборе самой часто встречаемой метки среди соседей нужно будет учитывать только тех соседей, из которых есть ребра в рассматриваемую вершину.
Где это можно применить на практике?
Представим, что у нас есть вершины, метки которых мы хотим заморозить (не обновлять), но на их основе обновлять метки других вершин. Тогда, как один из вариантов, для "замороженных" вершин можно удалить ребра, которые ведут к ним, оставив ребра, выходящие из них
Два сапога — пара, а три — уже community: как алгоритмы на графах помогают собирать группы товаров