OpenRaiser/Intern-Atlas huggingface dataset:
Dirichlet Proportions Model for Hierarchically Coherent Probabilistic Forecasting
Venue: arXiv cs.LG 2023
Year: 2023

Probabilistic, hierarchically coherent forecasting is a key problem in many practical forecasting applications -- the goal is to obtain coherent probabilistic predictions for a large number of time series arranged in a pre-specified tree hierarchy. In this paper, we present an end-to-end deep probabilistic model for hierarchical forecasting that is motivated by a classical top-down strategy. It jointly learns the distribution of the root time series, and the (dirichlet) proportions according to which each parent time-series is split among its children at any point in time. The resulting forecasts are naturally coherent, and provide probabilistic predictions over all time series in the hierarchy. We experiment on several public datasets and demonstrate significant improvements of up to 26% on most datasets compared to state-of-the-art baselines. Finally, we also provide theoretical justification for the superiority of our top-down approach compared to the more traditional bottom-up modeling.
Curriculum Learning for Goal-Oriented Semantic Communications with a Common Language
Venue: arXiv cs.NI 2023
Year: 2023

Goal-oriented semantic communication will be a pillar of next-generation wireless networks. Despite significant recent efforts in this area, most prior works are focused on specific data types (e.g., image or audio), and they ignore the goal and effectiveness aspects of semantic transmissions. In contrast, in this paper, a holistic goal-oriented semantic communication framework is proposed to enable a speaker and a listener to cooperatively execute a set of sequential tasks in a dynamic environment. A common language based on a hierarchical belief set is proposed to enable semantic communications between speaker and listener. The speaker, acting as an observer of the environment, utilizes the beliefs to transmit an initial description of its observation (called event) to the listener. The listener is then able to infer on the transmitted description and complete it by adding related beliefs to the transmitted beliefs of the speaker. As such, the listener reconstructs the observed event based on the completed description, and it then takes appropriate action in the environment based on the reconstructed event. An optimization problem is defined to determine the perfect and abstract description of the events while minimizing the transmission and inference costs with constraints on the task execution time and belief efficiency. Then, a novel bottom-up curriculum learning (CL) framework based on reinforcement learning is proposed to solve the optimization problem and enable the speaker and listener to gradually identify the structure of the belief set and the perfect and abstract description of the events. Simulation results show that the proposed CL method outperforms traditional RL in terms of convergence time, task execution cost and time, reliability, and belief efficiency.
A Taxonomy of Human and ML Strengths in Decision-Making to Investigate Human-ML Complementarity
Venue: arXiv cs.HC 2023
Year: 2023

Hybrid human-ML systems increasingly make consequential decisions in a wide range of domains. These systems are often introduced with the expectation that the combined human-ML system will achieve complementary performance, that is, the combined decision-making system will be an improvement compared with either decision-making agent in isolation. However, empirical results have been mixed, and existing research rarely articulates the sources and mechanisms by which complementary performance is expected to arise. Our goal in this work is to provide conceptual tools to advance the way researchers reason and communicate about human-ML complementarity. Drawing upon prior literature in human psychology, machine learning, and human-computer interaction, we propose a taxonomy characterizing distinct ways in which human and ML-based decision-making can differ. In doing so, we conceptually map potential mechanisms by which combining human and ML decision-making may yield complementary performance, developing a language for the research community to reason about design of hybrid systems in any decision-making domain. To illustrate how our taxonomy can be used to investigate complementarity, we provide a mathematical aggregation framework to examine enabling conditions for complementarity. Through synthetic simulations, we demonstrate how this framework can be used to explore specific aspects of our taxonomy and shed light on the optimal mechanisms for combining human-ML judgments
Evaluating regular path queries under the all-shortest paths semantics
Venue: arXiv cs.DB 2023
Year: 2023

The purpose of this report is to explain how the textbook breadth-first search algorithm (BFS) can be modified in order to also create a compact representation of all shortest paths connecting a single source node to all the nodes reachable from it. From this representation, all these paths can also be efficiently enumerated. We then apply this algorithm to solve a similar problem in edge labelled graphs, where paths also have an additional restriction that their edge labels form a word belonging to a regular language. Namely, we solve the problem of evaluating regular path queries (RPQs) under the all-shortest paths semantics.
Conversational Question Answering on Heterogeneous Sources
Venue: arXiv cs.IR 2023
Year: 2023

