Search

The unprecedented pace of machine learning research has lead to incredible advances, but also poses hard challenges. At present, the field lacks strong theoretical underpinnings, and many important achievements stem from ad hoc design choices which are hard to justify in principle and whose effectiveness often goes unexplained. Research debt is increasing and many papers are found not to be reproducible. This thesis is a survey that covers some recent work attempting to study machine learning categorically. Category theory is a branch of abstract mathematics that has found successful applications in many fields, both inside and outside mathematics. Acting as a lingua franca of mathematics and science, category theory might be able to give a unifying structure to the field of machine learning. This could solve some of the aforementioned problems. In this work, we mainly focus on the application of category theory to deep learning. Namely, we discuss the use of categorical optics to model gradient-based learning, the use of categorical algebras and integral transforms to link classical computer science to neural networks, the use of functors to link different layers of abstraction and preserve structure, and, finally, the use of string diagrams to provide detailed representations of neural network architectures., Comment: In the previous version of the survey, it was stated that the paper "Pooling Image Datasets with Multiple Covariate Shift and Imbalance" (Chytas, Lokhande, Singh) had been withdrawn by the authors. I have been informed that only an incomplete draft of the work was withdrawn after it was inadvertently uploaded. The complete work was actually published at ICLR and has never been withdrawn

