Seminars

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



Mathematics in Synchronization and Concurrency

Speaker: 
Пётр Кузнецов (Telecom ParisTech)
Date: 
Monday, December 22, 2014 - 18:00
Place: 
Аудитория 106, ПОМИ
Abstract: 

Practically all computing systems, from fire alarms to Internet-scale services, are nowadays distributed: they consist of a number of computing units performing independent computations and communicating with each other to synchronize their activities. Therefore, understanding fundamentals of distributed computing is of crucial importance.

The main complication here is the immense diversity of applications, models of distributed computations, and performance metrics, combined with the lack of mathematical tools to handle this complexity. In this talk, we discuss understanding of what can and what cannot be implemented in specific distributed environments, with a focus on how to apply modern mathematics in deriving new algorithms and lower bounds for distributed computing problems.



Алгоритм Эпштейна-Бейгеля решения задачи нахождения 3-раскраски графа

Speaker: 
Сергей Копелиович
Date: 
Monday, December 15, 2014 - 18:00
Place: 
Мраморный зал ПОМИ РАН
Abstract: 

1. Оценки на смежные задачи: CSP, Vertex 3-List-Coloring, Edge 3-Coloring, 3-SAT.
2. Применение результатов для CSP и Vertex 3-Coloring для решения перечисленных задач.
3. Основная идея алгоритма. Простой результат за 1.34488^n.
4. Улучшения до 1.3289^n.



Прямо-двойственный метод в приближённых алгоритмах

Speaker: 
Всеволод Опарин
Date: 
Monday, December 1, 2014 - 19:00
Place: 
ПОМИ, аудитория 106
Abstract: 

Доклад будет о различных техниках получения приближенных алгоритмов через прямо-двойственный метод. Общую идею метода я расскажу на примере задачи о взвешенном покрытии множествами (демонстрация метода, f-приближение, где f — максимальное число множеств покрывающее отдельный элемент). Потом будут различные вариации того, как метод применять, на задачах о поиске кратчайшего пути в графе (зачистка прямого решения, алгоритм Дейкстра), дереве Штейнера (множественное увеличение переменных, 2-приближение) и рюкзаке (усиление неравенств, 2-приближение). Если успею, то будет еще рассказ про uncapacity facility location problem.



Законы нуля или единицы для случайных графов

Speaker: 
Максим Жуковский (Яндекс)
Date: 
Monday, November 24, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

В докладе речь пойдет об асимпотическом поведении свойств первого порядка случайного графа Эрдеша-Реньи G(n,p). В 1988 году Дж. Спенсер и С. Шела доказали, что если p=n^{-a}, a - положительное иррациональное число, то для любого свойства первого порядка с вероятностью, стремящейся к 1, случайный граф либо обладает этим свойством, либо нет (иными словами, выполнен закон нуля или единицы). Если же a из интервала (0,1) - рациональное число, то закон нуля или единицы не выполнен. Позже мной было доказано, что для любого свойства первого порядка с ограниченной числом k кванторной глубиной выполнен закон нуля или единицы, если a принадлежит интервалам (0,1/(k-2)) и (1-1/(2^{k}-2),1). На концах этих интервалов закон нуля или единицы не выполнен.

В 1990 году Дж. Спенсер доказал, что существует свойство первого порядка L и бесконечно много таких рациональных чисел a из интервала (0,1), что вероятность того, что случайный граф G(n,n^{-a}) обладает свойством L, не стремится ни к 0, ни к 1 (множество S(L) таких рациональных чисел a называется спектром формулы L). В докладе буде рассказано о недавней совместной работе с Дж. Спенсером, в которой нам удалось получить новые результаты о распределении точек в спектре.



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

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.


Pages