Thu, 25 Nov 2021
11:30
C3

Relating Structure to Power

Samson Abramsky
(University College London)
Further Information

This is an in-person seminar.

Abstract

In this talk, we describe some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics.

The motivations for this work come from Computer Science, but there may be something of interest for model theorists and other logicians.

The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings.

One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way:

- the Ehrenfeucht-Fraisse game

- the quantifier rank fragments of first-order logic

- the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction to the existential-positive part, and (iii) the extension with counting quantifiers

- the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez).

Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth.

Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters.

This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers.

Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages.

Examples include semantic characterisation and preservation theorems, Lovasz-type results on  isomorphisms, and classification of constraint satisfaction problems.

Tue, 27 Oct 2020

14:00 - 15:00
Virtual

Atomic subgraphs and the statistical mechanics of networks

Anatol Wegner
(University College London)
Abstract

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows the for the generation of graphs with extensive numbers of triangles and other network motifs commonly observed in many real world networks. More specifically we focus on maximum entropy ensembles under constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such models. We also present a procedure for combining distributions of multiple atomic subgraphs that enables the construction of models with fewer parameters. Expanding the model to include atoms with edge and vertex labels we obtain a general class of models that can be parametrized in terms of basic building blocks and their distributions that includes many widely used models as special cases. These models include random graphs with arbitrary distributions of subgraphs, random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy for all these models can be derived from a single expression that is characterized by the symmetry groups of atomic subgraphs.

Thu, 12 Nov 2020

16:00 - 17:00
Virtual

The fluid mechanics of suspensions

Helen Wilson
(University College London)
Further Information
Abstract

Materials made from a mixture of liquid and solid are, instinctively, very obviously complex. From dilatancy (the reason wet sand becomes dry when you step on it) to extreme shear-thinning (quicksand) or shear-thickening (cornflour oobleck) there is a wide range of behaviours to explain and predict. I'll discuss the seemingly simple case of solid spheres suspended in a Newtonian fluid matrix, which still has plenty of surprises up its sleeve.

Tue, 28 Apr 2020

12:00 - 13:00
C1

Atomic structures and the statistical mechanics of networks

Anatol Wegner
(University College London)
Abstract

We consider random graph models where graphs are generated by connecting not only pairs of nodes by edges but also larger subsets of
nodes by copies of small atomic subgraphs of arbitrary topology. More specifically we consider canonical and microcanonical ensembles
corresponding to constraints placed on the counts and distributions of atomic subgraphs and derive general expressions for the entropy of such
models. We also introduce a procedure that enables the distributions of multiple atomic subgraphs to be combined resulting in more coarse
grained models. As a result we obtain a general class of models that can be parametrized in terms of basic building blocks and their
distributions that includes many widely used models as special cases. These models include random graphs with arbitrary distributions of subgraphs (Karrer & Newman PRE 2010, Bollobas et al. RSA 2011), random hypergraphs, bipartite models, stochastic block models, models of multilayer networks and their degree corrected and directed versions. We show that the entropy expressions for all these models can be derived from a single expression that is characterized by the symmetry groups of their atomic subgraphs.

Tue, 21 Jan 2020

12:00 - 13:00
C1

Generative models and representational learning on street networks

Mateo Neira
(University College London)
Abstract

Cities are now central to addressing global changes, ranging from climate change to economic resilience. There is a growing concern of how to measure and quantify urban phenomena, and one of the biggest challenges in quantifying different aspects of cities and creating meaningful indicators lie in our ability to extract relevant features that characterize the topological and spatial patterns of urban form. Many different models that can reproduce large-scale statistical properties observed in systems of streets have been proposed, from spatial random graphs to economical models of network growth. However, existing models fail to capture the diversity observed in street networks around the world. The increased availability of street network datasets and advancements in deep learning models present a new opportunity to create more accurate and flexible models of urban street networks, as well as capture important characteristics that could be used in downstream tasks.  We propose a simple approach called Convolutional-PCA (ConvPCA) for both creating low-dimensional representations of street networks that can be used for street network classification and other downstream tasks, as well as a generating new street networks that preserve visual and statistical similarity to observed street networks.

