Обсуждение:Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Группа 274, весна 2015

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Разработка алгоритма поиска параметров фибринолиза

  • Название: Разработка алгоритма поиска параметров фибринолиза.
  • Задача: Задан набор снимков роста фибринового сгустка, полученных в процессе исследования тромбодинамики и фибринолиза. Требуется разработать алгоритм поиска координат отрезка и угла наклона линии активатора по серии снимков. Протестировать разработанный алгоритм на разных видах фибринолиза и примерах, где данный процесс отсутствует.
  • Данные: Массив снимков для каждого исследования формата tiff 16 бит c моментами времени от начала [сек] (Image_0 соответствует первому кадру, Image_181 - 45 минуте при интервале съемки 15 секунд).
  • Литература
    • Описание прикладной задачи и техническое задание: по запросу?
  • Базовой алгоритм: Преобразование Хафа pdf, к примеру.
  • Решение:
  • Новизна: ??

Supervised rank aggregation with monotone feature transformation

  • Название: Supervised rank aggregation with monotone feature transformation.
  • Задача: We address the problem of supervised rank aggregation, the task of combining the ranking results of individual rankers at meta-search [Yu-Ting Liu et al]. In supervised learning rank aggregation is formalized as optimization which minimizes disagreements between ranking results and the labeled data. In current research we propose to expand the Borda Fuse rule (linear combination of ranking vectors) by considering monotone transformations of the rankings.
  • Данные:
  • Литература
    • Problem statement
    • Yu-Ting Liu, Tie-Yan Liu, Tao Qin, Zhi-Ming Ma, and Hang Li. Supervised rank aggregation. In Proceedings of the 16th international conference on World Wide Web, pages 481–490. ACM, 2007.
  • Базовой алгоритм: Borda Fuse rule: linear combination of ranking vectors without monotone transformation.
  • Решение:
  • Новизна: The proposed class of monotone transformations allows to get any possible transformation of orders in Euclidean space. In the special case of the unit weight vector we get the vector of the Borda Count scores.

Задачи от Каневского

Взаимозаменямость товаров

  • Задача: аналогично задаче о новых товарах. Гипотеза: в продажах наблюдается взаимозаменямость товаров, проявляющаяся в виде:
    1. . Эффекта «каннибализации» - при появлении на рынке нового товара продажи аналогичных товаров (по группе, по цене) начинают падать.
    2. Снижения продаж аналогичных товаров при проведении промо-акции по данному товару;
    3. Повышения продаж аналогичных товаров при проведении-промо-акции по данному товару;

Необходимо проверить гипотезу и повысить качество прогнозов путем учета эффектов взаимозаменяемости.

  • Решение: Для решения задачи предлагается:
    1. Формализовать понятие «аналог» для новых товаров;
    2. Повысить качество прогнозирования товара в начале его продаж с помощью привлечения аналогов;
    3. Указать период, в течение которого товар следует считать новым и, соответственно, привлекать аналоги для его прогнозирования.


Прогнозирование по группам

  • Дано: аналогично задаче о жизненном цикле.
  • Гипотеза: спрос на отдельные товары слишком неустойчив, поэтому прогнозировать непосредственно

временной ряд продаж товара не имеет смысла. Более качественные прогнозы можно получить, предварительно агрегируя продажи по группам товаров и/или по магазинам, прогнозируя ряд группы, после чего распределяя прогнозы обратно по товарам.

  • Задача: повысить качество прогнозов, подобрав подходящую группировку данных.
  • Внимание! Для прогнозирования группы может понадобиться другой алгоритм, чем для отдельных товаров.

Задачи вокруг информационного поиска

Simplification of the IR models structure

  • Название: Simplification of the IR models structure
  • Задача: To achieve the acceptable quality of the information retrieval models, modern search engines use models of very complex structure. In current research we propose to simplify the model structure and make it interpretable without decreasing the model accuracy. To do this, we follow the idea from (Goswami et al., 2014) of constructing the set of nonlinear IR functions of simple structure and admissible accuracy. However, each of this

functions is expected to have lower accuracy while comparing with the best IR model of complex structure. Thus, we propose to approximate this complex model with the linear combination of the simple nonlinear functions and expect to obtain the comparable quality of solution.

  • Данные:
  • Литература
    • P. Goswami et Al. Exploring the Space of IR Functions // Advances in Information Retrieval. Lecture Notes in Computer Science. 8416:372-384, 2014.
    • Problem statement
  • Базовой алгоритм: Exaustive search of superpositions from a set of elementary functions.
  • Решение: The optimal functions for the linear combination can be found by the greedy algorithm.
  • Новизна:

