28 мая 2015 года

Вероятностное программирование

Борис Янгель, Компания «Яндекс»

Время: 16:40 - 18:00

Вероятностное моделирование является одним из мощнейших инструментов для специалиста по анализу данных (data scientist). К сожалению, для его использования необходимо не только уверенно владеть аппаратом теории вероятностей и математической статистики, но и знать детали работы алгоритмов приближенного байесовского вывода, что делает порог вхождения очень высоким. В этом докладе я расскажу про сравнительно молодую парадигму в машинном обучении, вероятностное программирование, задача которой — сделать всю мощь вероятностного моделирования доступной любому человеку, имеющему опыт программирования и минимальный опыт анализа данных.

Афиша доклада Б. Янгеля (PDF, 519 Кб) 

21 мая 2015 года

Knowledge-based Verification and Construction of Distributed and Constrained Systems

Susanne Graf, VERIMAG, Grenoble

16:40 - 18:00

We explore here the problem from the knowledge perspective: a process can decide to execute a local action when it has the knowledge to do so. We discuss typical knowledge atoms, useful for expressing local enabling conditions with respect to different notions of correctness, as well as different means for obtaining knowledge and for representing it locally in an efficient manner.

Our goal is to use such a knowledge-based representation of the distribution problem for either deriving distributed implementations automatically from global specifications on which some constraint is enforced — a difficult problem — or for improving the efficiency of existing protocols by exploiting local knowledge. We also argue that such a knowledge-based presentation helps achieving the necessary correctness proofs.

Beyond Worst Case Analysis of Graph Partitioning Algorithms

Konstantin Makarychev, Microsoft Research

Время: 18:30 - 20:00

Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomenon and to design algorithms that work well in real-life. In this talk, I will first discuss different ways of modelling “real-life” instances. Then, I will present a new semi-random semi-adversarial model for graph partitioning problems, a planted model with permutation-invariant random edges (PIE). This model is much more general than stochastic models considered previously. Finally, I will describe a “constant factor” approximation algorithm for finding the minimum balanced cut in graphs from this model.

Афиша докладов С. Граф и К. Макарычева (PDF, 587 Кб)

14 мая 2015 года

Computational Aspects of Monotone Dualization

Kazuhisa Makino, Research Institute for Mathematical Sciences, Kyoto University

Время: 16:40 - 18:00

Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including computer science, artificial intelligence, data mining, machine learning, and game theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 30 years. We briefly survey computational results for this problem, which includes the remarkable result by M.L. Fredman and L.G. Khachiyan that the problem is solvable in quasi-polynomial time (and thus most likely not coNP-hard), as well as on follow-up works.

Афиша доклада K. Makino (PDF, 426 Кб)

30 апреля 2015 года

Мин-плюс многочлены и циклические игры

Владимир Подольский, Математический институт им.В.А.Стеклова РАН / ФКН НИУ ВШЭ

Время: 16.40-18.00

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

В этом докладе мы рассмотрим алгоритмические задачи, связанные с мин-плюс многочленами. Более конкретно, нас будет интересовать разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP.

Второй результат, который планируется обсудить в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры.

Доклад основан на совместных работах с Д.Ю. Григорьевым.

Афиша доклада В. Подольского (PDF, 607 Кб)

22 апреля 2015 года

An Informatics View of The World

Dines Bjørner, Technical University of Denmark

Время: 16:40 - 18:00

Внимание: коллоквиум состоится в среду, в лекционном зале Евклид!

This talk is for beginners in the serious study of computer science. Behind its presentation lies the attitude that software, including programmes, denote mathematical objects. Through three examples I provide a glimpse into a universe of domains for which software is developed every day but for which, in most instances, there are no formal, i.e., mathematical understanding. The three examples are: road transport and platooning systems, oil/gas pipeline systems, and stock exchange sell offer/buy bid matching. The objective of this talk is to show you what it means to develop software using mathematics, albeit it new kind of mathematics, not differential equations, nor integrals, nor statistics, etc., but mathematical logic and abstract algebra, so that software can be shown correct, i.e., no bugs, no blue screen, and to met customers expectations!