Conversational question answering (ConvQA) tackles sequential information needs where contexts in follow-up questions are left implicit. Current ConvQA systems operate over homogeneous sources of information: either a knowledge base (KB), or a text corpus, or a collection of tables. This paper addresses the novel issue of jointly tapping into all of these together, this way boosting answer coverage and confidence. We present CONVINSE, an end-to-end pipeline for ConvQA over heterogeneous sources, operating in three stages: i) learning an explicit structured representation of an incoming question and its conversational context, ii) harnessing this frame-like representation to uniformly capture relevant evidences from KB, text, and tables, and iii) running a fusion-in-decoder model to generate the answer. We construct and release the first benchmark, ConvMix, for ConvQA over heterogeneous sources, comprising 3000 real-user conversations with 16000 questions, along with entity annotations, completed question utterances, and question paraphrases. Experiments demonstrate the viability and advantages of our method, compared to state-of-the-art baselines.
Computing Reachable Simulations
Venue: arXiv cs.LO 2023
Year: 2023

We study the problem of computing the reachable principals of simulation preorder and the reachable blocks of simulation equivalence. Following a theoretical investigation of the decidability and complexity aspects of this problem, which in particular highlights a stark contrast with the already settled case of bisimulation, we design algorithms to solve this problem by leveraging the idea of interleaving reachability and simulation computation while possibly avoiding the computation of all the reachable states or the whole simulation preorder. In particular, we put forward a symbolic algorithm processing state partitions and, in turn, relations between their blocks, which is suited for processing infinite state systems.
Circular cartograms via the elastic beam algorithm originated from cartographic generalization
Venue: arXiv cs.HC 2023
Year: 2023

The circular cartogram, also known as the Dorling map, is a widely used tool for visualizing statistical data. It represents regions as circles with their areas in proportion to the statistical values and requires circle displacement to avoid overlap and maintain spatial relationships. In this paper, we propose a new approach for circular cartogram production that utilizes the elastic beam displacement algorithm in cartographic generalization. First, the initial circles are generated with their areas in proportion to the statistical values. Second, an elastic beam structure is built as a proximity graph based on the spatial relations between the circles. Third, the circles violating the quality requirements are considered to have a force on the nodes of a beam. Fourth, the elastic beam algorithm is applied to assign forces for each node to determine the new positions of the circles. Steps two through four are repeated until a circular cartogram that meets the defined quality requirements is obtained. The experiments indicate that the proposed approach can successfully generate circular cartograms without overlaps while maintaining topology and relative relationships with higher quality than existing approaches.
A Biset-Enriched Categorical Model for Proto-Quipper with Dynamic Lifting
Venue: arXiv cs.PL 2023
Year: 2023

Quipper and Proto-Quipper are a family of quantum programming languages that, by their nature as circuit description languages, involve two runtimes: one at which the program generates a circuit and one at which the circuit is executed, normally with probabilistic results due to measurements. Accordingly, the language distinguishes two kinds of data: parameters, which are known at circuit generation time, and states, which are known at circuit execution time. Sometimes, it is desirable for the results of measurements to control the generation of the next part of the circuit. Therefore, the language needs to turn states, such as measurement outcomes, into parameters, an operation we call dynamic lifting. The goal of this paper is to model this interaction between the runtimes by providing a general categorical structure enriched in what we call "bisets". We demonstrate that the biset-enriched structure achieves a proper semantics of the two runtimes and their interaction, by showing that it models a variant of Proto-Quipper with dynamic lifting. The present paper deals with the concrete categorical semantics of this language, whereas a companion paper deals with the syntax, type system, operational semantics, and abstract categorical semantics.
Mat2Stencil: A Modular Matrix-Based DSL for Explicit and Implicit Matrix-Free PDE Solvers on Structured Grid
Venue: arXiv cs.DC 2023
Year: 2023