Порождение ранжирующих моделей методом Насти (ветвей и границ)

  • Название: Направленный поиск структуры ранжирующей модели.
  • Задача: Порождение ранжирующих моделей методом Насти (ветвей и границ). Решается задача поиска ранжирующей функции в задачах информационного поиска. В работе [1] поиск осуществляется полным перебором, обеспечивающим оптимальность найденного решения решения. Поиск проводится среди непараметрических функций (структур), сгенерированныx грамматикой G вида: g---> B(g, g) | U(g) | S, где B - набор бинарных операций {+, -, *, /}, U - унарных {-(), sqrt, log, exp}, S - переменных и параметров {x, y, k}.Каждой порождаемой функции выставляется оценка качества, вычисляемая как MAP (mean average precision) на некоторой коллекции документов. На основе этих оценок качества выделяются множества оптимальных ранжирующих структур. Требуется проверить гипотезу о наличии структурных закономерностей среди оптимальных/неоптимальных структур для сокращения полного перебора.
  • Данные: Списки допустимых сгенерированных функций длины 4-8, список из 100 лучших функций длины 8, список из 500 лучших функций с оценками качества.
  • Литература
    • задачи
    • Описание коллекции данных, используемых для оценки функций, и процедуры оценки. [1]
  • Базовой алгоритм: Алгоритм полного перебора допустимых суперпозиций порождающих функций.
    • P. Goswami et Al. Exploring the Space of IR Functions // Advances in Information Retrieval. Lecture Notes in Computer Science. 8416:372-384, 2014.
  • Решение: (В рамках гипотезы о наличии набора/наборов структурно-близких оптимальных функций) В исходном методе порождаются все структуры заданной длины k с последовательным увеличением длины. Для сокращения полного перебора и упрощения процедуры их оценки предлагается выделить набор структур некоторой длины k, такой что все оптимальные структуры длины k+1 могут быть получены применением правил грамматики G к некоторой структуре из данного набора.
  • Новизна:
    • На данный момент в [1] был проведен поиск структур длины k до 10. Был обнаружен ряд функций, по качеству соперничающих с применяемыми на практике (например - BM25, ранжирующей функцией длины 25). Проведенные в [1] исследования позволяют предположить, что перебор структур с дальнейшим увеличением их длины выявит функции, существенно превосходящие по качеству обнаруженные ранее. Ограничением становится вычислительная сложность полного перебора при увеличении k. Сокращение процедуры перебора структур позволит увеличить сложность рассматриваемых структур.
    • Предложен алгоритм последовательного добавления элементы суперпозиций. Предложена функция расстояния между суперпозициями, исследованы ее свойства. Введено понятие сложности суперпозиции и понятие смежных суперпозиций, отличающихся по сложности на единицу. Предложен алгоритм порождения смежных суперпозиций.

Структурное обучение при порождении моделей

  • Название: Структурное обучение при порождении моделей
  • Задача: Решается задача поиска ранжирующей функции в задачах информационного поиска. Поиск проводится среди непараметрических функций (структур), сгенерированныx грамматикой вида G: g---> B(g, g) | U(g) | S, где B - набор бинарных операций {+, -, *, /}, U - унарных {-(), sqrt, log, exp}, S - переменных и параметров {x, y, k}. Предлагается решать задачу порождения ранжирующей модели в два этапа, используя в качестве обучающей выборки историю восстановления структуры модели.
  • Данные: Подколлекции TREC.
  • Описание коллекции данных, используемых для оценки функций, и процедуры оценки. [2]
  • Литература
    • Jaakkola T. Scaled structured prediction.
    • Tommi Jaakkola “Scaling structured prediction”
    • Найти все работы учеников TJ по данной тематике.
    • Варфоломеева А.А. Дипломная работа бакалавра в MLAlgorithms/BSThesis/Varfolomeeva
  • Базовой алгоритм: Парантапа, BM25 - модели для сравнения.
  • Решение:
  • Новизна: Обнаружены ранжирующие функции, не уступающие по качеству используемым на практике.


 ?? Про разбиение большой коллекции на маленькие подколлекции для задачи стр. обучения

  • Название: Создание выборки для задачи структурного обучения
  • Задача: Про разбиение большой коллекции на маленькие подколлекции для задачи стр. обучения/ расстояние между моделями и коллекциями

Для построения ранжирующей модели методами структурного обучения необходимо собрать выборку: набор коллекций документов и полученных на этих коллекциях ранжирующих функций. Коллекции, на которых происходит обучение ранжирующей структуры, традиционно размечаются вручную, что затрудняет процесс сбора выборки для задачи структурного обучения. Варианты: предложить способ разбиения существующих коллекций на подколлекции. Здесь же можно рассмотреть зависимость построенного набора оптимальных функций от коллекции. воспользоваться методом построения псевдо-коллекций (новизны нет)

  • Данные:
  • Литература
    • Варфоломеева А.А. Дипломная работа бакалавра в MLAlgorithms/BSThesis/Varfolomeeva
    • Nima Asadi, Donald Metzler, Tamer Elsayed, Jimmy Lin, “Pseudo Test Collections for Learning Web Search Ranking Functions”, 2011. pdf
  • Базовой алгоритм: ??.
  • Решение:
  • Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).