Link to the preprint

Tue, 05 Feb 2019

12:00 - 13:00
C4

Nonparametric inference of atomic network structures

Anatol Wegner
(University College London)
Abstract

Many real-world networks contain small recurring connectivity patterns also known as network motifs. Although network motifs are widely considered to be important structural features of networks that are closely connected to their function methods for characterizing and modelling the local connectivity structure of complex networks remain underdeveloped. In this talk, we will present a non-parametric approach that is based on generative models in which networks are generated by adding not only single edges but also but also copies of larger subgraphs such as triangles to the graph. We show that such models can be formulated in terms of latent states that correspond to subgraph decompositions of the network and derive analytic expressions for the likelihood of such models. Following a Bayesian approach, we present a nonparametric prior for model parameters. Solving the resulting inference problem results in a principled approach for identifying atomic connectivity patterns of networks that do not only identify statistically significant connectivity patterns but also produces a decomposition of the network into such atomic substructures. We tested the presented approach on simulated data for which the algorithm recovers the latent state to a high degree of accuracy. In the case of empirical networks, the method identifies concise sets atomic subgraphs from within thousands of candidates that are plausible and include known atomic substructures.

Thu, 17 Jan 2019

16:00 - 17:30
L3

Light scattering by atmospheric ice crystals - a hybrid numerical-asymptotic approach

Dr. David Hewett
(University College London)
Abstract

Accurate simulation of electromagnetic scattering by ice crystals in clouds is an important problem in atmospheric physics, with single scattering results feeding directly into the radiative transfer models used to predict long-term climate behaviour. The problem is challenging for numerical simulation methods because the ice crystals in a given cloud can be extremely varied in size and shape, sometimes exhibiting fractal-like geometrical characteristics and sometimes being many hundreds or thousands of wavelengths in diameter. In this talk I will focus on the latter "high-frequency" issue, describing a hybrid numerical-asymptotic boundary element method for the simplified problem of acoustic scattering by penetrable convex polygons, where high frequency asymptotic information is used to build a numerical approximation space capable of achieving fixed accuracy of approximation with frequency-independent computational cost. 

Fri, 09 Nov 2018

12:00 - 12:30
L4

Detection of Transient Data using the Signature Features

Hao Ni
(University College London)
Abstract

In this talk, we consider the supervised learning problem where the explanatory variable is a data stream. We provide an approach based on identifying carefully chosen features of the stream which allows linear regression to be used to characterise the functional relationship between explanatory variables and the conditional distribution of the response; the methods used to develop and justify this approach, such as the signature of a stream and the shuffle product of tensors, are standard tools in the theory of rough paths and provide a unified and non-parametric approach with potential significant dimension reduction. We apply it to the example of detecting transient datasets and demonstrate the superior effectiveness of this method benchmarked with supervised learning methods with raw data.

Thu, 18 Oct 2018

12:00 - 13:00
L4

On the Existence of Solutions to the Two-Fluids Systems

Ewelina Zatorska
(University College London)
Abstract

In this talk I will present the recent developments in the topic of existence of solutions to the two-fluid systems. I will discuss the application of approach developed by P.-L. Lions and E. Feireisl and explain the limitations of this technique in the context of multi-component flow models. A particular example of such a model is two-fluids Stokes system with single velocity field and two densities, and with an algebraic pressure law closure. The existence result that uses the compactness criterion introduced for the Navier-Stokes system by D. Bresch and P.-E. Jabin will be presented. I will also mention an innovative construction of solutions relying on the G. Crippa and C. DeLellis stability estimates for the transport equation.

Mon, 23 Oct 2017

15:45 - 16:45
L3

The signature approach for the supervised learning problem with sequential data input and its application

Hao Ni
(University College London)
Abstract

In the talk, we discuss how to combine the recurrent neural network with the signature feature set to tackle the supervised learning problem where the input is a data stream. We will apply this method to different datasets, including the synthetic datasets( learning the solution to SDEs ) and empirical datasets(action recognition) and demonstrate the effectiveness of this method.

 

Subscribe to University College London