Коллоквиум в 2016/2017 году
19 мая 2017
16.40 - 18.10Дмитрий Крюков, Northeastern University
Navigable networks as Nash equilibria of navigation games
Common sense suggests that networks are not random mazes of purposeless connections, but that these connections are organized so that networks can perform their functions well.
One function common to many networks is targeted transport or navigation. Here, using game theory, we show that minimalistic networks designed to maximize the navigation efficiency at minimal cost share basic structural properties with real networks. These idealistic networks are Nash equilibria of a network construction game whose purpose is to find an optimal trade-off between the network cost and navigability. We show that these skeletons are present in the Internet, metabolic, English word, US airport, Hungarian road networks, and in a structural network of the human brain. The knowledge of these skeletons allows one to identify the minimal number of edges, by altering which one can efficiently improve or paralyze navigation in the network, and to show that the spatiostructural organization of the human brain is nearly as needed for optimal routing of information between different parts of the brain.
Афиша коллоквиума
25 апреля 2017
18.10 - 19.30 Максим Жуковский, МФТИ
Логика случайного графа: от законов нуля или единицы до приложений
С 1960 года, после выхода основоположной статьи Эрдеша и Реньи, огромное количество работ было посвящено изучению свойств случайного графа. Значительная часть этих работ посвящена свойствам графов, описываемым на языке первого порядка и монадическом языке второго порядка. К таким свойствам можно отнести, например, свойство содержать треугольник, свойство содержать изолированную вершину и свойство связности.
В 2001 году свет увидела книга Дж. Спенсера "Strange logic of random graphs", содержащая обзор известных к тому моменту результатов о вероятностях свойств первого порядка случайного графа. Классический результат в этой области носит название закона нуля или единицы, который утверждает, что вероятность любого свойства первого порядка стремится либо к нулю, либо к единице. Разумеется, с 2001 года наука не стояла на месте — были получены новые результаты, касающиеся не только свойств первого порядка, но и монадических свойств. Более того, эти результаты нашли свое применение в задачах оценивания описательной сложности графовых свойств, решение которых, в свою очередь, позволяет находить новые алгоритмы проверки этих свойств.
11 апреля 2017
18.10 - 19.30Bruce Watson, Stellenbosch University
Correctness-by-Construction for Inventing Algorithms
For the most part, inventing a new algorithm is equal parts deep insight, experience, luck, and creativity. In this talk, I will introduce a more systematic approach to inventive algorithmics — an approach which also provides a correctness argument. Correctness-by-construction (CbC) is an algorithm derivation technique in which the algorithm is co-developed with its correctness proof. Starting with a pre- and post-condition specification, ‘derivation steps’ are made, eventually arriving at the final algorithm. Critically, each step in the derivation is a correctness-preserving one, meaning that the composition of the derivation steps is the correctness proof. While CbC can be used for already-invented algorithms, it can be used for taxonomization and also for identifying openings for new algorithms. This will be demonstrated on string, tree and FCA algorithms.
Афиша коллоквиума
14 марта 2017
18.10 - 19.30
Ivo Düntsch, Brock University, St Catharines, ON, Canada
Rough sets: A tool for qualitative knowledge discovery
Rough set theory (RST) was introduced in the early 1980s by Z. Pawlak (1982) and has become a well researched tool for knowledge discovery. The basic assumption of RST is that information is presented and perceived up to a certain granularity: "The information about a decision is usually vague because of uncertainty and imprecision coming from many sources [. . . ] Vagueness may be caused by granularity of representation of the information. Granularity may introduce an ambiguity to explanation or prescription based on vague information" (Pawlak and Słowin ́ski, 1993). In contrast to other machine learning or statistical methods, the original rough set approach uses only the information presented by the data itself and does not rely on outside distributional or other parameters. RST relies only on the principle of indifference and the nominal scale assumption. It has been applied in many fields, most recently in the investigation of complex adaptive systems, interactive granular computing, and big data analysis (Skowron et al., 2016). In my talk I will present the basic concepts of RST as well as non–parametric methods for feature reduction, data filtering, significance testing and model selection.
Афиша коллоквиума
21 февраля 2017
18.10 - 19.30
Peter Horvath, Hungarian Academy of Sciences, Biology Research Institute, and Finnish Institute for Molecular Medicine
Life beyond the pixels: Drug discovery using machine learning and image analysis methods
In this talk I will give an overview of the computational steps in the analysis of a single cell-based large-scale microscopy experiments. First, I will present a novel microscopic image correction method designed to eliminate vignetting and uneven background effects which, left uncorrected, corrupt intensity-based measurements. New single-cell image segmentation methods will be presented using energy minimization methods. I will discuss the Advanced Cell Classifier (ACC) (www.cellclassifier.org), a machine learning software tool capable of identifying cellular phenotypes based on features extracted from the image. It provides an interface for a user to efficiently train machine learning methods to predict various phenotypes. For cases where discrete cell-based decisions are not suitable, we propose a method to use multi-parametric regression to analyze continuous biological phenomena. Finally, to improve the learning speed and accuracy, we recently developed an active learning scheme which selects the most informative cell samples.
References:
Molnar, J., Molnar, Cs., Horvath, P. (2016)
An object splitting model using higher-order active contours for single-cell segmentation.
ISVC 16
Horvath, P., Aulner, N., Bickle, M., Davies, A., Del Nery, E., Ebner, D., Montoya, M., Ostling, P., Pietiainen, V., Price, L., Shorte, S., Turcatti, G., von Schantz, C., Carragher, N. (2016)
Screening out irrelevant cell-based models of disease
Nature Reviews Drug Discovery
Molnar, Cs., Jermyn, I., Kato, Z., Rahkama, V., Ostling, P., Mikkonen, P., Pietiainen, V., Horvath, P. (2016)
Accurate Morphology Preserving Segmentation of Overlapping Cells based on Active Contours
Scientific Reports - Nature
Molnar, J., Szucs, IA., Molnar, Cs., Horvath, P. (2016)
Active contours for selective object segmentation
IEEE WACV 16
Piccinini, F., Kiss, A., Horvath, P. (2015)
CellTracker (not only) for dummies.
Bioinformatics (Oxford)
Smith K., Li Y., Piccinini F., Csucs G., Balazs C., Bevilacqua A., Horvath, P. (2015)
CIDRE: an illumination-correction method for optical microscopy.
Nature Methods
Banerjee, I., Miyake, Y., Nobs, S. P., Schneider, C., Horvath, P., Kopf, M., Matthias, P., Helenius, A., Yamauchi, Y. (2014)
Influenza A virus uses the aggresome processing machinery for host cell entry.
Science
Афиша коллоквиума
14 февраля 2017
18.10 - 19.30
Ольга Реброва, РНИМУ им. Н.И. Пирогова/Общество специалистов доказательной медицины, НИУ ВШЭ
Доказательная и персонализированная медицина: каков потенциальный вклад data mining?
Медицина – весьма сложная, консервативная и все еще слабо формализованная область человеческой деятельности. В последние десятилетия возникли концепции доказательной и персонализированной медицины, связанные в том числе и с развитием различных разделов информатики. В докладе будут рассмотрены эти зачастую понимаемые как противоположные концепции, обсуждены потенциальная роль и место data mining в прогрессе медицины, а также основные проблемы применения математических методов в медицинских задачах и препятствия на пути «внедрения» полученных решений.
Афиша коллоквиума (PDF, 206 Кб)
22 декабря 2016
18.10 - 19.30
Михаил Захарьящев, НИУ ВШЭ / Birkbeck, University of London
Станислав Кикоть, ИППИ РАН / Birkbeck, University of London
Семантические технологии: новая жизнь для математической логики
Общая цель лекции - показать, как развитие семантических технологий приводит к новым интересным задачам в математической логике и построению новых логических систем. В частности, мы расскажем о дескрипционных логиках, их связи с модальными логиками и языком семантической паутины OWL. Мы обсудим онтологический доступ к данным, основанный на редукции пар (онтология, конъюнктивный запрос) к первопорядковым запросам, возникающие в этой связи логические и сложностные проблемы, и продемонстрируем работу системы Онтоп. Наконец, мы коснемся онтологического доступа к временным (в частности, потоковым) данным и соответствующих фрагментов различных временных логик.
Афиша коллоквиума (PDF, 331 Кб)
13 декабря 2016
18.10 - 19.30
Алексей Осадчий, НИУ ВШЭ
Математические методы анализа МЭГ-измерений межсудорожной активности мозга: от очагов к сетям и обратно
Современная технология магнитоэнцефалографии (МЭГ) позволяет неинвазивно исследовать электрическую активность головного мозга с высоким временным разрешением. Пространственное разрешение МЭГ фундаментально ограничено принципами электромагнетизма, однако использование арсенала математических методов решения обратной задачи позволяет, посредством введения априорных знаний о структуре нейрональной активности, достичь субсантиметрового пространственного разрешения. Наиболее распространённое медицинское применение МЭГ относится к решению задачи пространственной локализации эпилептогенных зон.
В этом докладе я расскажу о методах анализа МЭГ-измерений межсудорожной активности головного мозга с целью локализации первичного эпилептогенного очага, поиска каузальных взаимосвязей в межсудорожных сетях, а также о разрабатываемых нами подходах к повышению пространственного разрешения МЭГ-технологии на основе новых знаний о волновой динамике активности популяций нервных клеток.
Афиша коллоквиума (PDF, 287 Кб)
6 декабря 2016
18.10 - 19.30
Дмитрий Ульянов, Сколтех
Перенос стиля, дудлы и синтез текстур
Год назад были предложены новые алгоритмы для переноса стиля и синтеза текстур на основе нейросетей, а после был разработан метод так называемых нейросетевых дудлов. Все эти идеи работали так хорошо, что быстро нашли свое применение в некоторых программах по обработке изображений. Все же для обработки фото, например, на телефоне методы были неприменимы, так как требовали значительных ресурсов.
В нашей недавней работе мы представили идею ускорения предыдущих методов в 500 раз, которая в дальнейшем была использована в нескольких известных приложениях для стилизации изображений. В этом докладе я расскажу как про быстрый, так и про медленный алгоритмы стилизации, генерации текстур и дудлов.
Афиша коллоквиума (PDF, 323 Кб)
22 ноября 2016
18.10 - 19.30
Артем Бабенко, Яндекс
Эффективные алгоритмы нахождения ближайших соседей среди миллиардов векторов в пространствах высокой размерности
Определение ближайших соседей является подзадачей многих алгоритмов анализа данных, компьютерного зрения и других прикладных областей. Самый очевидный и наивный метод поиска ближайших соседей – полный перебор. Но при больших объемах поисковой базы полный перебор становится несостоятельным из-за своей вычислительной сложности, и необходимо использовать более быстрые приближенные алгоритмы. Одним из самых распространенных подходов является построение инвертированного индекса, который делит поисковое пространство на непересекающиеся регионы и осуществляет поиск только в небольшом количестве регионов, являющихся наиболее перспективными для конкретного запроса.
В докладе будут описаны две структуры данных, обобщающие идею стандартного инвертированного индекса, позволяющие осуществлять поиск ближайших соседей в базах, содержащих миллиарды векторов, за несколько миллисекунд. Практическая применимость предложенных методов подтверждена экспериментально на нескольких поисковых базах из задач компьютерного зрения.
Афиша коллоквиума (PDF, 314 Кб)
25 октября 2016
18.10 - 19.30
Дмитрий Шабанов, ФКН ВШЭ/МФТИ
Раскраски гиперграфов и смежные проблемы: вероятностно-алгоритмический подход
Ряд известных задач комбинаторики и теоретической информатики (например, задача k-SAT, задача об оценках чисел Рамсея и др.) могут быть сформулированы в абстрактных терминах раскрасок однородных гиперграфов. В докладе будут представлены классические комбинаторные постановки подобных задач и будет рассказано о последних достижениях в их решении. Мы обсудим вероятностные алгоритмы, с помощью которых были получены новые результаты, а также вопрос их практической реализации.
Афиша коллоквиума (PDF, 202 Кб)
11 октября 2016
18.10 - 19.30
Александр Новиков, ФКН ВШЭ/ИВМ РАН
Разложение в тензорный поезд в задачах машинного обучения
Разложение в тензорный поезд (Tensor Train, ТТ) — это обобщение SVD-разложения на тензоры (многомерные массивы). Этот подход позволяет компактно представить тензор в виде произведения факторов и совершать над ним операции посредством работы с факторами, не материализуя исходный тензор в процессе. Например, можно найти ТТ-представление поэлементного произведения двух тензоров размера 2100, заданных в виде ТТ-представления.
В докладе я расскажу как ТТ-разложение может быть использовано для представления параметров моделей машинного обучения на примере полиномиальных моделей и нейронных сетей. Такая параметризация позволяет обучать модели у которых экспоненциально много "виртуальных" параметров, работая при этом на практике с относительно небольшими факторами ТТ-формата.
Афиша коллоквиума (PDF, 208 Кб)
20 сентября 2016
18.10 - 19.30
Лев Беклемишев, МИАН / НИУ ВШЭ
Строго позитивные фрагменты модальных и дескрипционных логик
В докладе будут рассматриваться слабые фрагменты модальной логики, называемые строго позитивными. Формулы строго позитивного модального языка представляют собой импликации вида A → B, где A и B построены из переменных и константы T (истина) с использованием лишь & и экзистенциальных модальностей (типа «ромб»). Интерес к таким фрагментам возник около 2010 года независимо в двух различных областях: в дескрипционной логике и в области приложений модальной логики в теории доказательств. С точки зрения дескрипционной логики строго позитивные фрагменты соответствуют профилю OWL 2 EL известного языка онтологий OWL, в котором различные свойства онтологий распознаваемы за полиномиальное время. В области теоретико-доказательственных приложений такие фрагменты называются «исчисления рефлексий» и представляют собой удобное средство исследования независимых утверждений, так называемых схем рефлексии в формальной арифметике, и вычисления характеристических ординалов формальных теорий. Таким образом, в обеих областях строго позитивные языки и логики соединяют простоту и эффективность с достаточными выразительными возможностями. В докладе мы расскажем о проблемах общего характера, связанных со строго позитивными логиками, и опишем некоторые их приложения.
Афиша коллоквиума (PDF, 270 Кб)
6 сентября 2016
16.40 - 18.00
Christoph Lampert, IST Austria
Towards Lifelong Machine Learning
The goal of lifelong machine learning is to develop techniques that continuously and autonomously learn from data, potentially for years or decades. During this time, the system should autonomously improve its performance by extracting and preserving information between different learning tasks, similar to how a natural system learns more and more complex tasks over time. In my talk, I will highlight recent work from our research group in two directions: theoretical guarantees for lifelong learning and applications to computer vision problems.
Афиша коллоквиума
Владимир Гурвич, НИУ ВШЭ / Rutgers
18.10 - 19.30
Равновесие Нэша в чистых стратегиях
В 1912 г. Цермело доказал наличие решения (седловой точки) в чистых стратегиях для конечных позиционных игр с полной информацией, например, для шахмат. Затем Кёниг и Кальмар усилили этот результат, доказав существование стационарных (ход зависит только от текущей позиции, но не от предыстории) и равномерно оптимальных (не зависящих от начальной позиции) седловых стратегий. В 1950 г. Нэш предложил свою концепцию равновесия. Равновесие Нэша обобщает классическое понятие седловой точки на случай игр многих лиц, а также игр двух лиц с ненулевой суммой. Сразу же возник вопрос о возможности замены седловой точки равновесием Нэша в теоремах Цермело, Кёнига и Кальмара. Мы изучим условия существования равновесий Нэша в чистых (стационарных) стратегиях в конечных играх многих лиц: позиционных, стохастических, а также играх в нормальной форме, и покажем, что результаты Цермело обобщаются на случай игр с ненулевой суммой двух игроков, но не на случай трёх и более игроков.
Афиша коллоквиума