This position paper on the (meta-)theory of Structural Operational Semantic (SOS) is motivated by the following two questions: (1) Is the (meta-)theory of SOS dying out as a research field? (2) If so, is it possible to rejuvenate this field with a redefined purpose? In this article, we will consider possible answers to those questions by first analysing the history of the EXPRESS/SOS workshops and the data concerning the authors and the presentations featured in the editions of those workshops as well as their subject matters. The results of our quantitative and qualitative analyses all indicate a diminishing interest in the theory of SOS as a field of research. Even though `all good things must come to an end', we strive to finish this position paper on an upbeat note by addressing our second motivating question with some optimism. To this end, we use our personal reflections and an analysis of recent trends in two of the flagship conferences in the field of Programming Languages (namely POPL and PDLI) to draw some conclusions on possible future directions that may rejuvenate research on the (meta-)theory of SOS. We hope that our musings will entice members of the research community to breathe new life into a field of research that has been kind to three of the authors of this article., Comment: In Proceedings EXPRESS/SOS2023, arXiv:2309.05788

We review the fuzzy approach to poverty measurement by comparing poverty indices using different membership functions proposed in the literature. We put our main focus on the issue of estimation of the mean squared errors of these fuzzy methods showing which indices can be more accurately estimated using sample data. By means of simulations, we also investigate the role of parameters of the membership function when it comes to estimating mean squared errors via a robustness analysis., Comment: 25 pages, 9 tables, 9 figures

We study distributed knowledge, which is what privately informed agents come to know by communicating freely with one another and sharing everything they know. Agents are not necessarily fully rational and differ in the ability to form higher-order knowledge. We model the inference making process that leads to distributed knowledge, and we do that by introducing revision operators and revision types. Since reasoning abilities can be heterogeneous, inference making turns out to be order dependent. We show that there are two qualitatively different cases of how distributed knowledge is attained. In the first, distributed knowledge is determined by any group member who can replicate all the inferences that anyone else in the group makes. This result is in line with the extant literature. In the second case, no member can replicate all the inferences that are made within the group. As a result, distributed knowledge is determined by any two group members who can jointly replicate what anyone else infers. This case can be interpreted as a form of wisdom of crowd effect and shows that, contrary to what is generally believed, distributed knowledge cannot always be reduced to the reasoning abilities of a single group member.

A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with increasing edge time labels. We consider the problem of assigning time labels to the edges of a digraph in order to maximize the total reachability of the resulting temporal graph (that is, the number of pairs of nodes which are connected one to the other). In particular, we prove that this problem is NP-hard. We then conjecture that the problem is approximable within a constant approximation ratio. This conjecture is a consequence of the following graph theoretic conjecture: any strongly connected directed graph with n nodes admits an out-arborescence and an in-arborescence that are edge-disjoint, have the same root, and each spans $\Omega$(n) nodes.

We provide a syntactic construction of correlated equilibrium. For any finite game, we study how players coordinate their play on a signal by means of a public strategy whose instructions are expressed in some natural language. Language can be ambiguous in that different players may assign different truth values to the very same formula in the same state of the world. We model ambiguity using the player-dependent logic of Halpern and Kets (2015). We show that, absent any ambiguity, self-enforcing coordination always induces a correlated equilibrium of the underlying game. When language ambiguity is allowed, self-enforcing coordination strategies induce subjective correlated equilibria.

A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erd\H{o}s-R\'enyi random graph model. The proposed model is obtained by randomly permuting the edges of an Erd\H{o}s-R\'enyi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erd\H{o}s-R\'enyi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at $p = \log n/n$ the size of the largest temporally connected component increases from $o(n)$ to~$n-o(n)$. This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.

Graphene, consisting of an inert, thermally stable material with an atomically flat, dangling bond-free surface is by essence an ideal template layer for van der Waals heteroepitaxy of two-dimensional materials such as silicene. However, depending on the synthesis method and growth parameters, graphene (Gr) substrates could exhibit, on a single sample, various surface structures, thicknesses, defects, and step heights. These structures noticeably affect the growth mode of epitaxial layers, e.g. turning the layer-by-layer growth into the Volmer-Weber growth promoted by defect-assisted nucleation. In this work, the growth of silicon on chemical vapor deposited epitaxial Gr (1 ML Gr/1ML Gr buffer) on 6H-SiC(0001) substrate is investigated by a combination of atomic force microscopy (AFM), scanning tunneling microscopy (STM), x-ray photoelectron spectroscopy (XPS), scanning electron microscopy (SEM) and Raman spectroscopy measurements. It is shown that the perfect control of full-scale almost defect-free 1 ML Gr with a single surface structure and the ultra-clean conditions for molecular beam epitaxy (MBE) deposition of silicon represent key prerequisites for ensuring the growth of extended silicene sheets on epitaxial graphene.

We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that it is carried out exclusively through the spiking of neurons. Even though much has been accomplished in the blocks world over the past five decades, we believe that this is the first algorithm of its kind. The input is a sequence of symbols encoding an initial set of block stacks as well as a target set, and the output is a sequence of motion commands such as "put the top block in stack 1 on the table". The program is written in the Assembly Calculus, a recently proposed computational framework meant to model computation in the brain by bridging the gap between neural activity and cognitive function. Its elementary objects are assemblies of neurons (stable sets of neurons whose simultaneous firing signifies that the subject is thinking of an object, concept, word, etc.), its commands include project and merge, and its execution model is based on widely accepted tenets of neuroscience. A program in this framework essentially sets up a dynamical system of neurons and synapses that eventually, with high probability, accomplishes the task. The purpose of this work is to establish empirically that reasonably large programs in the Assembly Calculus can execute correctly and reliably; and that rather realistic -- if idealized -- higher cognitive functions, such as planning in the blocks world, can be implemented successfully by such programs.

We consider the problem of assigning appearing times to the edges of a digraph in order to maximize the (average) temporal reachability between pairs of nodes. Motivated by the application to public transit networks, where edges cannot be scheduled independently one of another, we consider the setting where the edges are grouped into certain walks (called trips) in the digraph and where assigning the appearing time to the first edge of a trip forces the appearing times of the subsequent edges. In this setting, we show that, quite surprisingly, it is NP-complete to decide whether there exists an assignment of times connecting a given pair of nodes. This result allows us to prove that the problem of maximising the temporal reachability cannot be approximated within a factor better than some polynomial term in the size of the graph. We thus focus on the case where, for each pair of nodes, there exists an assignment of times such that one node is reachable from the other. We call this property strong temporalisability. It is a very natural assumption for the application to public transit networks. On the negative side, the problem of maximising the temporal reachability remains hard to approximate within a factor $\sqrt$ n/12 in that setting. Moreover, we show the existence of collections of trips that are strongly temporalisable but for which any assignment of starting times to the trips connects at most an O(1/ $\sqrt$ n) fraction of all pairs of nodes. On the positive side, we show that there must exist an assignment of times that connects a constant fraction of all pairs in the strongly temporalisable and symmetric case, that is, when the set of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. Keywords:edge labeling edge scheduled network network optimisation temporal graph temporal path temporal reachability time assignment

We study how a consensus emerges in a finite population of like-minded individuals who are asymmetrically informed about the realization of the true state of the world. Agents observe a private signal about the state and then start exchanging messages. Generalizing the classical model of rational dialogues of Geanakoplos and Polemarchakis (1982) and its subsequent extensions, we dispense with the standard assumption that the state space is a probability space and we do not put any bound on the cardinality of the state space itself or the information partitions. We show that a class of rational dialogues can be found that always lead to consensus provided that three main conditions are met. First, everybody must be able to send messages to everybody else, either directly or indirectly. Second, communication must be reciprocal. Finally, agents need to have the opportunity to engage in dialogues of transfinite length.

Consider a sub-population of rebels that wish to initiate a revolution. In order to avoid initializing a failed revolution, rebels would first strive to estimate their relative "power", which is often correlated with their fraction in the population. However, and especially in non-democratic countries, rebels refrain from disclosing themselves. This poses a significant challenge for rebels: estimating their fraction in the population while minimizing the risk of being identified as rebels. This paper introduces a distributed computing framework aiming to study this question. Our main takeaway message is that the communication pattern has a crucial role in achieving such a task. Specifically, we show that relying on the inherent noise in the communication, "public communication", characterized by the fact that each message announced by an individual can be viewed by all its neighbors, allows rebels to estimate their fraction in the population while keeping a negligible risk of each rebel being identified as such. The suggested estimation protocol, inspired by historical events, is extremely simple and can be executed covertly even under extreme conditions of surveillance. Conversely, we show that under peer-to-peer communication, protocols of similar simplicity are either inefficient or non-covert.

Despite the large literature focused on the growth of graphene (Gr) on 6H-SiC(0001) by chemical vapour deposition (CVD), some important issues have not been solved and full wafer scale epitaxy of Gr remains challenging, hampering applications in microelectronics. With this study we shed light on the generic mechanism which produces the coexistence of two different types of Gr domains, whose proportion can be carefully controlled by tuning the H2 flow rate. For the first time, we show that the growth of Gr using CVD under H2/Ar flow rate proceeds in two stages. Firstly, the nucleation of free-standing epitaxial graphene on hydrogen (H-Gr) occurs, then H-atoms eventually desorb from either step edges or defects. This gives rise, for H2 flow rate below a critical value, to the formation of (6x6)Gr domains on 6H-SiC(0001). The front of H-desorption progresses proportionally to the reduction of H2. Using a robust and generic X-ray photoelectron spectroscopy (XPS) analysis, we realistically quantify the proportions of H-Gr and (6x6)Gr domains of a Gr film synthetized in any experimental conditions. Scanning tunnelling microscopy supports the XPS measurements. From these results we can deduce that the H- assisted CVD growth of Gr developed here is a unique method to grow fully free-standing H-Gr on the contrary to the method consisting of H-intercalation below epitaxial Gr on buffer layer. These results are of crucial importance for future applications of Gr/SiC(0001) in nanoelectronics, providing the groundwork for the use of Gr as an optimal template layer for Van der Waals homo- and hetero-epitaxy.

Data integration is a long-standing interest of the data management community and has many disparate applications, including business, science and government. We have recently witnessed impressive results in specific data integration tasks, such as Entity Resolution, thanks to the increasing availability of benchmarks. A limitation of such benchmarks is that they typically come with their own task definition and it can be difficult to leverage them for complex integration pipelines. As a result, evaluating end-to-end pipelines for the entire data integration process is still an elusive goal. In this work, we present Alaska, the first benchmark based on real-world dataset to support seamlessly multiple tasks (and their variants) of the data integration pipeline. The dataset consists of ~70k heterogeneous product specifications from 71 e-commerce websites with thousands of different product attributes. Our benchmark comes with profiling meta-data, a set of pre-defined use cases with diverse characteristics, and an extensive manually curated ground truth. We demonstrate the flexibility of our benchmark by focusing on several variants of two crucial data integration tasks, Schema Matching and Entity Resolution. Our experiments show that our benchmark enables the evaluation of a variety of methods that previously were difficult to compare, and can foster the design of more holistic data integration solutions.

A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. In this paper we consider the single source Pareto problem in weighted point-availability time-dependent networks, which consists of computing, for any destination d, all Pareto optimal pairs (t, c), where t and c are the arrival time and the cost of a path from s to d, respectively (a pair (t, c) is Pareto optimal if there is no path with arrival time smaller than t and cost no worse than c or arrival time no greater than t and better cost). We design and analyse a general algorithm for solving this problem, whose time complexity is O(M log P), where M is the number of temporal edges and P is the maximum number of Pareto optimal pairs for each node of the network. This complexity significantly improves the time complexity of the previously known solution. Our algorithm can be used to solve several different minimum cost path problems in weighted point-availability time-dependent networks with a vast variety of cost definitions, and it can be easily modified in order to deal with the single destination Pareto problem. All our results apply to directed networks, but they can be easily adapted to undirected networks with no edges with zero travel time.