Partial differential equation (PDE) solvers are extensively utilized across numerous scientific and engineering fields. However, achieving high performance and scalability often necessitates intricate and low-level programming, particularly when leveraging deterministic sparsity patterns in structured grids. In this paper, we propose an innovative domain-specific language (DSL), Mat2Stencil, with its compiler, for PDE solvers on structured grids. Mat2Stencil introduces a structured sparse matrix abstraction, facilitating modular, flexible, and easy-to-use expression of solvers across a broad spectrum, encompassing components such as Jacobi or Gauss-Seidel preconditioners, incomplete LU or Cholesky decompositions, and multigrid methods built upon them. Our DSL compiler subsequently generates matrix-free code consisting of generalized stencils through multi-stage programming. The code allows spatial loop-carried dependence in the form of quasi-affine loops, in addition to the Jacobi-style stencil's embarrassingly parallel on spatial dimensions. We further propose a novel automatic parallelization technique for the spatially dependent loops, which offers a compile-time deterministic task partitioning for threading, calculates necessary inter-thread synchronization automatically, and generates an efficient multi-threaded implementation with fine-grained synchronization. Implementing 4 benchmarking programs, 3 of them being the pseudo-applications in NAS Parallel Benchmarks with $6.3\%$ lines of code and 1 being matrix-free High Performance Conjugate Gradients with $16.4\%$ lines of code, we achieve up to $1.67\times$ and on average $1.03\times$ performance compared to manual implementations.
Reducing Predictive Feature Suppression in Resource-Constrained Contrastive Image-Caption Retrieval
Venue: arXiv cs.CV 2023
Year: 2023

To train image-caption retrieval (ICR) methods, contrastive loss functions are a common choice for optimization functions. Unfortunately, contrastive ICR methods are vulnerable to predictive feature suppression. Predictive features are features that correctly indicate the similarity between a query and a candidate item. However, in the presence of multiple predictive features during training, encoder models tend to suppress redundant predictive features, since these features are not needed to learn to discriminate between positive and negative pairs. While some predictive features are redundant during training, these features might be relevant during evaluation. We introduce an approach to reduce predictive feature suppression for resource-constrained ICR methods: latent target decoding (LTD). We add an additional decoder to the contrastive ICR framework, to reconstruct the input caption in a latent space of a general-purpose sentence encoder, which prevents the image and caption encoder from suppressing predictive features. We implement the LTD objective as an optimization constraint, to ensure that the reconstruction loss is below a bound value while primarily optimizing for the contrastive loss. Importantly, LTD does not depend on additional training data or expensive (hard) negative mining strategies. Our experiments show that, unlike reconstructing the input caption in the input space, LTD reduces predictive feature suppression, measured by obtaining higher recall@k, r-precision, and nDCG scores than a contrastive ICR baseline. Moreover, we show that LTD should be implemented as an optimization constraint instead of a dual optimization objective. Finally, we show that LTD can be used with different contrastive learning losses and a wide variety of resource-constrained ICR methods.
From prediction markets to interpretable collective intelligence
Venue: arXiv cs.GT 2023
Year: 2023

We outline how to create a mechanism that provides an optimal way to elicit, from an arbitrary group of experts, the probability of the truth of an arbitrary logical proposition together with collective information that has an explicit form and interprets this probability. Namely, we provide strong arguments for the possibility of the development of a self-resolving prediction market with play money that incentivizes direct information exchange between experts. Such a system could, in particular, motivate simultaneously many experts to collectively solve scientific or medical problems in a very efficient manner. We also note that in our considerations, experts are not assumed to be Bayesian.
Bilinear value networks
Venue: arXiv cs.AI 2023
Year: 2023

The dominant framework for off-policy multi-goal reinforcement learning involves estimating goal conditioned Q-value function. When learning to achieve multiple goals, data efficiency is intimately connected with the generalization of the Q-function to new goals. The de-facto paradigm is to approximate Q(s, a, g) using monolithic neural networks. To improve the generalization of the Q-function, we propose a bilinear decomposition that represents the Q-value via a low-rank approximation in the form of a dot product between two vector fields. The first vector field, f(s, a), captures the environment's local dynamics at the state s; whereas the second component, ϕ(s, g), captures the global relationship between the current state and the goal. We show that our bilinear decomposition scheme substantially improves data efficiency, and has superior transfer to out-of-distribution goals compared to prior methods. Empirical evidence is provided on the simulated Fetch robot task-suite and dexterous manipulation with a Shadow hand.
Practical Considerations in Direct Detection Under Tukey Signalling
Venue: arXiv cs.IT 2023
Year: 2023

