Участник:Anastasiya/Черновики

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

Содержание 1 Список проектов 1.1 Задача 1 1.2 Задача 2 1.3 Задача 2.5 1.4 Задача 3 1.5 Задача 4 1.6 Задача 5 1.7 Задача 6 1.8 Задача 7 1.9 Задача 8 1.10 Задача 9 2 Дополнительные задачи 2.1 Задача Максимов + 2.2 Задача Антиплагиат + 2.3 Задача Хританкова (Transfer Learning)

Список проектов

Шаблон описания проекта — научной статьи

• Название: Название, под которым статья подается в журнал.
• Задача: Описание или постановка задачи. Желательна постановка в виде задачи оптимизации (в формате argmin). Также возможна ссылка на классическую постановку задачи.
• Данные: Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку.
• Литература: Список научных работ, дополненный 1) формулировкой решаемой задачи, 2) ссылками на новые результаты, 3) основной информацией об исследуемой проблеме.
• Базовой алгоритм: Ссылка на алгоритм, с которым проводится сравнение или на ближайшую по теме работу.
• Решение: Предлагаемое решение задачи и способы проведения исследования. Способы представления и визуализации данных и проведения анализа ошибок, анализа качества алгоритма.
• Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).
• Авторы: эксперт, консультант.

Задача 1

• Название: Классификация видов деятельности человека по измерениям фитнес-браслетов.
• Задача: По измерениям акселерометра и гироскопа требуется определить вид деятельности рабочего. Предполагается, что временные ряды измерений содержат элементарные движения, которые образуют кластеры в пространстве описаний временных рядов. Характерная продолжительность движения – секунды. Временные ряды размечены метками вида деятельности: работа, отдых. Характерная продолжительность деятельности – минуты. Требуется по описанию временного ряда и кластера восстановить вид деятельности.
• Данные: Временные ряды акселерометра WISDM (Временной ряд (библиотека примеров), раздел Accelerometry).
• Литература:
  • Карасиков М.Е., Стрижов В.В. Классификация временных рядов в пространстве параметров порождающих моделей // Информатика и ее применения, 2016. [URL]
  • Кузнецов М.П., Ивкин Н.П. Алгоритм классификации временных рядов акселерометра по комбинированному признаковому описанию // Машинное обучение и анализ данных. 2015. T. 1, № 11. C. 1471 - 1483. [URL]
  • Исаченко Р.В., Стрижов В.В. Метрическое обучение в задачах многоклассовой классификации временных рядов // Информатика и ее применения, 2016, 10(2) : 48-57. [URL]
  • Задаянчук А.И., Попова М.С., Стрижов В.В. Выбор оптимальной модели классификации физической активности по измерениям акселерометра // Информационные технологии, 2016. [URL]
  • Motrenko A.P., Strijov V.V. Extracting fundamental periods to segment human motion time series // Journal of Biomedical and Health Informatics, 2016, Vol. 20, No. 6, 1466 - 1476. [URL]
  • Ignatov A., Strijov V. Human activity recognition using quasiperiodic time series collected from a single triaxial accelerometer // Multimedia Tools and Applications, 2015, 17.05.2015 : 1-14. [URL]
• Базовой алгоритм: Базовый алгоритм описан в работах [Карасиков, Стрижов: 2016] и [Кузнецов, Ивкин: 2014].
• Решение: Найти оптимальный способ сегментации и оптимальное описание временного ряда. Построить метрическое пространство описаний элементарных движений.
• Новизна:: Соединение двух характеристических времен описания жизни человека, комбинированная постановка задачи.
• Авторы: В.В. Стрижов, М.П. Кузнецов, П.В. Левдик.

Задача 2

