OpenRaiser/Intern-Atlas huggingface dataset:
Temporal Weights
Venue: arXiv cs.NE 2022
Year: 2022

In artificial neural networks, weights are a static representation of synapses. However, synapses are not static, they have their own interacting dynamics over time. To instill weights with interacting dynamics, we use a model describing synchronization that is capable of capturing core mechanisms of a range of neural and general biological phenomena over time. An ideal fit for these Temporal Weights (TW) are Neural ODEs, with continuous dynamics and a dependency on time. The resulting recurrent neural networks efficiently model temporal dynamics by computing on the ordering of sequences, and the length and scale of time. By adding temporal weights to a model, we demonstrate better performance, smaller models, and data efficiency on sparse, irregularly sampled time series datasets.
A Survey on Human Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Human Action Recognition (HAR), one of the most important tasks in computer vision, has developed rapidly in the past decade and has a wide range of applications in health monitoring, intelligent surveillance, virtual reality, human computer interaction and so on. Human actions can be represented by a wide variety of modalities, such as RGB-D cameras, audio, inertial sensors,etc. Consequently, in addition to the mainstream single modality based HAR approaches, more and more research is devoted to the multimodal domain due to the complementary properties between multimodal data. In this paper, we present a survey of HAR methods in recent years according to the different input modalities. Meanwhile, considering that most of the recent surveys on HAR focus on the third perspective, while this survey aims to provide a more comprehensive introduction to HAR novices and researchers, we therefore also investigate the actions recognition methods from the first perspective in recent years. Finally, we give a brief introduction about the benchmark HAR datasets and show the performance comparison of different methods on these datasets.
Image Embedding for Denoising Generative Models
Venue: arXiv cs.CV 2022
Year: 2022

Denoising Diffusion models are gaining increasing popularity in the field of generative modeling for several reasons, including the simple and stable training, the excellent generative quality, and the solid probabilistic foundation. In this article, we address the problem of {\em embedding} an image into the latent space of Denoising Diffusion Models, that is finding a suitable ``noisy'' image whose denoising results in the original image. We particularly focus on Denoising Diffusion Implicit Models due to the deterministic nature of their reverse diffusion process. As a side result of our investigation, we gain a deeper insight into the structure of the latent space of diffusion models, opening interesting perspectives on its exploration, the definition of semantic trajectories, and the manipulation/conditioning of encodings for editing purposes. A particularly interesting property highlighted by our research, which is also characteristic of this class of generative models, is the independence of the latent representation from the networks implementing the reverse diffusion process. In other words, a common seed passed to different networks (each trained on the same dataset), eventually results in identical images.
Exploring the Versal AI engines for accelerating stencil-based atmospheric advection simulation
Venue: arXiv cs.DC 2022
Year: 2022

AMD Xilinx's new Versal Adaptive Compute Acceleration Platform (ACAP) is an FPGA architecture combining reconfigurable fabric with other on-chip hardened compute resources. AI engines are one of these and, by operating in a highly vectorized manner, they provide significant raw compute that is potentially beneficial for a range of workloads including HPC simulation. However, this technology is still early-on, and as yet unproven for accelerating HPC codes, with a lack of benchmarking and best practice. This paper presents an experience report, exploring porting of the Piacsek and Williams (PW) advection scheme onto the Versal ACAP, using the chip's AI engines to accelerate the compute. A stencil-based algorithm, advection is commonplace in atmospheric modelling, including several Met Office codes who initially developed this scheme. Using this algorithm as a vehicle, we explore optimal approaches for structuring AI engine compute kernels and how best to interface the AI engines with programmable logic. Evaluating performance using a VCK5000 against non-AI engine FPGA configurations on the VCK5000 and Alveo U280, as well as a 24-core Xeon Platinum Cascade Lake CPU and Nvidia V100 GPU, we found that whilst the number of channels between the fabric and AI engines are a limitation, by leveraging the ACAP we can double performance compared to an Alveo U280.
Hypernets -- Good (G)news for Gnutella
Venue: arXiv cs.PF 2022
Year: 2022

Criticism of Gnutella network scalability has rested on the bandwidth attributes of the original interconnection topology: a Cayley tree. Trees, in general, are known to have lower aggregate bandwidth than higher dimensional topologies e.g., hypercubes, meshes and tori. Gnutella was intended to support thousands to millions of peers. Studies of interconnection topologies in the literature, however, have focused on hardware implementations which are limited by cost to a few thousand nodes. Since the Gnutella network is virtual, hyper-topologies are relatively unfettered by such constraints. We present performance models for several plausible hyper-topologies and compare their query throughput up to millions of peers. The virtual hypercube and the virtual hypertorus are shown to offer near linear scalability subject to the number of peer TCP/IP connections that can be simultaneously kept open.
Proof of Church's Thesis
Venue: arXiv cs.LO 2023
Year: 2023