Афиша доклада Д. Бьорнера (PDF, 334 Кб)

16 апреля 2015 года

Все, что вы хотели знать про молекулярную биологию, но не удосужились спросить

Михаил Гельфанд, Институт проблем передачи информации им. А.А. Харкевича РАН

Время: 16:40 - 18:00

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

Афиша доклада М. Гельфанда (PDF, 354 Кб)

2 апреля 2015 года

Статистические задачи идентификации сетевых структур

Валерий Калягин, НИУ ВШЭ Нижний Новгород

Время: 16:40 - 18:00

В сложных сетях, с помощью различных процессов фильтрации, могут быть выделены важные сетевые структуры, несущие содержательную информацию о сети. Среди сетевых структур традиционно рассматриваются: максимальное остовное дерево, максимально отфильтрованный планарный граф, отсеченный граф, максимальные клики и максимальные независимые множества отсеченного графа и другие. В условиях статистической природы исходных данных возникает задача идентификации сетевых структур. Доклад будет посвящен недавнему развитию этой темы в рамках теории одновременной проверки многих статистических гипотез (Multiple decision statistical procedures, multiple test procedures). Такой подход позволяет разработать методы оценки статистической неопределенности сетевых структур и выделить оптимальные и устойчивые статистические процедуры идентификации. Оказывается, что сетевые структуры, построенные по вероятностям совпадения знаков, оказываются предпочтительными перед структурами, построенными по классическим корреляциям Пирсона. Будут рассмотрены приложения результатов к анализу фондовых рынков.

19 марта 2015 года

Обобщенные паросочетания, или как заключать браки и распределять абитуриентов

Софья Кисельгоф, Международная научная лаборатория анализа и выбора решений НИУ ВШЭ

Время: 16:40 - 18:00

На практике часто возникает задача распределения объектов или людей в пары друг с другом, например, распределение сотрудников по вакансиям, формирование комитетов, распределение абитуриентов по вузам и др. Доклад посвящен теории и практике построения механизмов такого распределения с учетом предпочтений индивидов.

Афиша доклада С. Кисельгоф (PDF, 271 Кб)

5 марта 2015 года

Моделирование и анализ вычислительных процессов

Ростислав Яворский, ФКН НИУ ВШЭ

Время: 16:40 - 18:00

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

Афиша доклада Р. Яворского (PDF, 346 Кб)

19 февраля 2015 года

Gaussian Multiplier Bootstrap in High Dimension with Applications to Model Selection

Владимир Спокойный, ПреМоЛаб МФТИ / Институт проблем передачи информации им. А.А. Харкевича РАН

Время: 16:40 - 18:00

Since its introduction in 1979 by Efron, the bootstrap became one of the most popular and effective methods in various statistical problems like confidence estimation, hypothesis testing, model selection, etc. However, validation of a bootstrap procedure is very involved and requires some advance tools from empirical process theory and Gaussian processes.

Most of these tools meet serious problems and challenges if the parameter dimension becomes large, much larger than the sample size. Recently Chernozhkov et al (2013, 2014) offered a new approach to statistical inference in high dimension which includes powerful result for Gaussian processes and random matrices, Gaussian approximation in high dimension, and Gaussian comparison. This talk reviews some of these results and tools and explains how they can be applied to the problems of subset estimation and sparse estimation problems.

Афиша доклада В. Спокойного (PDF, 286 Кб)

5 февраля 2015 года

Эпсилон-сложность непрерывных функций и её применения

Борис Дарховский, Институт системного анализа РАН

Совместная работа с A. Piryatinska (San Francisсo, USA)

Время: 16:40 - 18:00