• Название: Построение аппроксимирующего описания скалограммы в задаче прогнозирования движений по электрокортикограмме.
• Задача: В рамках решения задачи декодирования сигналов ECoG решается задача классификации движений по временным рядам показаний электродов. Инструментами для извлечения признаков из временных рядов ECoG являются коэффициенты вейвлет-преобразования исследуемого сигнала [Макарчук 2016], на основе которых для каждого электрода строится скалограмма - двумерный массив признаков в пространстве частота-время. Объединение скалограмм для каждого электрода даёт признаки временного ряда в пространственно-частотно-временной области. Построенное таким образом признаковое описание заведомо содержит мультикоррелирующие признаки и является избыточным. Требуется предложить метод снижения размерности признакового пространства.
• Данные: Измерения положений пальцев при совершении простых жестов. Описание экспериментов данные.
• Литература:
  • Макарчук Г.И., Задаянчук А.И. Стрижов В.В. 2016. Использование метода частичных наименьших квадратов для декодирования движения руки с помощью ECoG сигналов у обезьян. pdf
  • Карасиков М.Е., Стрижов В.В. Классификация временных рядов в пространстве параметров порождающих моделей // Информатика и ее применения, 2016. [URL]
  • Кузнецов М.П., Ивкин Н.П. Алгоритм классификации временных рядов акселерометра по комбинированному признаковому описанию // Машинное обучение и анализ данных. 2015. T. 1, № 11. C. 1471 - 1483.
• Базовой алгоритм: PLS

Chen C, Shin D, Watanabe H, Nakanishi Y, Kambara H, et al. (2013) Prediction of Hand Trajectory from Electrocorticography Signals in Primary Motor Cortex. PLoS ONE 8(12): e83534.

• Решение: Для снижения размерности предлагается использовать метод локальной аппроксимации, предложенный в [Кузнецов 2015] использованный для классификации акселерометрических временных рядов [Карасиков 2016].
• Новизна: Предложен новый метод восстановления движений на основе электрокортикограмм.
• Авторы: Стрижов.

Задача 2.5

• Название: Выбор признаков в задаче распознавания активности областей головного мозга.
• Задача: Решается задача восстановления координат конечности испытуемого на основе измерений активности головного мозга. Каждому обхъекты выборки, описываемому трехиндексной матрцей пространственных, временных и частотных признаков, требуется сопоставить 3D координаты конечности испытуемого.
  • Постановка задачи и описание процесса построения выборки
• Данные: Описание эксперимента и ссылка на данные
• Литература:
  • Andrey Eliseyev and Tetiana Aksenova. Penalized multi-way partial least squares for smooth trajectory decoding from lectrocorticographic (ecog). PLoS ONE, 11(5):e0154878, 2016.
  • Andrey Eliseyev, Cecile Moro, Thomas Costecalde, Napoleon Torres, Sadok Gharbi, Corinne Mestais, Alim Louis Benabid, and Tatiana Aksenova. Iterative n-way partial least squares for a binary self-paced brain-computer interface in freely moving animals. J. Neural EngJournal of Neural Engineering, 8, 2011.
  • Aleksandr Katrutsa and Vadim Strijov. Comprehensive study of feature selection methods to solve multicollinearity problem according to evaluation criteria. Expert Systems with Applications, 2017.
• Базовой алгоритм: NPLS или другие модификации [Eliseyev 2016, Eliseev 2011]
• Решение: Предлагается сравнить базовые методы с методом [Katrutsa 2017]
• Новизна: Алгоритм выбора признаков [Katrutsa 2017] был предложен для двухиндексных данных и при использовании тензорных (многоиндексных) признаковых описаний требует модификации.
• Авторы: эксперт, консультант.

Задача 3

• Название: Multiple Manifold Learning (Joint diagonalization for 3D shapes - AJD on Hessian matrices).
• Задача: Построение оптимального алгоритма для задачи Multiple Manifold Learining. Пространство движений эластичного тела задается собственными векторами гессиана. Требуется найти общее low-rank приближение пространства движений двух эластичных тел.
• Данные: Белковые структуры в двойных конформациях из PDB, около 100 наборов из статьи https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4677049/
• Литература:
  • Tirion, M. M. (1996). Large amplitude elastic motions in proteins from a single-parameter, atomic analysis. Physical Review Letters, 77(9), 1905.
  • Moal, I. H., & Bates, P. A. (2010). {SwarmDock} and the Use of Normal Modes in Protein-Protein Docking. IJMS, 11(10), 3623–3648. https://doi.org/10.3390/ijms11103623