We prove that if our calculating capability is that of a universal Turing machine with a finite tape, then Church's thesis is true. This way we accomplish Post (1936) program.
An Empirical Comparison of Three Inference Methods
Venue: arXiv cs.AI 2023
Year: 2023

In this paper, an empirical evaluation of three inference methods for uncertain reasoning is presented in the context of Pathfinder, a large expert system for the diagnosis of lymph-node pathology. The inference procedures evaluated are (1) Bayes' theorem, assuming evidence is conditionally independent given each hypothesis; (2) odds-likelihood updating, assuming evidence is conditionally independent given each hypothesis and given the negation of each hypothesis; and (3) a inference method related to the Dempster-Shafer theory of belief. Both expert-rating and decision-theoretic metrics are used to compare the diagnostic accuracy of the inference methods.
Internal Pattern Matching Queries in a Text and Applications
Venue: arXiv cs.DS 2023
Year: 2023

We consider several types of internal queries, that is, questions about fragments of a given text $T$ specified in constant space by their locations in $T$. Our main result is an optimal data structure for Internal Pattern Matching (IPM) queries which, given two fragments $x$ and $y$, ask for a representation of all fragments contained in $y$ and matching $x$ exactly; this problem can be viewed as an internal version of the Exact Pattern Matching problem. Our data structure answers IPM queries in time proportional to the quotient $|y|/|x|$ of fragments' lengths, which is required due to the information content of the output. If $T$ is a text of length $n$ over an integer alphabet of size $σ$, then our data structure occupies $O(n/ \log_σn)$ machine words (that is, $O(n\log σ)$ bits) and admits an $O(n/ \log_σn)$-time construction algorithm. We show the applicability of IPM queries for answering internal queries corresponding to other classic string processing problems. Among others, we derive optimal data structures reporting the periods of a fragment and testing the cyclic equivalence of two fragments. IPM queries have already found numerous further applications, following the path paved by the classic Longest Common Extension (LCE) queries of Landau and Vishkin (JCSS, 1988). In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the PILLAR model, developed by Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). On the way to our main result, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka (STOC 2019). Our method, based on a new restricted version of the recompression technique of Jeż (J. ACM, 2016), yields a hierarchy of $O(\log n)$ string synchronizing sets covering the whole spectrum of fragments' lengths.
Semantics for a Logic of Presuppositions
Venue: arXiv cs.LO 2023
Year: 2023

In 1952 P. F. Strawson proposed a logic of presuppositions. It is an interpretation of Aristotelian logic, i.e. of the logic of the traditional syllogism. In 1981 Richard Diaz published a monograph in which he presented truth-relevant logic. This paper shows that truth-relevant logic is but a propositional version of the logic of presuppositions. A semantics of the logic of presuppositions is developed using truth-relevant logic. The semantics is then further extended to polyadic logic and some consequences discussed.
The ERA of FOLE: Superstructure
Venue: arXiv cs.LO 2023
Year: 2023

This paper discusses the representation of ontologies in the first-order logical environment {\ttfamily FOLE}. An ontology defines the primitives with which to model the knowledge resources for a community of discourse. These primitives consist of classes, relationships and properties. An ontology uses formal axioms to constrain the interpretation of these primitives. In short, an ontology specifies a logical theory. This paper continues the discussion of the representation and interpretation of ontologies in the first-order logical environment {\ttfamily FOLE}. The formalism and semantics of (many-sorted) first-order logic can be developed in both a \emph{classification form} and an \emph{interpretation form}. Two papers, ``The {\ttfamily ERA} of {\ttfamily FOLE}: Foundation'', defining the concept of a structure, and the current paper, defining the concept of a sound logic, represent the \emph{classification form}, corresponding to ideas discussed in the ``Information Flow Framework''. Two papers, ``The {\ttfamily FOLE} Table'', defining the concept of a relational table, and ``The {\ttfamily FOLE} Database'', defining the concept of a relational database, represent the \emph{interpretation form}, expanding on material found in the paper ``Database Semantics''. Although the classification form follows the entity-relationship-attribute data model of Chen, the interpretation form incorporates the relational data model of Codd. A fifth paper ``{\ttfamily FOLE} Equivalence'' proves that the classification form is equivalent to the interpretation form. In general, the {\ttfamily FOLE} representation uses a conceptual structures approach, that is completely compatible with the theory of institutions, formal concept analysis and information flow.
Tractable Lineages on Treelike Instances: Limits and Extensions
Venue: arXiv cs.DB 2023
Year: 2023

