Задать вопрос

SeptiM

Ответы

  • Почему сложность алгоритма (n+2n+3n+…+n⋅n) = O(n³)?

    @SeptiM
    На всякий случай, O -- это асимптотическая оценка сверху. Что-то типа '<='. Точная оценка определяется через \Theta, а нижня оценка `>=` через \Omega.

    В целом, можно посчитать точно через через прогрессию: 
    n + 2n + 3n + … + n ⋅ n = n ⋅ (1 + ... + n) = n * n * (n + 1) / 2 = O(n^3) (и \Theta(n^3)


    Можно лениво через верхнюю оценку:
    n + 2n + 3n + … + n ⋅ n <= n * n + ... n * n (n раз) = n^3 = O(n^3)

    Нижняя оценка оценивается по такому же принципу:
    n + 2n + 3n + … + n ⋅ n >= n/2 * n + ... n * n (n / 2 раз) >= n / 2 * n / 2 * n = \Omeg(n^3)
    Ответ написан
    Комментировать
    Комментировать

  • Есть ли готовая модель для распознавания объектов?

    @SeptiM
    BLIP: https://huggingface.co/Salesforce/blip-image-capti...
    Ответ написан
    Комментировать
    Комментировать

  • Почему не сходится градиентный спуск?

    @SeptiM
    Попробуй градиент нормализовать.
    Ответ написан
    Комментировать
    Комментировать

  • Как найти паттерны во времени посещения приложения?

    @SeptiM
    В целом звучит как задача кластеризации. Методы тут можно разные выбрать, главное -- как метрику задать.

    На вскидку, можно попробовать определить расстояние между пользователями Вася и Петя следующим образом. Для каждого захода Вася ищем ближайший заход Пети и смотрим как они различаются по времени. Получится набор времен t_1, t_2, ... t_В. Делаем тоже самое для Пети. Дальше считаем среднее значение как расстояние. Разницу можно считать на зацикленном периоде (на неделе между воскресеньем и понедельником расстояние -- 1 один день).

    Расстояние между Васей и Васей будет 0. Неравенство треугольника вроде выполняется. Если Вася и Петя заходили в одно и то же время, расстояние между ними будет маленькое.

    P.S. Расстояние можно посчитать за линию от числа заходов через линейный мердж сортированных массивов.
    Ответ написан
    2 комментария
    2 комментария

  • Как найти все палиндромы в терабайтном файле?

    @SeptiM
    https://arxiv.org/abs/1506.04862

    Там структура данных, линейная по памяти с суффиксным бором и деревом. Очень эффективная. Остается, правда, придумать, как ее на терабайт отмасштабировать.
    Ответ написан
    Комментировать
    Комментировать

  • Кто учился в магистратуре на машинное обучение (ИТМО)?

    @SeptiM
    В Питере CS Center есть. Я бы туда пошел. Яндекс преподает и денег драть не будут (им кадры нужны).
    Ответ написан
    Комментировать
    Комментировать

  • Есть ли платформы для машинного обучения без программирования?

    @SeptiM
    Может куда-нибудь сюда посмотреть: https://habrahabr.ru/post/244625/ ?
    Ответ написан
    Комментировать
    Комментировать

  • На чем и как лучше написать скрипт?

    @SeptiM
    Я бы это на bash-е написал. Что там, curl, sed, sort, unique, comm. Можно, наверное, в одну команду уложиться...
    Ответ написан
    7 комментариев
    7 комментариев

  • Подходит Java для ИИ и машинного обучения?

    @SeptiM
    Я бы больше думал про Python. Там экосистема под ML побогаче, чем в Java.
    Ответ написан
    Комментировать
    Комментировать

  • Как доказать отсутствие алгоритма для решения задачи?

    @SeptiM
    Вы возможно ищете проблему останова? Обычно ее сводят к нужной задаче, тем самым показывая алгоритмическую неразрешимость.
    Ответ написан
    Комментировать
    Комментировать

  • С чего начинать разработку нейронной сети?

    @SeptiM
    Не самый большой опыт, но если хотите именно понять, как использовать нейронные сети, то лучше воспользоваться питоном. Там неплохо развита экосистема, есть возможность использовать cuda. Посмотрите keras, и попробуйте решить что-нибудь на kaggle. На первое время должно хватить.

    В процессе, обычно хочется меньше тратить время на технические особенности языка. Каких-нибудь проблем с переобучением там хватит за глаза.
    Ответ написан
    Комментировать
    Комментировать

  • Суть машинного обучения сводится к классификации проанализированных данных?

    @SeptiM
    Мне кажется, на русской википедии есть базовый набор задач.

    Так, примеры не из классификации.
    1. Пишем поисковик. Нашли 100500 страниц, нужно выделить топ-10 самых релевантых. Проблема ранжирования.
    2. Пишем сервис для сравнения цен на квартиры. У нас есть база данных по рынку. Приходит очередная квартира со своими параметрами: дом, площадь, расстояние до метро, местная инфраструктура. Нужно восстановить цену. Регрессия.
    3. Мы ведем популярный аккаунт в инстаграме. У нас есть аудитория, мы хотим понять ее структуру, подумать, что там можно продавать. Требуется выделить сообщества, на которые разбиваются подписчики (обычно они подписаны друг на друга). Задача кластеризации.
    4. Мы -- кинопоиск. У нас есть огромная разреженная матрица (пользователи x фильмы). Кому что и насколько понравилось. Хотим научиться советовать, кому какой фильм порекомендовать. Рекомендательные системы.
    Ответ написан
    3 комментария
    3 комментария

  • Какой алгоритм использовать для нахождения повторяющихся слов в строке?

    @SeptiM
    А префиксное дерево не подойдет? Я бы сначала убрал бы все знаки препинания, понизил регистры, а потом его построил. Можно в каждой вершине хранить число листьей в поддереве и находить за O(1/phi) все слова, которые встречаются хотя бы phi * n раз, где n -- число всех слов.
    Ответ написан
    Комментировать
    Комментировать

  • В чём суть понятия cache conscious?

    @SeptiM
    Есть два вещи: cache conscious и cache oblivious. Обе относятся к уточненной модели памяти.

    В обычных алгоритмах у нас есть одна RAM память, к которой есть равноценный доступ. В уточненной -- между процессором и основной памятью есть кэш, доступ к которому существенно быстрее чем к основной памяти. Теоретическая модель кэша обычно выглядит так: это H строчек по W байт в каждой. Алгоритмы запрашивают чтение кусочка памяти в кэш, а потом оперируют с тем, что есть в кэше. Эффективность алгоритма определяется числом чтений основной памяти в кэш (+ стандартные характеристики)

    Собственно алгоритмы делятся на те, которым важны параметры кэша W и H -- cache concious, и те, которым они не важны -- cache oblivious.

    P.S. Вот на хабре подгоняют бинарный поиск с учетом кэша, а в update-е там же делают подсказку как сделать cache oblivious.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм приблизительного поиска выбрать?

    @SeptiM
    habrahabr.ru/post/114997
    Ответ написан
    Комментировать
    Комментировать

  • Как найти кратчайший путь в графе эвристическим алгоритмом?

    @SeptiM
    Начните с простого, с Дейкстры: e-maxx.ru/algo/dijkstra
    Ответ написан
    6 комментариев
    6 комментариев

  • Как решить задачу на статическую балансировку?

    @SeptiM
    На английском эта задача называется multiprocessor scheduling. Задача NP-трудная, так что точного алгоритма не ждите. В википедии предлагают 4/3 приближение: отсортировать все работы в порядке убывания длины, в полученном порядке назначать работу узлу, который освобождается раньше всех.
    Ответ написан
    Комментировать
    Комментировать

  • Как средствами программирования посчитать частоту сердцебиения?

    @SeptiM
    Можно сделать двухпороговую функцию. Пусть сигнал меняется от нуля до единицы. Возьмем два порога один на 0.1, другой на 0.9. Возьмем переменную x, которая принимает два состояния: высоко и низко. Если значение сигнала падает ниже 0.1 и x = "высоко", меняем на x на "низко". Поднимается с x = "низко" до 0.9, меняем на "высоко".

    Каждый раз, когда переменная меняет свое значение на высоко, считаем пульс. Единственное, надо понаблюдать, как амплитуда себя ведет. Может делить на максимум за последние секунд 10, ну и параметры понаблюдать. Лучше всего, если есть приличная размеченная история с пульсом и можно сразу запустить тестирование на обучающей, кросс и контрольной выборках.
    Ответ написан
    2 комментария
    2 комментария

  • Как получить фотографию грабителя из записи видеонаблюдения?

    @SeptiM
    В жизни патроны кончаются быстрее. Есть техника superresolution, но она работает только если сделали сотню фоток с одной позиции слабенькой камерой. Есть проблема, что лица двигаются и видео их размазывает. Второй товарищ в этом смысле засветился гораздо качественней. Так можете с лупой в VLC прогнать на замедленной съемке, может что лучше поймаете.

    0f243cdf52444fb78ff0bdb2ef58b56f.png
    UPD: Немного гистограмму подкорректировал.
    Ответ написан
    4 комментария
    4 комментария

  • Представление категорических и порядковых данных линейной регрессии (машинное обучение)?

    @SeptiM
    1. По сути вся машинка сводится к решению оптимизационных задач. Есть набор ограничений и есть функция, которую надо оптимизировать (min, max). В вашем случае вы, скорее всего, минимизируете среднеквадратическое отклонение. Делите выборку на две части, обучаетесь на тренировочной, считаете значение на контрольной. Вот это значение и есть критерий качества вашей модели.

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

    3. Вывод: теория -- это хорошо, но лучше честно сравнить модели по данным.

    4. Теория. Если вы представляете одну категорию несколькими переменными, то у вас получается большая размерность. На примере, если цвет вносит вклад по принципу белый -- 0, красный -- 10, черный -- 20, то в одной модели это будет 10 * x_цвет, а в другой 0 * x_белый + 10 * x_красный + 20 * x_черный. В то же время ситуация выглядит как белый -- 0, красный -- 10, черный -- 100, то в первой модели точного представления уже не получится, а во второй можно по прежнему расставить соответствующие веса.

    По сути модель с множеством переменных является обобщением модели с одной. Проблема только, что число переменных растет...
    Ответ написан
    Комментировать
    Комментировать