• Базовой алгоритм: AJD algorithm: http://perso.telecom-paristech.fr/~cardoso/jointdiag.html, AJD algorithms implemented as part of Shogun ML toolbox http://shogun-toolbox.org, http://shogun-toolbox.org/api/latest/classshogun_1_1CApproxJointDiagonalizer.html.
• Решение: Вычисление гессианов (C++ код у Сергея), изучение и запуск стандартных алгоритмов совместной диагонализации для первых n нетривиальных собственных векторов, анализ функций потерь, адаптирование стандартного алгоритма для решения исходной задачи.
• Новизна: При помощи простых моделей теории эластичности с одним или несколькими свободными параметрами можно описать тепловые флуктуации в белках. Однако такие модели не описывают переходы между несколькими стабильными конформациями в белках. Целью данной работы является доработка эластичной модели так, чтобы она также описывала пространство конформационных изменений.
• Авторы: Грудинин Сергей, консультант: Карасиков Михаил.

Задача 4

• Название: Convex relaxations for multiple structure alignment (synchronization problem for SO(3)).
• Задача: Найти преобразования для одновременного выравнивания третичных структур белков. Оптимизационная задача с исходной полиномиальной функцией потерь невыпукла. Если структуры одинаковые (RMSD после выравнивания равно нулю), то выравнивать можно попарно. Однако, если это не так, то базовый алгоритм, вообще говоря, не находит оптимум исходной задачи.
• Данные: Структуры белков в PDB формате в различных состояниях и системах координат.
• Литература:
  • Multiple structural alignment:
    1. Kearsley.S.K. (1990)7. Comput. Chem., 11, 1187-1192.
    2. Shapiro., BothaJ.D., PastorA and Lesk.A.M. (1992) Acta Crystallogr., A48, 11-14.
    3. Diamond,R. (1992) Protein Sci., 1, 1279-1287.
    4. May AC, Johnson MS, Improved genetic algorithm-based protein structure comparisons: pairwise and multiple superpositions. Protein Eng. 1995 Sep;8(9):873-82.
  • Synchronisation problem:
    1. O. Özyeşil, N. Sharon, A. Singer, ``Synchronization over Cartan motion groups via contraction”, Available at arXiv.
    2. L. Wang, A. Singer, ``Exact and Stable Recovery of Rotations for Robust Synchronization”, Information and Inference: A Journal of the IMA, 2(2), pp. 145--193 (2013).
    3. Semidefinite relaxations for optimization problems over rotation matrices J Saunderson, PA Parrilo… - Decision and Control ( …, 2014 - ieeexplore.ieee.org
    4. Spectral synchronization of multiple views in SE (3) F Arrigoni, B Rossi, A Fusiello - SIAM Journal on Imaging Sciences, 2016 - SIAM
    5. Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition, F Arrigoni, A Fusiello, B Rossi, P Fragneto - arXiv preprint arXiv: …, 2015 - arxiv.org
  • Spectral relaxation for SO(2)
    1. A. Singer, Angular synchronization by eigenvectors and semidefinite programming, Applied and Computational Harmonic Analysis 30 (1) (2011) 20 – 36.
  • Spectral relaxation for SO(3)
    1. M.Arie-Nachimson,S.Z.Kovalsky,I.Kemelmacher-Shlizerman,A.Singer,R.Basri,Global motion estimation from point matches, in: International Conference on 3D Imaging, Modeling, Processing, Visualization and Transmission, 2012, pp. 81–88.
    2. A. Singer, Y. Shkolnisky, Three-dimensional structure determination from common lines in cryo-em by eigenvectors and semidefinite programming, SIAM Journal on Imaging Sciences 4 (2) (2011) 543– 572.
• Базовой алгоритм: Алгоритм локального (попарного) выравнивания. Kearsley.S.K. (1989) Acta Crystallogr., A45, 208-210 ; Rapid determination of RMSDs corresponding to macromolecular rigid body motions

Petr Popov, Sergei Grudinin, Journal of Computational Chemistry, Wiley, 2014, 35 (12), pp.950-956. <10.1002/jcc.23569> DOI : 10.1002/jcc.23569

• Решение: Два варианта постановки оптимизационных задач (через матрицы поворота и через кватернионы). Релаксация полученных задач выпуклыми, сравнение решений задачи базовым алгоритмом и релаксациями (spectral relaxation, SDP).
• Новизна: Метод, выравнивающий структуры, минимизируя функцию потерь, учитывающую все попарные потери.
• Авторы: Грудинин Сергей, консультант: Карасиков Михаил.

Задача 5

• Название: Локальная аппроксимация временных рядов для построения признакового описания в задачах классификации и прогнозирования.
• Задача: Целью проекта является создание инструмента для анализа этой проблемы. Исследуется сегмент временного ряда. Требуется спрогнозировать класс сегмента. (Вариант: спрогнозировать окончание сегмента, последующий сегмент, его класс. При этом класс последующего сегмента может отличаться от класса предыдущего).
• Данные: Взять за основу выборку Santa Fe или WISDM (выборки состоят из сегментов со многими элементарными движениями и соответствующими сегментам метками классов), вариант OPPORTUNITY Activity Recognition Challenge.
• Литература:
  • Карасиков М.Е., Стрижов В.В. Классификация временных рядов в пространстве параметров порождающих моделей // Информатика и ее применения, 2016. [URL]
  • Кузнецов М.П., Ивкин Н.П. Алгоритм классификации временных рядов акселерометра по комбинированному признаковому описанию // Машинное обучение и анализ данных. 2015. T. 1, № 11. C. 1471 - 1483. [URL]
• Базовой алгоритм: [Карасиков 2016]
• Решение: См. описание задачи.
• Новизна: При создании метапрогностических моделей (моделей прогнозирования прогностических моделей) остается открытой проблема использования значений параметров локальных моделей при создании метамоделей. Цель нижеприведенного проекта - создание инструмента для анализа этой проблемы.
• Авторы: Стрижов

Задача 6

• Название: Выбор оптимальной модели рекуррентной сети в задачах поиска парафраза
• Задача: Задана выборка пар предложений с метками <<похожие>> и <<непохожие>>. Требуется построить рекуррентную сеть небольшой сложности (т.е. с небольшим количеством параметров), доставляющую минимум ошибке классификации пар предложений.
• Данные: Предлагается рассмотреть две выборки: Microsoft Paraphrase Corpus (небольшой набор предложений) и PPDB (набор коротких сегментов, не всегда корректная разметка)
• Литература:
  • [1] Пошаговое описание реализации рекуррентной сети LSTM
  • [2] Алгоритм прореживания, основанный на построении сети, обладающей минимальной длиной описания
  • [3] Optimal Brain Damage
• Базовый алгоритм: В качестве базового алгоритма могут выступать:
  1. Решение без прореживания
  2. Решение, описанное в [3]
  3. Otimal Brain Damage
• Решение: Предлагается рассмотреть метод прореживания, описанный в [3] с блочной матрицей ковариаций: в качестве блоков выступают либо нейроны, либо параметры с группировкой по входным признакам.
• Новизна: Предложенный метод позволит эффективно снижать сложность рекуррентной сети с учетом взаимосвязи между нейронами или входными признаками.
• Авторы: Олег Бахтеев, консультант

Задача 7

• Название: Детектирование внутреннего плагиата
• Задача: Решается задача выявления внутренних заимствований в тексте. Требуется проверить гипотезу о том, что заданный текст написан единственным автором, и в случае ее невыполнения выделить заимствованные части текста. Заимствованием считается часть текста, предположительно написанная другим автором и содержащая характерные отличия от стиля основного автора. Требуется разработать такую стилевую функцию, которая позволяет с высокой степенью достоверности отличить стиль основного автора текста от заимствований.
• Данные: Предлагается рассмотреть корпус PAN-2011, PAN-2016
• Литература:
  • [1] Пошаговое описание реализации рекуррентной сети LSTM
  • [2] Алгоритм кластеризации авторов
  • [3] Statistical Language Models Based on Neural Networks
  • [4] Methods for intrinsic plagiarism detection and author diarization
• Базовый алгоритм: В качестве базового алгоритма может выступать решение, описанное в [4].
• Решение: Предлагается рассмотреть метод, описанный в [2] и строить стилевую функцию, основываясь на выходах нейронной сети.
• Новизна: Предполагается, что построение стилевой функции предлагаемым методом может дать прирост качества по сравнению с типичными решениями этой задачи.
• Авторы: Рита Кузнецова, консультант

Задача 8

• Название: Адаптивные релаксации NP трудных задач через машинное обучение
• Задача: Современные задачи оптимизации потоков мощности в энергетических сетях приводят к невыпуклым задачам оптимизации с большим количеством ограничений. Аналогичные по структуре постановки возникают также в ряде других инженерных задач и в классических задачах комбинаторной оптимизации. Традиционный подход к решению подобных NP трудных задач состоит в написании их выпуклых релаксаций (semidefinite/SDP, second order conic/SOCP, etc), имеющих как правило существенно большее множество допустимых решений, чем в исходной задаче. И последующей проекцией полученного решения в область, где выполнены ограничения исходной задачи. Во многих практических случаях, качество полученного таким образом решения невелико. Альтернативные подходы, например MILP (mixed integer linear programming) релаксации, существенно более трудоемки по времени, но приводят к более точно у ответу.

Основная проблема состоит в невозможности применения известных методов для решения задач большой размерности (сети из 1000 узлов и более). Одним из ключевых препятствий является не столько размерность задачи, сколько большое число ограничений. Вместе с тем, в реальных задачах можно выделить небольшое множество ограничений такое, что множества допустимых точек в выделенном множестве и в исходном весьма близки. Это позволит заменить задачу на иную, с меньшим числом ограничений, что повысит скорость используемых алгоритмов. Предлагается использовать методы машинного обучения для построения указанного множества наиболее важных ограничений.

• Литература: Методы семплинга/машинного обучения:
  1. Beygelzimer, A., Dasgupta, S., & Langford, J. (2009, June). Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning (pp. 49-56). ACM.
  2. Tong, S., & Koller, D. (2001). Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov), 45-66.
  3. Owen, A., & Zhou, Y. (2000). Safe and effective importance sampling. Journal of the American Statistical Association, 95(449), 135-143.