The deliberate introduction of controlled intersymbol interference (ISI) in Tukey signalling enables the recovery of signal amplitude and (in part) signal phase under direct detection, giving rise to significant data rate improvements compared to intensity modulation with direct detection (IMDD). The use of an integrate-and-dump detector makes precise waveform shaping unnecessary, thereby equipping the scheme with a high degree of robustness to nonlinear signal distortions introduced by practical modulators. Signal sequences drawn from star quadrature amplitude modulation (SQAM) formats admit an efficient trellis description that facilitates codebook design and low-complexity near maximum-likelihood sequence detection in the presence of both shot noise and thermal noise. Under the practical (though suboptimal) allocation of a 50% duty cycle between ISI-free and ISI-present signalling segments, at a symbol rate of 50 Gbaud and a launch power of -10 dBm the Tukey scheme has a maximum theoretically achievable throughput of 200 Gb/s with an (8,4)-SQAM constellation, while an IMDD scheme achieves about 145 Gb/s using PAM-8. Note that the two mentioned constellations have the same number of magnitude levels and the difference in throughput is resulting from exploiting phase information under using a complex-valued signal constellation.
Average Redundancy of Variable-Length Balancing Schemes à la Knuth
Venue: arXiv cs.IT 2023
Year: 2023

We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses $\frac12 \log n+O(1)$ redundant bits to encode messages into length-$n$ words with weight $(n/2)+{\sf q}$ for constant ${\sf q}$. We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits.
Towards Optimal Tradeoff Between Data Freshness and Update Cost in Information-update Systems
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the Age-of-Information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.
Enhancing Core Image Classification Using Generative Adversarial Networks (GANs)
Venue: arXiv cs.CV 2023
Year: 2023

In the thrilling world of oil exploration, drill core samples are key to unlocking geological information critical to finding lucrative oil deposits. Despite the importance of these samples, traditional core logging techniques are known to be laborious and, worse still, subjective. Thankfully, the industry has embraced an innovative solution core imaging that allows for nondestructive and noninvasive rapid characterization of large quantities of drill cores. Our preeminent research paper aims to tackle the pressing problem of core detection and classification. Using state-of-the-art techniques, we present a groundbreaking solution that will transform the industry. Our first challenge is detecting the cores and segmenting the holes in images, which we will achieve using the Faster RCNN and Mask RCNN models, respectively. Then, we will address the problem of filling the hole in the core image, utilizing the powerful Generative Adversarial Networks (GANs) and employing Contextual Residual Aggregation (CRA) to create high-frequency residuals for missing contents in images. Finally, we will apply sophisticated texture recognition models for the classification of core images, revealing crucial information to oil companies in their quest to uncover valuable oil deposits. Our research paper presents an innovative and groundbreaking approach to tackling the complex issues surrounding core detection and classification. By harnessing cutting-edge techniques and technologies, we are poised to revolutionize the industry and make significant contributions to the field of oil exploration.
Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods
Venue: arXiv cs.GT 2023
Year: 2023

We study the problem of fair and efficient allocation of a set of indivisible goods to agents with additive valuations using the popular fairness notions of envy-freeness up to one good (EF1) and equitability up to one good (EQ1) in conjunction with Pareto-optimality (PO). There exists a pseudo-polynomial time algorithm to compute an EF1+PO allocation and a non-constructive proof of the existence of allocations that are both EF1 and fractionally Pareto-optimal (fPO), which is a stronger notion than PO. We present a pseudo-polynomial time algorithm to compute an EF1+fPO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+fPO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time. We also consider the class of $k$-ary instances where $k$ is a constant, i.e., each agent has at most $k$ different values for the goods. For such instances, we show that an EF1+fPO allocation can be computed in strongly polynomial time. When all values are positive, we show that an EQ1+fPO allocation for such instances can be computed in strongly polynomial time. Next, we consider instances where the number of agents is constant and show that an EF1+PO (likewise, an EQ1+PO) allocation can be computed in polynomial time. These results significantly extend the polynomial-time computability beyond the known cases of binary or identical valuations. We also design a polynomial-time algorithm that computes a Nash welfare maximizing allocation when there are constantly many agents with constant many different values for the goods. Finally, on the complexity side, we show that the problem of computing an EF1+fPO allocation lies in the complexity class PLS.