Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Компьютерное зрение: обучение методов распознавания со слабой разметкой данных

Speaker: 
Иван Лаптев (INRIA Paris-Rocquencourt, France)
Date: 
Monday, November 17, 2014 - 18:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

Недавний прогресс в компьютерном зрении тесно связан с методами машинного обучения и использованием большого количества данных. Тогда как количество видео и изображений практически неограниченно, их ручная разметка, необходимая для методов обучения с учителем, часто слишком дорога или невозможна. Для решения этой проблемы, в этом докладе мы сосредоточимся на методах обучения допускающих неполную и шумную разметку данных. В первой части мы рассмотрим обучение распознавания событий по видео и соответствующим текстовым описаниям. Я опишу постановку задачи в форме квадратичного программирования и продемонстрирую успешное применение метода к автоматическому обучению действий людей и имен актеров по видео из фильмов и соответствующим сценариям. Во второй части доклада мы остановимся на распознавании изображений и обсудим метод обучения основанный на сверточных нейронных сетях адаптированных к использованию слабой разметки данных. Представленный метод позволяет распознавать и находить местоположение объектов и действий людей на изображениях без использования информации о местоположении при тренировке. К удивлению, данный метод достигает высоких результатов распознавания, не уступающих по качеству лучшим аналогам использующим полную разметку для тренировки.

English version. Computer Vision: Weakly-supervised learning from images and video.
Recent progress in visual recognition goes hand-in-hand with the supervised learning and large-scale training data. While the amount of existing images and videos is huge, their detailed annotation is expensive and often prohibitive. To address this problem, in this talk we will focus on weakly-supervised learning methods using incomplete and noisy annotation for training. I will first address the learning of human actions from videos and corresponding video scripts. I will describe our recent formulation of this problem in the form of a quadratic program with constraints and will show its successful application to the joint learning of actions and actors from movies and corresponding movie scripts. In the second part of the talk I will focus on recognition from still images and will describe our work on weakly supervised convolutional neural networks. I will present a network that learns to recognize and localize objects as well as human actions without using location supervision at the training time. Somewhat surprisingly, our weakly-supervised method achieves state-of-the-art performance comparable to its strongly-supervised counterparts.

Short bio.
Ivan Laptev is a research director at INRIA Paris-Rocquencourt, France. He received Habilitation degree in 2013 from École Normale Supérieure (ENS) in Paris. He also received a PhD degree in Computer Science from the Royal Institute of Technology (KTH) in 2004 and a Master of Science degree from the same institute in 1997. He was a research assistant at the Technical University of Munich (TUM) during 1998-1999. He has joined INRIA as a postdoc in 2004 and became a full-time INRIA researcher in 2005. Ivan's main research interests include visual recognition of human actions, objects and interactions. He has published over 50 papers at international conferences and journals of computer vision and machine learning. He serves as an associate editor of IJCV, TPAMI and IVC journals, he was/is an area chair for CVPR 2010, ICCV 2011, ECCV 2012, CVPR 2013, ECCV 2014, ACCV 2014 and CVPR 2015, he has co-organized several tutorials, workshops and challenges on human action recognition at major computer vision conferences. He has also co-organized a series of INRIA summer schools on computer vision and machine learning (2010-2013). Ivan was awarded ERC Starting Grant in 2012.



Решение задачи о гамильтоновом пути с помощью базиса совершенных паросочетаний

Speaker: 
Павел Кунявский
Date: 
Monday, October 27, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

В докладе будет рассказано вероятностное решение задачи о гамильтоновом цикле за время O*(1.888^n) в неориентированном графе, в ориентированном двудольном из статьи Цыгана, Кратча и Недерлофа [STOC 2013]. Алгоритм основан на разложении гамильтонова пути на два полных паросочетания, и проверки на тождественное равенство нулю
специального многочлена над достаточно большим полем характертистики 2. Построение базиса паросочетаний позволяет сгруппировать части многочлена и вычислить их быстрее. Если останется время, будет также рассказан вероятностный FPT-алгоритм, параметризованный путевой шириной, со временем работы O*((2 + \sqrt(2))^pw), использующий тот же базис.



Решение задачи о k-пути в неориентированных графах за 2^{3k/4}

Speaker: 
Александр Куликов
Date: 
Monday, October 6, 2014 - 18:00
Place: 
Аудитория 106, ПОМИ
Abstract: 

Будет рассказан недавний алгоритм Бьорклунда, Хусфельда, Каски, Коивисто решения задачи нахождения просто пути длины k в неориентированном графе за время O^*(2^{3k/4}). Из этого, в частности, следует, что найти гамильтонов путь в неориентированном графе можно быстрее 2^n. Алгоритм основан на построении специального многочлена, в котором каждому простому k-пути соответствует уникальный моном, а самопересекающиеся k-пути разбиваются на пары с одинаковыми мономами. Таким образом, данный многочлен тождественно равен нулю в поле характеристики два (достаточно большого размера) тогда и только тогда, когда в графе есть простой k-путь.



Схемы со средней входящей степенью

Speaker: 
Дмитрий Соколов
Date: 
Monday, September 29, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

В докладе мы рассмотрим булевы схемы, в которых входная степень гейта ограничена линейной функцией от числа переменных. Мы докажем оценку \Omega(log^2 n) на явную функцию для подобных схем. Будет продемонстрирован метод применения коммуникационной сложности для доказательства нижних оценок на размер схем.



Introduction to online algorithms

Speaker: 
Sushmita Gupta
Date: 
Monday, September 22, 2014 - 18:00
Place: 
ПОМИ РАН, Мраморный зал
Abstract: 

In this lecture we will survey the area of online algorithms using some well known examples and problems. We will look at classical approaches as well as new ones, and discuss the underlying principles and objectives that drive research in the online paradigm.


Pages