Query evaluation on probabilistic databases is generally intractable (#P-hard). Existing dichotomy results have identified which queries are tractable (or safe), and connected them to tractable lineages. In our previous work, using different tools, we showed that query evaluation is linear-time on probabilistic databases for arbitrary monadic second-order queries, if we bound the treewidth of the instance. In this paper, we study limitations and extensions of this result. First, for probabilistic query evaluation, we show that MSO tractability cannot extend beyond bounded treewidth: there are even FO queries that are hard on any efficiently constructible unbounded-treewidth class of graphs. This dichotomy relies on recent polynomial bounds on the extraction of planar graphs as minors, and implies lower bounds in non-probabilistic settings, for query evaluation and match counting in subinstance-closed families. Second, we show how to explain our tractability result in terms of lineage: the lineage of MSO queries on bounded-treewidth instances can be represented as bounded-treewidth circuits, polynomial-size OBDDs, and linear-size d-DNNFs. By contrast, we can strengthen the previous dichotomy to lineages, and show that there are even UCQs with disequalities that have superpolynomial OBDDs on all unbounded-treewidth graph classes; we give a characterization of such queries. Last, we show how bounded-treewidth tractability explains the tractability of the inversion-free safe queries: we can rewrite their input instances to have bounded-treewidth.
CoPaSul Manual -- Contour-based parametric and superpositional intonation stylization
Venue: arXiv cs.CL 2023
Year: 2023

The purposes of the CoPaSul toolkit are (1) automatic prosodic annotation and (2) prosodic feature extraction from syllable to utterance level. CoPaSul stands for contour-based, parametric, superpositional intonation stylization. In this framework intonation is represented as a superposition of global and local contours that are described parametrically in terms of polynomial coefficients. On the global level (usually associated but not necessarily restricted to intonation phrases) the stylization serves to represent register in terms of time-varying F0 level and range. On the local level (e.g. accent groups), local contour shapes are described. From this parameterization several features related to prosodic boundaries and prominence can be derived. Furthermore, by coefficient clustering prosodic contour classes can be obtained in a bottom-up way. Next to the stylization-based feature extraction also standard F0 and energy measures (e.g. mean and variance) as well as rhythmic aspects can be calculated. At the current state automatic annotation comprises: segmentation into interpausal chunks, syllable nucleus extraction, and unsupervised localization of prosodic phrase boundaries and prominent syllables. F0 and partly also energy feature sets can be derived for: standard measurements (as median and IQR), register in terms of F0 level and range, prosodic boundaries, local contour shapes, bottom-up derived contour classes, Gestalt of accent groups in terms of their deviation from higher level prosodic units, as well as for rhythmic aspects quantifying the relation between F0 and energy contours and prosodic event rates.
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
Venue: arXiv cs.LG 2023
Year: 2023

We propose a novel technique for analyzing adaptive sampling called the {\em Simulator}. Our approach differs from the existing methods by considering not how much information could be gathered by any fixed sampling strategy, but how difficult it is to distinguish a good sampling strategy from a bad one given the limited amount of data collected up to any given time. This change of perspective allows us to match the strength of both Fano and change-of-measure techniques, without succumbing to the limitations of either method. For concreteness, we apply our techniques to a structured multi-arm bandit problem in the fixed-confidence pure exploration setting, where we show that the constraints on the means imply a substantial gap between the moderate-confidence sample complexity, and the asymptotic sample complexity as $δ\to 0$ found in the literature. We also prove the first instance-based lower bounds for the top-k problem which incorporate the appropriate log-factors. Moreover, our lower bounds zero-in on the number of times each \emph{individual} arm needs to be pulled, uncovering new phenomena which are drowned out in the aggregate sample complexity. Our new analysis inspires a simple and near-optimal algorithm for the best-arm and top-k identification, the first {\em practical} algorithm of its kind for the latter problem which removes extraneous log factors, and outperforms the state-of-the-art in experiments.
Compression with wildcards: All k-models of a binary decision diagram
Venue: arXiv cs.DS 2023
Year: 2023

Given a Binary Decision Diagram $B$ of a Boolean function $φ$ in $n$ variables, it is well known that all $φ$-models can be enumerated in output polynomial time, and in a compressed way (using don't-care symbols). We show that all $N$ many $φ$-models of fixed Hamming-weight $k$ can be enumerated as well in time polynomial in $n$ and $|B|$ and $N$. Furthermore, using novel wildcards, again enables a compressed enumeration of these models.
Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms
Venue: arXiv cs.LG 2023
Year: 2023

We study multi-item profit maximization when there is an underlying distribution over buyers' values. In practice, a full description of the distribution is typically unavailable, so we study the setting where the mechanism designer only has samples from the distribution. If the designer uses the samples to optimize over a complex mechanism class -- such as the set of all multi-item, multi-buyer mechanisms -- a mechanism may have high average profit over the samples but low expected profit. This raises the central question of this paper: how many samples are sufficient to ensure that a mechanism's average profit is close to its expected profit? To answer this question, we uncover structure shared by many pricing, auction, and lottery mechanisms: for any set of buyers' values, profit is piecewise linear in the mechanism's parameters. Using this structure, we prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature and match or improve over the best-known guarantees for many classes.
Continuous Average Straightness in Spatial Graphs
Venue: arXiv cs.DM 2023
Year: 2023

The Straightness is a measure designed to characterize a pair of vertices in a spatial graph. It is defined as the ratio of the Euclidean distance to the graph distance between these vertices. It is often used as an average, for instance to describe the accessibility of a single vertex relatively to all the other vertices in the graph, or even to summarize the graph as a whole. In some cases, one needs to process the Straightness between not only vertices, but also any other points constituting the graph of interest. Suppose for instance that our graph represents a road network and we do not want to limit ourselves to crossroad-to-crossroad itineraries, but allow any street number to be a starting point or destination. In this situation, the standard approach consists in: 1) discretizing the graph edges, 2) processing the vertex-to-vertex Straightness considering the additional vertices resulting from this discretization, and 3) performing the appropriate average on the obtained values. However, this discrete approximation can be computationally expensive on large graphs, and its precision has not been clearly assessed. In this article, we adopt a continuous approach to average the Straightness over the edges of spatial graphs. This allows us to derive 5 distinct measures able to characterize precisely the accessibility of the whole graph, as well as individual vertices and edges. Our method is generic and could be applied to other measures designed for spatial graphs. We perform an experimental evaluation of our continuous average Straightness measures, and show how they behave differently from the traditional vertex-to-vertex ones. Moreover, we also study their discrete approximations, and show that our approach is globally less demanding in terms of both processing time and memory usage. Our R source code is publicly available under an open source license.
Video Captioning with Guidance of Multimodal Latent Topics
Venue: arXiv cs.CV 2023
Year: 2023