Вводится новое понятие — эпсилон-сложность непрерывных функций. Это понятие полностью соответствует общей идее А.Н. Колмогорова о том, что такое «сложный объект». Установлено, что для широкого класса непрерывных функций эпсилон-сложность допускает удобное описание. Это обстоятельство позволяет предложить принципиально новую методологию для решения таких прикладных задач, как сегментация и классификация данных произвольной природы (стохастических, детерминированных или смешанных). Так как эпсилон-сложность является внутренней характеристикой данных, которая не связана с механизмом их генерации, новая методология не использует никакой априорной информации. В докладе приводятся некоторые результаты компьютерных экспериментов и обработки электроэнцефалограмм человека.

Афиша доклада Б. Дарховского (PDF, 360 Кб)

29 января 2015 года

Approximate Nearest Neighbor Search: Beyond Locality-Sensitive Hashing

Ilya Razenshteyn, MIT

Время: 16:40 - 18:00

In the Approximate Nearest Neighbor problem (ANN), we are given a set of n points in a d-dimensional space, and the goal is to build a data structure that, given a query point q, reports any point from P that is approximately closest to q.

Locality-Sensitive Hashing (LSH) is by now a standard technique for solving the ANN problem. In my talk I will define LSH and show several constructions of good hash families. Then I will state some limitations of LSH and describe a recent line of research that provides data structures for ANN that are provably (substantially) better than what LSH could possibly give.

The talk is partially based on a joint work with Alexandr Andoni (Simons Institute, previously Microsoft Research Silicon Valley). See http://www.ilyaraz.org/optimal_lsh.pdf for the paper.

Внимание! В 15:20, перед докладом И. Разенштейна, пройдет семинар НУЛ интеллектуальных систем и структурного анализа с докладом Артема Ревенко (НИУ ВШЭ, TU Dresden, TU Wien) «Автоматизация построения импликативных теорий».

Афиша доклада И. Разенштейна (PDF, 336 Кб)

22 января 2015 года

Математика больших данных: тензоры, нейросети, байесовский вывод

Дмитрий Ветров, ФКН НИУ ВШЭ

Время: 16:40 - 18:00

Человечество вступило в эпоху больших данных — время, когда объем доступной для анализа информации нарастает на порядки быстрее чем вычислительные мощности. Традиционные математические методы и модели в такой ситуации становятся неприменимы. Необходимо создание «новой математики», адаптированной под новые соотношения между данными и вычислительными ресурсами. Как можно хранить и обрабатывать многомерные массивы в линейных по памяти структурах? Что дает обучение нейронных сетей из триллионов триллионов нейронов и как можно осуществить его без переобучения? Можно ли обрабатывать информацию «на лету», не сохраняя поступающие последовательно данные? Как найти минимум функции за время меньшее, чем уходит на ее вычисление в одной точке? Что дает обучение по слаборазмеченным данным? И почему для решения всех перечисленных выше задач надо хорошо знать математику? Ответы на эти вопросы будут рассмотрены в докладе.

Афиша доклада Д. Ветрова (PDF, 334 Кб)

---

2014

30 декабря 2014 года

Probabilistic Graphical Models: Factor Graphs and More

Frederico Wadehn, ETH Zurich

Время: 16:00 - 17:30

Probabilistic graphical models together with dedicated algorithms such as belief propagation and other message passing algorithms allow a unified approach to a multitude of problems arising in signal processing, coding theory as well as in statistical inference in general. The following talk will briefly cover Bayesian networks and Markov random fields before focussing on factor graphs and related algorithms such as sum-product message passing. Various toy examples as well as an input estimation and a Bayesian inference algorithm using the factor graph description language will be shown.

Афиша доклада F. Wadehn (PDF, 479 Кб)

25 декабря 2014 года

Resource Reasoning in Program Analysis

Max Kanovich, University College London

Время: 16:40 - 18:00

The fundamental ideas of the resource logics (linear logic, separation logic) are presented in a semi-formal style.

For general resource models, on one hand, and for concrete heap-like models of practical interest, on the other hand, we get into the formalities, including the semantics of the assertion language and axioms and inference rules.