Упрощение суперпозиций, доработка статьи Кулунчакова и Сологуба

  • Название: Упрощение суперпозиций, доработка статьи Кулунчакова и Сологуба
  • Задача: Написать обзор по методам упрощения суперпозиции, провести их сравнение (желательно на данных TREC?)
  • Данные:
  • Литература
    • Ehrig H., Ehrig G., Prange U.,Taentzer. G. Fundamentals of Algebraic Graph Transformation. Springer, 2006.
    • Ehrig H., Engels G. Handbook of Graph Grammars and Computing by Graph Transformation. World Scientific Publishing, 1997.
    • Роман Сологуб. Алгоритмы индуктивного порождения и трансформации моделей. [3]
    • Kulunchakov2014IsomorphicStructures.pdf
  • Базовой алгоритм: .
  • Решение:
  • Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).

Непараметрическое прогнозирование временных рядов

Синхронизация рядов

  • Название: Обнаружение закономерностей в наборах временных рядов
  • Задача: Разработать метод выявления связей между временными рядами, определяемых структурой фазового пространства. Требуется изучить набор подходов к выявлению связей между ними; описать границы применимости базового алгоритма и предложить новые варианты выявляемых структурных связей.
  • Данные: Синтетические данные, исторические биржевые цены на основные инструменты и данные по железнодорожным грузоперевозкам.
  • Литература
    • Tools for the Analysis of Chaotic Data. HENRY D. I. ABARBANEL
    • Nonlinear forecasting as a way of distinguishing chaos from measurement error in time series, G. Sugihara, R.M. May.
    • George Sugihara et al. Detecting Causality in Complex Ecosystems. Science 338, 496 (2012);
    • Вальков А.С., Кожанов Е.М., Мотренко А.П., Хусаинов Ф.И. Построение кросс-корреляционных зависимостей при прогнозе загруженности железнодорожного узла // Машинное обучение и анализ данных. 2013. T. 1, № 5. C. 505-518.
  • Базовой алгоритм: Алгоритм сходящегося перекрестного отображения (Convergent Cross Mapping, CCM)
  • Решение:
  • Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).


Условный прогноз

  • Название: Про учет экзогенных факторов
  • Задача: При прогнозировании железнодорожных грузоперевозок предлагается учесть как предысторию самих перевозок, так и экзогенные (внешние) факторы. Для учета экзогенных факторов при прогнозировании железнодорожных грузоперевозок необходимо развить ранее предложенный метод гистограммного прогнозирования Hist, основанный на свертке гистограммы временного ряда с функцией потерь.
  • Данные: Синтетические данные, исторические биржевые цены на основные инструменты и данные по железнодорожным грузоперевозкам.
  • Литература
    • Вальков А.С., Кожанов Е.М., Медведникова М.М., Хусаинов Ф.И. Непараметрическое прогнозирование загруженности системы железнодорожных узлов по историческим данным // Машинное обучение и анализ данных. — 2012. — № 4.
    • Model Estimation and Validation by Daniel McFadden, Antti Talvitie, and Associates, 1977
    • Density forecasting: обзор гистограммных подходов к прогнозированию временных рядов.
    • Экспериментальные исследования свойств алгоритма Hist [4], [5]
  • Базовой алгоритм: Алгоритм Hist.
  • Решение: Чтобы включить в модель гистограммного прогнозирования экзогенные переменные, необходимо разработать методы оценки многомерных гистограмм/ условных гистограмм временных рядов при небольшой длине истории. (Длина исследуемого временного не очень велика, что при увеличении размерности гистограммы приводит к ее разреженности).
  • Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).


Выделение тренда и сезонности

  • Название: Повышение качества непараметрического пронгозирования путем выявления и учета экзогенных факторов (тренд и сезонность при этом выделяются из временного ряда и учитываются как экзогенные факторы)
  • Задача: Предлагается рассматривать тренд и сезонность как экзогенные факторы при прогнозировании железнодорожных перевозок.
  • Данные: Синтетические данные, исторические биржевые цены на основные инструменты и данные по железнодорожным грузоперевозкам.
  • Литература
    • Вальков А.С., Кожанов Е.М., Мотренко А.П., Хусаинов Ф.И. Построение кросс-корреляционных зависимостей при прогнозе загруженности железнодорожного узла // Машинное обучение и анализ данных. 2013. T. 1, № 5. C. 505-518.
    • Вальков А.С., Кожанов Е.М., Медведникова М.М., Хусаинов Ф.И. Непараметрическое прогнозирование загруженности системы железнодорожных узлов по историческим данным // Машинное обучение и анализ данных. — 2012. — № 4.

временных рядов.

  • Базовой алгоритм: Метод Грейнджера?
  • Решение: Для проверки наличия тренда и сезонности используются существующие методы выявления экзогенных факторов. При этом сезонность моделируется тригонометрическими рядами, тренд - экзогенными временными рядами из заданного списка.
  • Новизна: Новый подход к выделению тренда и сезонности?
Личные инструменты