OpenRaiser/Intern-Atlas huggingface dataset:
Conditional Bisimilarity for Reactive Systems
Venue: arXiv cs.LO 2022
Year: 2022

Reactive systems à la Leifer and Milner, an abstract categorical framework for rewriting, provide a suitable framework for deriving bisimulation congruences. This is done by synthesizing interactions with the environment in order to obtain a compositional semantics. We enrich the notion of reactive systems by conditions on two levels: first, as in earlier work, we consider rules enriched with application conditions and second, we investigate the notion of conditional bisimilarity. Conditional bisimilarity allows us to say that two system states are bisimilar provided that the environment satisfies a given condition. We present several equivalent definitions of conditional bisimilarity, including one that is useful for concrete proofs and that employs an up-to-context technique, and we compare with related behavioural equivalences. We consider examples based on DPO graph rewriting, an instantiation of reactive systems.
A Simple Language Model for Task-Oriented Dialogue
Venue: arXiv cs.CL 2022
Year: 2022

Task-oriented dialogue is often decomposed into three tasks: understanding user input, deciding actions, and generating a response. While such decomposition might suggest a dedicated model for each sub-task, we find a simple, unified approach leads to state-of-the-art performance on the MultiWOZ dataset. SimpleTOD is a simple approach to task-oriented dialogue that uses a single, causal language model trained on all sub-tasks recast as a single sequence prediction problem. This allows SimpleTOD to fully leverage transfer learning from pre-trained, open domain, causal language models such as GPT-2. SimpleTOD improves over the prior state-of-the-art in joint goal accuracy for dialogue state tracking, and our analysis reveals robustness to noisy annotations in this setting. SimpleTOD also improves the main metrics used to evaluate action decisions and response generation in an end-to-end setting: inform rate by 8.1 points, success rate by 9.7 points, and combined score by 7.2 points.
Explaining How Deep Neural Networks Forget by Deep Visualization
Venue: arXiv cs.LG 2022
Year: 2022

Explaining the behaviors of deep neural networks, usually considered as black boxes, is critical especially when they are now being adopted over diverse aspects of human life. Taking the advantages of interpretable machine learning (interpretable ML), this paper proposes a novel tool called Catastrophic Forgetting Dissector (or CFD) to explain catastrophic forgetting in continual learning settings. We also introduce a new method called Critical Freezing based on the observations of our tool. Experiments on ResNet articulate how catastrophic forgetting happens, particularly showing which components of this famous network are forgetting. Our new continual learning algorithm defeats various recent techniques by a significant margin, proving the capability of the investigation. Critical freezing not only attacks catastrophic forgetting but also exposes explainability.
Demand-Side Scheduling Based on Multi-Agent Deep Actor-Critic Learning for Smart Grids
Venue: arXiv cs.LG 2022
Year: 2022

We consider the problem of demand-side energy management, where each household is equipped with a smart meter that is able to schedule home appliances online. The goal is to minimize the overall cost under a real-time pricing scheme. While previous works have introduced centralized approaches in which the scheduling algorithm has full observability, we propose the formulation of a smart grid environment as a Markov game. Each household is a decentralized agent with partial observability, which allows scalability and privacy-preservation in a realistic setting. The grid operator produces a price signal that varies with the energy demand. We propose an extension to a multi-agent, deep actor-critic algorithm to address partial observability and the perceived non-stationarity of the environment from the agent's viewpoint. This algorithm learns a centralized critic that coordinates training of decentralized agents. Our approach thus uses centralized learning but decentralized execution. Simulation results show that our online deep reinforcement learning method can reduce both the peak-to-average ratio of total energy consumed and the cost of electricity for all households based purely on instantaneous observations and a price signal.
LandCover.ai: Dataset for Automatic Mapping of Buildings, Woodlands, Water and Roads from Aerial Imagery
Venue: arXiv cs.CV 2022
Year: 2022

Monitoring of land cover and land use is crucial in natural resources management. Automatic visual mapping can carry enormous economic value for agriculture, forestry, or public administration. Satellite or aerial images combined with computer vision and deep learning enable precise assessment and can significantly speed up change detection. Aerial imagery usually provides images with much higher pixel resolution than satellite data allowing more detailed mapping. However, there is still a lack of aerial datasets made for the segmentation, covering rural areas with a resolution of tens centimeters per pixel, manual fine labels, and highly publicly important environmental instances like buildings, woods, water, or roads. Here we introduce LandCover.ai (Land Cover from Aerial Imagery) dataset for semantic segmentation. We collected images of 216.27 sq. km rural areas across Poland, a country in Central Europe, 39.51 sq. km with resolution 50 cm per pixel and 176.76 sq. km with resolution 25 cm per pixel and manually fine annotated four following classes of objects: buildings, woodlands, water, and roads. Additionally, we report simple benchmark results, achieving 85.56% of mean intersection over union on the test set. It proves that the automatic mapping of land cover is possible with a relatively small, cost-efficient, RGB-only dataset. The dataset is publicly available at https://landcover.ai.linuxpolska.com/
XEM: An Explainable-by-Design Ensemble Method for Multivariate Time Series Classification
Venue: arXiv cs.LG 2022
Year: 2022