Surprisingly, as for the assertion language of separation logic, even purely propositional separation logic turns out to be undecidable, even for a concrete heap-like models of practical interest.

11 декабря 2014 года

Как устроен цвет

Дмитрий Николаев, Институт проблем передачи информации им. А.А. Харкевича РАН

Время: 16:40 - 18:00

Мы постучимся к вам в дверь и спросим, думали ли вы когда-нибудь о цвете.

Почему формальное определение цвета то ли есть, то ли нет, и связано ли это с тем, что его дал тот самый Шрёдингер? Что имел в виду Вейнберг, когда назвал свою революционную статью «геометрия цветов»? Почему у цветового треугольника два угла, хотя интуитивно кажется, что должен быть один? Почему обычный детский рисунок показывает, что у автора всё в порядке с цветовосприятием, и зачем художник-академист всю жизнь учится его отключать? Почему в цветовом пространстве находятся кластеры, но они не находятся? Почему любая женщина знает о явлении метамерии окрасок, а ученые всё время забывают? Сколько должно быть цветовых каналов у хорошего фотоаппарата? А у монитора? А почему ответ разный? А красок у принтера? Да вы шутите, сколько-сколько? Во что одета тётя на картинке, и почему это так же смешно, как lena512.tif?

Обо всем этом (и многом другом) вы узнаете, если придете к нам на коллоквиум.

Афиша доклада Д. Николаева (PDF, 167 Кб)

5 декабря 2014 года

RaaS and Ginseng: The Resource as a Service Cloud

Assaf Schuster, Technion

Время: 16:00 - 17:00

Cloud providers, such as Amazon EC2, would like to have satisfied clients. Who wouldn't? However, in order to maximize their marginal profit, they have to fit the clients on as few machines as possible.

One way providers can maximize clients' satisfaction while making best use of the resources is by renting precious physical memory to those clients who value it the most. But real-world cloud clients are selfish; they will only tell their providers the truth about how much they value memory when it is in the clients' best interest to do so. How, then, can cloud providers allocate memory efficiently to those (selfish) clients?

We present Ginseng, the first market-driven cloud system that solves this problem, allocating memory efficiently precisely to those selfish cloud clients who value it the most. Ginseng, built using the KVM hypervisor and libvirt, achieves a 6.2x--15.8x improvement (83%--100% of the optimum) in aggregate client satisfaction.

Energy efficient Cloud Computing

Dzmitry Kliazovich, University of Luxembourg

Время: 17:00 - 18:00

27 ноября 2014 года

Process Mining: Data Science in Action

Wil van der Aalst, Eindhoven University of Technology

Время: 16:40 - 18:00

Data science is the profession of the future, because organizations that are unable to use (big) data in a smart way will not survive. It is not sufficient to focus on data storage and data analysis. The data scientist also needs to relate data to process analysis. Process mining bridges the gap between traditional model-based process analysis (e.g., simulation and other business process management techniques) and data-centric analysis techniques such as machine learning and data mining. Process mining seeks the confrontation between event data (i.e., observed behavior) and process models (hand-made or discovered automatically). This technology has become available only recently, but it can be applied to any type of operational processes (organizations and systems). Example applications include: analyzing treatment processes in hospitals, improving customer service processes in a multinational, understanding the browsing behavior of customers using a booking site, analyzing failures of a baggage handling system, and improving the user interface of an X-ray machine. All of these applications have in common that dynamic behavior needs to be related to process models. Hence, prof. Wil van der Aalst refers to it in his talk as “data science in action”. Process mining provides not only a bridge between data mining and business process management; it also helps to address the classical divide between “business” and “IT”. Evidence-based business process management based on process mining helps to create a common ground for business process improvement and information systems development.

Афиша доклада Wil van der Aalst (PDF, 1.03 Мб)

13 ноября 2014 года

Применение алгоритмов многорукого бандита к задачам веб-поиска

Глеб Гусев, компания Яндекс

Время: 16:40 - 18:00