The topic diversity of open-domain videos leads to various vocabularies and linguistic expressions in describing video contents, and therefore, makes the video captioning task even more challenging. In this paper, we propose an unified caption framework, M&M TGM, which mines multimodal topics in unsupervised fashion from data and guides the caption decoder with these topics. Compared to pre-defined topics, the mined multimodal topics are more semantically and visually coherent and can reflect the topic distribution of videos better. We formulate the topic-aware caption generation as a multi-task learning problem, in which we add a parallel task, topic prediction, in addition to the caption task. For the topic prediction task, we use the mined topics as the teacher to train a student topic prediction model, which learns to predict the latent topics from multimodal contents of videos. The topic prediction provides intermediate supervision to the learning process. As for the caption task, we propose a novel topic-aware decoder to generate more accurate and detailed video descriptions with the guidance from latent topics. The entire learning procedure is end-to-end and it optimizes both tasks simultaneously. The results from extensive experiments conducted on the MSR-VTT and Youtube2Text datasets demonstrate the effectiveness of our proposed model. M&M TGM not only outperforms prior state-of-the-art methods on multiple evaluation metrics and on both benchmark datasets, but also achieves better generalization ability.
DeepTransport: Learning Spatial-Temporal Dependency for Traffic Condition Forecasting
Venue: arXiv cs.AI 2023
Year: 2023

Predicting traffic conditions has been recently explored as a way to relieve traffic congestion. Several pioneering approaches have been proposed based on traffic observations of the target location as well as its adjacent regions, but they obtain somewhat limited accuracy due to a lack of mining road topology. To address the effect attenuation problem, we suggest taking into account the traffic of surrounding locations(wider than the adjacent range). We propose an end-to-end framework called DeepTransport, in which Convolutional Neural Networks (CNN) and Recurrent Neural Networks (RNN) are utilized to obtain spatial-temporal traffic information within a transport network topology. In addition, an attention mechanism is introduced to align spatial and temporal information. Moreover, we constructed and released a real-world large traffic condition dataset with a 5-minute resolution. Our experiments on this dataset demonstrate our method captures the complex relationship in the temporal and spatial domains. It significantly outperforms traditional statistical methods and a state-of-the-art deep learning method.
The Limits of Citation Counts
Venue: arXiv cs.DL 2023
Year: 2023

I study the measurement of scientists' influence using bibliographic data. The main result is an axiomatic characterization of the family of citation-counting indices, a broad class of influence measures which includes the renowned h-index. The result highlights several limitations of these indices: they are not suitable to compare scientists across different fields, and they cannot account for indirect influence. I explore how these limitations can be overcome by using richer bibliographic information.