Релаксации: Nagarajan, H., Lu, M., Yamangil, E., & Bent, R. (2016). Tightening McCormick Relaxations for Nonlinear Programs via Dynamic Multivariate Partitioning. arXiv preprint arXiv:1606.05806.

• Данные: данные ieee + matpower содержащие описания энергетических сетей и режимов их функционирования.
• Новизна: указанный подход, по видимому, является первым применением методов прикладной статистики/машинного обучения для решения трудных оптимизационных задач. Мы ожидаем существенный выигрыш в трудоемки стиль методов
• Автор: консультант: Юрий Максимов, эксперт: Михаил Чертков

Задача 9

• Название: Оптимальный алгоритм для восстановления динамических моделей.
• Задача: Стандартная постановка задач машинного обучения в контексте обучения без учителя (unsupervised learning) предполагает, что примеры (samples) независимы и получены из одного распределения вероятности. Однако зачастую наблюдаемые данные имеют динамическое происхождение и являются коррелироваными. Задача состоит в разработке эффективного метода для восстановления динамической графической модели (графа и параметров модели) по наблюдаемым коррелированным динамическим конфигурациям. Эта задача важна с теоретической точки зрения и имеет массу приложений. Основой алгоритма будет служить адаптация нового оптимального метода экранирования взаимодействий (interaction screening), разработанного для модели Изинга. Процесс решения будет сочетать в себе знакомство с теоретическими методами компьютерных наук / машинного обучения и численные эксперименты.
• Данные: Симулированные динамические конфигурации спинов в кинетической модели Изинга.
• Литература:
  1. Lokhov et al., "Optimal structure and parameter learning of Ising models", arXiv:1612.05024 (2016) {https://arxiv.org/abs/1612.05024}
  2. Vuffray et al., "Interaction screening: efficient and sample-optimal learning of Ising models", NIPS 2016 {https://arxiv.org/abs/1605.07252}
  3. Decelle and Zhang, "Inference of the sparse kinetic Ising model using the decimation method", Phys. Rev. E 2016 {https://arxiv.org/abs/1502.01660}
  4. Bresler et al., "Learning graphical models from the Glauber dynamics", Allerton 2014 {https://arxiv.org/abs/1410.7659}
  5. Zeng et al., "Maximum likelihood reconstruction for Ising models with asynchronous updates", Phys. Rev. Lett. 2013 {https://arxiv.org/abs/1209.2401}
• Базовой алгоритм: Динамический метод экранирования взаимодействий. Сравнение с методом максимального правдоподобия.
• Новизна: В настоящее время оптимальный (т.е. использующий минимальное возможное количество примеров) алгоритм для данной задачи неизвестен. Динамический метод экранирования взаимодействия имеет хорошие шансы окончательно "закрыть" эту задачу, т.к. является оптимальным для статической задачи.
• Автор: Консультанты Андрей Лохов, Юрий Максимов. Эксперт Михаил Чертков

Дополнительные задачи

Задача Максимов +

Задача Антиплагиат +

• Название: Отбор кандидатов в задаче поиска текстовых заимствований с перефразированием, основанный на векторизации текстовых фрагментов.
• Задача: Поиск текстовых заимствований по коллекции документов предполагает отбор небольшого множества кандидатов для последующего детального анализа. Задача отбора кандидатов формулируется как поиск оптимального ранжирования документов коллекции по запросу относительно некоторой функции, являющейся оценкой для общей длины заимствований из документа коллекции в документ-запрос.
• Данные: PAN
• Литература: Романов А.В., Хританков А.С. Отбор кандидатов при поиске заимствований в коллекции документов на иностранном языке pdf
• Базовый алгоритм: метод шинглов с построением обратного индекса.
• Решение: Векторизация фрагментов текста (word embeddings + свёрточные / рекуррентные нейронные сети) и последующий поиск ближайших объектов в многомерном метрическом пространстве.
• Новизна: новый подход к решению задачи.
• Авторы: Алексей Романов (консультант)

Задача Хританкова (Transfer Learning)

• Название: Применение сетей глубокого обучения для переноса моделей классификации в случае недостаточного объема данных.
• Задача:
  1. Разработать алгоритм вычисления набора скрытых признаков в задаче symmetric homogeneous transfer learning , решение задачи классификации в котором не зависит от исходной области, и который не хуже, чем при решении для каждого области отдельно (transfer error) для случая небольших размеров выборки с ошибками в разметке
  2. Разработать алгоритм перехода к скрытому набору признаков без использования разметки (unsupervised domain adaptation)
• Данные: teraPromise-CK (33 датасета с одинаковыми признаками, но разными распределениями).
• Литература:Базовая статья: Xavier Glorot , Antoine Bordes , Yoshua Bengio. (2011) Domain Adaptation for Large-Scale sentiment classification: A Deep Learning approach / In Proceedings of the Twenty-eight International Conference on Machine Learning, ICML.

Статьи с идеями по доработкам алгоритма будут выданы на руки (несколько).

• Базовой алгоритм: SDA (Stacked Denoising Autoencoder) – описан в статье базовой статье Glorot et al.
• Решение: Взять базовый алгоритм, а) попробовать улучшить для применения к небольшим датасетам 100-1000 объектов (когда и применяется transfer learning) путем применения регуляризаторов, корректировкой архитектуры автокодировшика, корректировки алгоритма обучения (например, bootstrapping) б) исследовать модель на устойчивость к ошибкам в разметке (label corruption / noisy labels) и предложить доработку для повышения устойчивости (robustness).
• Новизна: Получение устойчивого алгоритма переноса моделей классификации на небольших объемах данных с ошибками в разметке.
• Авторы: Хританков