Доклад посвящен знаменитой проблеме многорукого бандита и ее применениям в веб-поиске. Проблема происходит от задачи игрока в казино, который дергает ручки игральных автоматов.

Шаг игры состоит в том, что игрок выбирает ручку, получает некоторый выигрыш, который является выборкой из некоторого заранее неизвестного вероятностного распределения, ассоциированного с данной ручкой, и обновляет информацию о наблюдаемых выигрышах выбранной ручки. Цель игрока --- максимизировать математическое ожидание суммарного выигрыша, полученного игроком в течение некоторого определенного количества шагов. Для этого ему приходится выбирать баланс между эксплуатированием ручек, которые которые приносили выигрыш в прошлом, и экспериментированием с ручками, которые недостаточно хорошо были опробованы ранее.

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

Афиша доклада Г. Гусева (PDF, 123 Кб)

23 октября 2014 года

Решетки замкнутых множеств для наук о данных

Сергей Кузнецов, ФКН НИУ ВШЭ

Время: 16:40 - 18:00

В докладе планируется затронуть следующие темы:

• решетки замкнутых множеств в математике 20-го века; сообщество специалистов: конференции и школы;
• основные определения: решетки, соответствия Галуа, понятия, импликации, базисы импликаций;
• функциональные зависимости в базах данных и импликации на признаках;
• вычислительные задачи и алгоритмы Анализа Формальных Понятий;
• решетки понятий и ассоциативные правила в Data Mining;
• за пределами бинарных данных: решетки замкнутых описаний на основе графов, последовательностей, кортежей числовых интервалов.

Афиша доклада С. Кузнецова (PDF, 119 Кб)

9 октября 2014 года

On scale invariance, multifractal formalism, and their applications

Geoffrey Gérard Décrouez, ФКН НИУ ВШЭ

Время: 16:40 - 18:00

Scale invariance represents a relatively new way to analyse and model real world data. It find numerous applications in many diverse fields, including the study of natural phenomena in physics, biology, but also man-made applications such as signal and image processing. Data presenting scale invariance do not have a well defined time scale playing a dominant role. Instead, their dynamics can be understood from the relationship existing across a whole range of scales. Multifractal theory is particularly useful for analysing this kind of data.In this talk I will present some basic notions of fractal theory, and then discuss the multifractal formalism.

I will illustrate the theory with examples taken from the literature and my research, including multiplicative cascades on trees and random processes in multifractal time.

Афиша доклада Geoffrey Gérard Décrouez (PDF, 212 Кб)

18 сентября 2014 года

True Concurrency — from C.A. Petri to Telecom and Systems Biology

Stefan Haar, ENS Cachan (Париж)

Время: 16:40 - 18:00

Some circles, squares and arrows, plus some black dots moving along: that is all it takes to build a Petri net. These nets are a mathematical tool and model for dynamical systems generally considered to be “at home” in computer science. However, a great deal of the theory of Petri nets and of the concurrency (describing asynchronous parallel processes) which they involve, had been developed for and inspired by the understanding of physical processes, building upon principles from chemical reactions, and both relativistic and quantum physics.

It is fair to say that Petri nets are not only intuitive, but also fertile for many fields; in this talk, I will illustrate this in the contexts of physics, engineering, and biology, reflecting in some sort the evolution that the field has taken over the past 50 years.

Афиша доклада S. Haar (PDF, 1.21 Мб)

11 сентября 2014 года

Алгоритмическая теория информации и случайность индивидуальных объектов

Александр Шень, Институт проблем передачи информации им. А.А. Харкевича РАН / LIF (Марсель)

Время: 16:40 - 18:00

В середине XX века Шеннон ввёл понятие энтропии, которое можно интуитивно описать как «среднее количестве битов информации в одном значении случайной величины». Но его нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.

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

Я попытаюсь рассказать основные определения и какие-то из базовых результатов, а также (в зависимости от пожеланий аудитории) что-то про более современные работы.

Афиша доклада А. Шеня (PDF, 1.58 Мб)