We present XEM, an eXplainable-by-design Ensemble method for Multivariate time series classification. XEM relies on a new hybrid ensemble method that combines an explicit boosting-bagging approach to handle the bias-variance trade-off faced by machine learning models and an implicit divide-and-conquer approach to individualize classifier errors on different parts of the training data. Our evaluation shows that XEM outperforms the state-of-the-art MTS classifiers on the public UEA datasets. Furthermore, XEM provides faithful explainability-by-design and manifests robust performance when faced with challenges arising from continuous data collection (different MTS length, missing data and noise).
Learning Stable Models for Prediction and Control
Venue: arXiv cs.RO 2022
Year: 2022

This paper demonstrates the benefits of imposing stability on data-driven Koopman operators. The data-driven identification of stable Koopman operators (DISKO) is implemented using an algorithm \cite{mamakoukas_stableLDS2020} that computes the nearest \textit{stable} matrix solution to a least-squares reconstruction error. As a first result, we derive a formula that describes the prediction error of Koopman representations for an arbitrary number of time steps, and which shows that stability constraints can improve the predictive accuracy over long horizons. As a second result, we determine formal conditions on basis functions of Koopman operators needed to satisfy the stability properties of an underlying nonlinear system. As a third result, we derive formal conditions for constructing Lyapunov functions for nonlinear systems out of stable data-driven Koopman operators, which we use to verify stabilizing control from data. Lastly, we demonstrate the benefits of DISKO in prediction and control with simulations using a pendulum and a quadrotor and experiments with a pusher-slider system. The paper is complemented with a video: \url{https://sites.google.com/view/learning-stable-koopman}.
Symplectic Neural Networks in Taylor Series Form for Hamiltonian Systems
Venue: arXiv cs.LG 2022
Year: 2022

We propose an effective and lightweight learning algorithm, Symplectic Taylor Neural Networks (Taylor-nets), to conduct continuous, long-term predictions of a complex Hamiltonian dynamic system based on sparse, short-term observations. At the heart of our algorithm is a novel neural network architecture consisting of two sub-networks. Both are embedded with terms in the form of Taylor series expansion designed with symmetric structure. The key mechanism underpinning our infrastructure is the strong expressiveness and special symmetric property of the Taylor series expansion, which naturally accommodate the numerical fitting process of the gradients of the Hamiltonian with respect to the generalized coordinates as well as preserve its symplectic structure. We further incorporate a fourth-order symplectic integrator in conjunction with neural ODEs' framework into our Taylor-net architecture to learn the continuous-time evolution of the target systems while simultaneously preserving their symplectic structures. We demonstrated the efficacy of our Taylor-net in predicting a broad spectrum of Hamiltonian dynamic systems, including the pendulum, the Lotka--Volterra, the Kepler, and the Hénon--Heiles systems. Our model exhibits unique computational merits by outperforming previous methods to a great extent regarding the prediction accuracy, the convergence rate, and the robustness despite using extremely small training data with a short training period (6000 times shorter than the predicting period), small sample sizes, and no intermediate data to train the networks.
Increased-confidence adversarial examples for deep learning counter-forensics
Venue: arXiv cs.CV 2022
Year: 2022

Transferability of adversarial examples is a key issue to apply this kind of attacks against multimedia forensics (MMF) techniques based on Deep Learning (DL) in a real-life setting. Adversarial example transferability, in fact, would open the way to the deployment of successful counter forensics attacks also in cases where the attacker does not have a full knowledge of the to-be-attacked system. Some preliminary works have shown that adversarial examples against CNN-based image forensics detectors are in general non-transferrable, at least when the basic versions of the attacks implemented in the most popular libraries are adopted. In this paper, we introduce a general strategy to increase the strength of the attacks and evaluate their transferability when such a strength varies. We experimentally show that, in this way, attack transferability can be largely increased, at the expense of a larger distortion. Our research confirms the security threats posed by the existence of adversarial examples even in multimedia forensics scenarios, thus calling for new defense strategies to improve the security of DL-based MMF techniques.
Edit Distance in Near-Linear Time: it's a Constant Factor
Venue: arXiv cs.DS 2022
Year: 2022

We present an algorithm for approximating the edit distance between two strings of length $n$ in time $n^{1+\varepsilon}$ up to a constant factor, for any $\varepsilon>0$. Our result completes a research direction set forth in the recent breakthrough paper [Chakraborty-Das-Goldenberg-Koucky-Saks, FOCS'18], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results of [Koucky-Saks, STOC'20] and [Brakensiek-Rubinstein, STOC'20] have shown near-linear time algorithms that obtain an additive approximation, near-linear in $n$ (equivalently, constant-factor approximation when the edit distance value is close to $n$). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input strings. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings, of length $n^{i\varepsilon}$ for $i=0,1,\ldots,1/\varepsilon$. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance.
Intracranial Hemorrhage Detection Using Neural Network Based Methods With Federated Learning
Venue: arXiv cs.CV 2022
Year: 2022

Intracranial hemorrhage, bleeding that occurs inside the cranium, is a serious health problem requiring rapid and often intensive medical treatment. Such a condition is traditionally diagnosed by highly-trained specialists analyzing computed tomography (CT) scan of the patient and identifying the location and type of hemorrhage if one exists. We propose a neural network approach to find and classify the condition based upon the CT scan. The model architecture implements a time distributed convolutional network. We observed accuracy above 92% from such an architecture, provided enough data. We propose further extensions to our approach involving the deployment of federated learning. This would be helpful in pooling learned parameters without violating the inherent privacy of the data involved.
ExSample: Efficient Searches on Video Repositories through Adaptive Sampling
Venue: arXiv cs.DB 2022
Year: 2022

Capturing and processing video is increasingly common as cameras become cheaper to deploy. At the same time, rich video understanding methods have progressed greatly in the last decade. As a result, many organizations now have massive repositories of video data, with applications in mapping, navigation, autonomous driving, and other areas. Because state-of-the-art object detection methods are slow and expensive, our ability to process even simple ad-hoc object search queries ('find 100 traffic lights in dashcam video') over this accumulated data lags far behind our ability to collect it. Processing video at reduced sampling rates is a reasonable default strategy for these types of queries, however, the ideal sampling rate is both data and query dependent. We introduce ExSample, a low cost framework for object search over unindexed video that quickly processes search queries by adapting the amount and location of sampled frames to the particular data and query being processed. ExSample prioritizes the processing of frames in a video repository so that processing is focused in portions of video that most likely contain objects of interest. It continually re-prioritizes processing based on feedback from previously processed frames. On large, real-world datasets, ExSample reduces processing time by up to 6x over an efficient random sampling baseline and by several orders of magnitude over state-of-the-art methods that train specialized per-query surrogate models. ExSample is thus a key component in building cost-efficient video data management systems.
Interacting with Explanations through Critiquing
Venue: arXiv cs.CL 2022
Year: 2022

Using personalized explanations to support recommendations has been shown to increase trust and perceived quality. However, to actually obtain better recommendations, there needs to be a means for users to modify the recommendation criteria by interacting with the explanation. We present a novel technique using aspect markers that learns to generate personalized explanations of recommendations from review texts, and we show that human users significantly prefer these explanations over those produced by state-of-the-art techniques. Our work's most important innovation is that it allows users to react to a recommendation by critiquing the textual explanation: removing (symmetrically adding) certain aspects they dislike or that are no longer relevant (symmetrically that are of interest). The system updates its user model and the resulting recommendations according to the critique. This is based on a novel unsupervised critiquing method for single- and multi-step critiquing with textual explanations. Experiments on two real-world datasets show that our system is the first to achieve good performance in adapting to the preferences expressed in multi-step critiquing.
Instability, Computational Efficiency and Statistical Accuracy
Venue: arXiv cs.LG 2022
Year: 2022

Many statistical estimators are defined as the fixed point of a data-dependent operator, with estimators based on minimizing a cost function being an important special case. The limiting performance of such estimators depends on the properties of the population-level operator in the idealized limit of infinitely many samples. We develop a general framework that yields bounds on statistical accuracy based on the interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (in)stability when applied to an empirical object based on $n$ samples. Using this framework, we analyze both stable forms of gradient descent and some higher-order and unstable algorithms, including Newton's method and its cubic-regularized variant, as well as the EM algorithm. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models. We exhibit cases in which an unstable algorithm can achieve the same statistical accuracy as a stable algorithm in exponentially fewer steps -- namely, with the number of iterations being reduced from polynomial to logarithmic in sample size $n$.
Two-Hop Connectivity to the Roadside in a VANET Under the Random Connection Model
Venue: arXiv cs.NI 2022
Year: 2022

In this paper, we compute the expected number of vehicles with at least one two-hop path to a fixed roadside unit (RSU) in a multi-hop, one-dimensional vehicular ad hoc network (VANET) where other cars can act as relays. The pairwise channels experience Rayleigh fading in the random connection model, and so exist, with a probability given by a function of the mutual distance between the cars, or between the cars and the RSU. We derive exact expressions for the expected number of cars with a two-hop connection to the RSU when the car density $ρ$ tends to zero and infinity, and determine its behaviour using an infinite oscillating power series in $ρ$, which is accurate for all regimes of traffic density. We also corroborate those findings with a realistic scenario, using snapshots of actual traffic data. Finally, a normal approximation is discussed for the probability mass function of the number of cars with a two-hop connection to the RSU.
A Fast Algorithm for Online k-servers Problem on Trees
Venue: arXiv cs.DS 2022
Year: 2022

We consider online algorithms for the $k$-server problem on trees. There is a $k$-competitive algorithm for this problem, and it is the best competitive ratio. M. Chrobak and L. Larmore provided it. At the same time, the existing implementation has $O(n)$ time complexity for processing a query and $O(n)$ for prepossessing, where $n$ is the number of nodes in a tree. Another implementation of the algorithm has $O(k^2+k\log n)$ time complexity for processing a query and $O(n\log n)$ for prepossessing. We provide a new time-efficient implementation of the algorithm. It has $O(n)$ time complexity for preprocessing and $O\left(k(\log n)^2\right)$ for processing a query.
Improving Disentangled Text Representation Learning with Information-Theoretic Guidance
Venue: arXiv cs.LG 2022
Year: 2022

Learning disentangled representations of natural language is essential for many NLP tasks, e.g., conditional text generation, style transfer, personalized dialogue systems, etc. Similar problems have been studied extensively for other forms of data, such as images and videos. However, the discrete nature of natural language makes the disentangling of textual representations more challenging (e.g., the manipulation over the data space cannot be easily achieved). Inspired by information theory, we propose a novel method that effectively manifests disentangled representations of text, without any supervision on semantics. A new mutual information upper bound is derived and leveraged to measure dependence between style and content. By minimizing this upper bound, the proposed method induces style and content embeddings into two independent low-dimensional spaces. Experiments on both conditional text generation and text-style transfer demonstrate the high quality of our disentangled representation in terms of content and style preservation.
Discovering Parametric Activation Functions
Venue: arXiv cs.LG 2022
Year: 2022

Recent studies have shown that the choice of activation function can significantly affect the performance of deep learning networks. However, the benefits of novel activation functions have been inconsistent and task dependent, and therefore the rectified linear unit (ReLU) is still the most commonly used. This paper proposes a technique for customizing activation functions automatically, resulting in reliable improvements in performance. Evolutionary search is used to discover the general form of the function, and gradient descent to optimize its parameters for different parts of the network and over the learning process. Experiments with four different neural network architectures on the CIFAR-10 and CIFAR-100 image classification datasets show that this approach is effective. It discovers both general activation functions and specialized functions for different architectures, consistently improving accuracy over ReLU and other activation functions by significant margins. The approach can therefore be used as an automated optimization step in applying deep learning to new tasks.
Efficient Semi-External Depth-First Search
Venue: arXiv cs.DB 2022
Year: 2022

As the sizes of graphs grow rapidly, currently many real-world graphs can hardly be loaded in the main memory. It becomes a hot topic to compute depth-first search (DFS) results, i.e., depth-first order or DFS-Tree, on semi-external memory model. Semi-external algorithms assume the main memory could at least hold a spanning tree T of a graph G, and gradually restructure T into a DFS-Tree, which is non-trivial. In this paper, we present a comprehensive study of semi-external DFS problem. Based on our theoretical analysis of its main challenge, we introduce a new semi-external DFS algorithm, named EP-DFS, with a lightweight index N+-index. Unlike traditional algorithms, we focus on addressing such complex problem efficiently not only with less I/Os, but also with simpler CPU calculation (implementation-friendly) and less random I/O accesses (key-to-efficiency). Extensive experimental evaluation is conducted on both synthetic and real graphs. The experimental results confirm that our EP-DFS algorithm significantly outperforms existing algorithms.
Compositional modelling of network games
Venue: arXiv cs.GT 2022
Year: 2022

The analysis of games played on graph-like structures is of increasing importance due to the prevalence of social networks, both virtual and physical, in our daily life. As well as being relevant in computer science, mathematical analysis and computer simulations of such distributed games are vital methodologies in economics, politics and epidemiology, amongst other fields. Our contribution is to give compositional semantics of a family of such games as a well-behaved mapping, a strict monoidal functor, from a category of open graphs (syntax) to a category of open games (semantics). As well as introducing the theoretical framework, we identify some applications of compositionality.