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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Разработка алгоритма поиска параметров фибринолиза)
м (От Матвеева)
Строка 9: Строка 9:
* '''Новизна''': ??
* '''Новизна''': ??
-
=== От Матвеева ===
+
 
-
* '''Название''': Определение области затенения радужки классификатором локальных текстурных признаков
+
-
* '''Задача''': Дано изображение радужки глаза человека и окружности, аппроксимирующие границы зрачок-радужка и радужка-склера. Кольцо, заключённое между этими окружностями, - радужка. Область радужки часто перекрыта (затенена) различными объектами: блики, веки, ресницы, тени от век и ресниц. Известен некоторый сегмент S кольца, не содержащий затенений. Требуется выделить точки затенения в области радужки. Качество решения определяется как минимум суммы относительных ошибок первого и второго рода по тестовому набору изображений, для которых известны области затенения.
+
-
* '''Данные''':
+
-
*# База изображений радужки CASIA-Iris-Thousand http://biometrics.idealtest.org/dbDetailForUser.do?id=4
+
-
*# База изображений радужки MMU
+
-
*# База изображений радужки IIT Delhi http://www4.comp.polyu.edu.hk/~csajaykr/IITD/Database_Iris.htm
+
-
*# NIST ICE DB и др.
+
-
* '''Литература''':
+
-
**[1] Y. H. Li, M. Savvides. A pixel-wise, learning-based approach for occlusion estimation of iris images in polar domain. In ICASSP, pages 1357–1360. IEEE, 2009.
+
-
**[2] Guangzhu Xu, Zaifeng Zhang, and Yide Ma. Improving the performance of iris recogniton system using eyelids and eyelashes detection and iris image enhancement. In Cognitive Informatics, 2006. ICCI 2006. 5th IEEE International Conference on, volume 2, pages 871–876, July 2006.
+
-
**[3] Zhaofeng He, Tieniu Tan, Zhenan Sun, and Xianchao Qiu. Robust eyelid, eyelash and shadow localization for iris recognition. In ICIP, pages 265–268. IEEE, 2008.
+
-
**[4] Zhaofeng He, Tieniu Tan, Zhenan Sun, and Xianchao Qiu. Toward accurate and fast iris segmentation for iris biometrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(9):1670–1684, 2009.
+
-
* '''Базовой алгоритм''': См. [1]. Каждая точка области радужки относится к одному из двух классов: радужка/затенение, с использованием классификатора, основанного на смесях гауссианов. Вектор признаков точки пятимерный, состоит из её координат, яркости, средней яркости окрестности и дисперсии яркости в окрестности. Для обучения классификатора используются изображения, размеченные вручную.
+
-
* '''Решение''': В [1] используется ручная разметка некоторых изображений для тренировки классификатора. Это является недостатком. С использованием сегмента S, не содержащего затенений, можно построить полностью автоматический метод. Таким образом содержание работы — реализация метода [1], но с использованием сегмента S (содержащего лишь часть истинной радужки) вместо разметки, где выделена вся незатенённая радужка. Также рекомендуется рассмотреть различные характеристики окрестности точки в дополнение к пяти признакам, используемым в [1].
+
-
* '''Новизна''': Метод выделения всей незатенённой области радужки на основании анализа её малой части, применимый для широкого класса изображений.
+
=== Supervised rank aggregation with monotone feature transformation ===
=== Supervised rank aggregation with monotone feature transformation ===

Версия 08:48, 24 февраля 2015

Содержание

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

  • Название: Разработка алгоритма поиска параметров фибринолиза.
  • Задача: Задан набор снимков роста фибринового сгустка, полученных в процессе исследования тромбодинамики и [1]. Требуется разработать алгоритм поиска координат отрезка и угла наклона линии активатора по серии снимков. Протестировать разработанный алгоритм на разных видах фибринолиза и примерах, где данный процесс отсутствует.
  • Данные: Массив снимков для каждого исследования формата 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.

По мотивам Липатовой

  • Название: Supervised rank aggregation with monotone feature transformation.
  • Задача: Сравниваются подходы к кластеризации временных рядов. Требуется кластеризовать набор временных рядов и приблизить каждый ряд прогностической моделью. Разница рассматриваемых подходов заключается в порядке выполнения шагов: 1) вначале выполнить кластеризацию, а затем приближать ряды/кластеры моделями или 2) вначале приблизить каждый ряд моделей, а затем кластеризовать набор рядов, используя информацию о сходстве моделей. Исследования, проведенные в [1] позволяют предположить, что второй подход точнее. Предлагается также рассмотреть комбинированный подход, при котором выбор модели и кластеризация временных рядов происходят одновременно [2].
  • Данные: Временные ряды акселерометра, описывающие различные типы человеческой активности.
  • Литература
    • [1] М. Кузнецов. Классификация объектов сложной структуры. pdf
    • [2] А. Липатова. Одновременная кластеризация набора временных рядов и соответствующих им прогностических моделей. pdf
  • Базовой алгоритм: Кластеризация временных рядов на основе набора интегральных признаков: среднее, дисперсия, максимальное значение и другие статистики (см. [1]).
  • Решение: Предлагается сравнивать модели как векторы их прогнозов. Тогда расстояния между прогнозами всех рядов всеми моделями образуют четырехиндексную матрицу. Среза матрицы, минимизирующего внутрикластерное расстояние между рядами и моделями, выбирается генетическим алгоритмом.
  • Новизна: Предложен более точный метод кластеризации набора временных рядов.

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

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

  • Задача: аналогично задаче о новых товарах. Гипотеза: в продажах наблюдается взаимозаменямость товаров, проявляющаяся в виде:
    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 лучших функций с оценками качества.
  • Литература
    • Описание задачи
    • Описание коллекции данных, используемых для оценки функций, и процедуры оценки. pdf
  • Базовой алгоритм: Алгоритм полного перебора допустимых суперпозиций порождающих функций.
    • 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.

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

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