OpenRaiser/Intern-Atlas huggingface dataset:
Parameter Synthesis for Markov Models: Covering the Parameter Space
Venue: arXiv cs.LO 2023
Year: 2023

Markov chain analysis is a key technique in formal verification. A practical obstacle is that all probabilities in Markov models need to be known. However, system quantities such as failure rates or packet loss ratios, etc. are often not -- or only partially -- known. This motivates considering parametric models with transitions labeled with functions over parameters. Whereas traditional Markov chain analysis relies on a single, fixed set of probabilities, analysing parametric Markov models focuses on synthesising parameter values that establish a given safety or performance specification $φ$. Examples are: what component failure rates ensure the probability of a system breakdown to be below 0.00000001?, or which failure rates maximise the performance, for instance the throughput, of the system? This paper presents various analysis algorithms for parametric discrete-time Markov chains and Markov decision processes. We focus on three problems: (a) do all parameter values within a given region satisfy $φ$?, (b) which regions satisfy $φ$ and which ones do not?, and (c) an approximate version of (b) focusing on covering a large fraction of all possible parameter values. We give a detailed account of the various algorithms, present a software tool realising these techniques, and report on an extensive experimental evaluation on benchmarks that span a wide range of applications.
On ZpZp[u, v]-additive cyclic and constacyclic codes
Venue: arXiv cs.IT 2023
Year: 2023

Let $\mathbb{Z}_{p}$ be the ring of residue classes modulo a prime $p$. The $\mathbb{Z}_{p}\mathbb{Z}_{p}[u,v]$-additive cyclic codes of length $(α,β)$ is identify as $\mathbb{Z}_{p}[u,v][x]$-submodule of $\mathbb{Z}_{p}[x]/\langle x^α-1\rangle \times \mathbb{Z}_{p}[u,v][x]/\langle x^β-1\rangle$ where $\mathbb{Z}_{p}[u,v]=\mathbb{Z}_{p}+u\mathbb{Z}_{p}+v\mathbb{Z}_{p}$ with $u^{2}=v^{2}=uv=vu=0$. In this article, we obtain the complete sets of generator polynomials, minimal generating sets for cyclic codes with length $β$ over $\mathbb{Z}_{p}[u,v]$ and $\mathbb{Z}_{p}\mathbb{Z}_{p}[u,v]$-additive cyclic codes with length $(α,β)$ respectively. We show that the Gray image of $\mathbb{Z}_{p}\mathbb{Z}_{p}[u,v]$-additive cyclic code with length $(α,β)$ is either a QC code of length $4α$ with index $4$ or a generalized QC code of length $(α,3β)$ over $\mathbb{Z}_{p}$. Moreover, some structural properties like generating polynomials, minimal generating sets of $\mathbb{Z}_{p}\mathbb{Z}_{p}[u,v]$-additive constacyclic code with length $(α,p-1)$ are determined.
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
Venue: arXiv cs.DC 2023
Year: 2023

Given a boolean predicate $Π$ on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for $Π$ is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying $Π$. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size $n$ of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $Ω(\log \log n)$-bit per node registers in some $n$-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms.
Invariant Feature Coding using Tensor Product Representation
Venue: arXiv cs.CV 2023
Year: 2023

In this study, a novel feature coding method that exploits invariance for transformations represented by a finite group of orthogonal matrices is proposed. We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier using convex loss minimization. Based on this result, a novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering, which are commonly used in most feature coding methods, and global feature functions. Although the global feature functions are in general complex nonlinear functions, the group action on this space can be easily calculated by constructing these functions as tensor-product representations of basic representations, resulting in an explicit form of invariant feature functions. The effectiveness of our method is demonstrated on several image datasets.
Counterfactual Inference for Consumer Choice Across Many Product Categories
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a method for estimating consumer preferences among discrete choices, where the consumer chooses at most one product in a category, but selects from multiple categories in parallel. The consumer's utility is additive in the different categories. Her preferences about product attributes as well as her price sensitivity vary across products and are in general correlated across products. We build on techniques from the machine learning literature on probabilistic models of matrix factorization, extending the methods to account for time-varying product attributes and products going out of stock. We evaluate the performance of the model using held-out data from weeks with price changes or out of stock products. We show that our model improves over traditional modeling approaches that consider each category in isolation. One source of the improvement is the ability of the model to accurately estimate heterogeneity in preferences (by pooling information across categories); another source of improvement is its ability to estimate the preferences of consumers who have rarely or never made a purchase in a given category in the training data. Using held-out data, we show that our model can accurately distinguish which consumers are most price sensitive to a given product. We consider counterfactuals such as personally targeted price discounts, showing that using a richer model such as the one we propose substantially increases the benefits of personalization in discounts.
Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Tight estimation of the Lipschitz constant for deep neural networks (DNNs) is useful in many applications ranging from robustness certification of classifiers to stability analysis of closed-loop systems with reinforcement learning controllers. Existing methods in the literature for estimating the Lipschitz constant suffer from either lack of accuracy or poor scalability. In this paper, we present a convex optimization framework to compute guaranteed upper bounds on the Lipschitz constant of DNNs both accurately and efficiently. Our main idea is to interpret activation functions as gradients of convex potential functions. Hence, they satisfy certain properties that can be described by quadratic constraints. This particular description allows us to pose the Lipschitz constant estimation problem as a semidefinite program (SDP). The resulting SDP can be adapted to increase either the estimation accuracy (by capturing the interaction between activation functions of different layers) or scalability (by decomposition and parallel implementation). We illustrate the utility of our approach with a variety of experiments on randomly generated networks and on classifiers trained on the MNIST and Iris datasets. In particular, we experimentally demonstrate that our Lipschitz bounds are the most accurate compared to those in the literature. We also study the impact of adversarial training methods on the Lipschitz bounds of the resulting classifiers and show that our bounds can be used to efficiently provide robustness guarantees.
Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience
Venue: arXiv cs.DS 2023
Year: 2023

We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process, and derive new results for these online matching problems under the adversarial, non-stationary, and IID arrival models, assuming we can (approximately) solve the product ranking problem for each single customer. To that end, we show new results for product ranking under two cascade-click models: an optimal algorithm when each item has its own hazard rate for making the customer depart, and a 1/2-approximate algorithm when the customer has a general item-independent patience distribution. We also present a constant-factor 0.027-approximate algorithm in a new model where items are not initially available and arrive over time. We complement these positive results by presenting three additional negative results relating to these problems.
No-dimensional Tverberg Theorems and Algorithms
Venue: arXiv cs.CG 2023
Year: 2023

Tverberg's theorem states that for any $k \ge 2$ and any set $P \subset \mathbb{R}^d$ of at least $(d + 1)(k - 1) + 1$ points in $d$ dimensions, we can partition $P$ into $k$ subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class $\text{CLS} = \text{PPAD} \cap \text{PLS}$, but no hardness results are known. In the colorful Tverberg theorem, the points in $P$ have colors, and under certain conditions, $P$ can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Barany, and Mustafa gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of $P$. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any $n$-point set $P \subset \mathbb{R}^d$ and any $k \in \{2, \dots, n\}$ in $O(nd \lceil{\log k}\rceil)$ time a $k$-partition of $P$ such that there is a ball of radius $O\left((k/\sqrt{n})\mathrm{diam(P)}\right)$ that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method to reduce the Tverberg problem to the Colorful Caratheodory problem (in the simplified tensor product interpretation of Barany and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Venue: arXiv cs.DS 2023
Year: 2023

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In $H$-free graphs, that is, graphs not containing a fixed graph $H$ as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever $H$ contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of $H$ is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs $H$ such as $P_5$, $P_6$, the claw, or the fork. We show that for every graph $H$ for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in $H$-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.
Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning
Venue: arXiv cs.AI 2023
Year: 2023

We propose Stable Yet Memory Bounded Open-Loop (SYMBOL) planning, a general memory bounded approach to partially observable open-loop planning. SYMBOL maintains an adaptive stack of Thompson Sampling bandits, whose size is bounded by the planning horizon and can be automatically adapted according to the underlying domain without any prior domain knowledge beyond a generative model. We empirically test SYMBOL in four large POMDP benchmark problems to demonstrate its effectiveness and robustness w.r.t. the choice of hyperparameters and evaluate its adaptive memory consumption. We also compare its performance with other open-loop planning algorithms and POMCP.
Towards Automated Infographic Design: Deep Learning-based Auto-Extraction of Extensible Timeline
Venue: arXiv cs.HC 2023
Year: 2023

Designers need to consider not only perceptual effectiveness but also visual styles when creating an infographic. This process can be difficult and time consuming for professional designers, not to mention non-expert users, leading to the demand for automated infographics design. As a first step, we focus on timeline infographics, which have been widely used for centuries. We contribute an end-to-end approach that automatically extracts an extensible timeline template from a bitmap image. Our approach adopts a deconstruction and reconstruction paradigm. At the deconstruction stage, we propose a multi-task deep neural network that simultaneously parses two kinds of information from a bitmap timeline: 1) the global information, i.e., the representation, scale, layout, and orientation of the timeline, and 2) the local information, i.e., the location, category, and pixels of each visual element on the timeline. At the reconstruction stage, we propose a pipeline with three techniques, i.e., Non-Maximum Merging, Redundancy Recover, and DL GrabCut, to extract an extensible template from the infographic, by utilizing the deconstruction results. To evaluate the effectiveness of our approach, we synthesize a timeline dataset (4296 images) and collect a real-world timeline dataset (393 images) from the Internet. We first report quantitative evaluation results of our approach over the two datasets. Then, we present examples of automatically extracted templates and timelines automatically generated based on these templates to qualitatively demonstrate the performance. The results confirm that our approach can effectively extract extensible templates from real-world timeline infographics.
A Whittle Index Approach to Minimizing Functions of Age of Information
Venue: arXiv cs.IT 2023
Year: 2023

We consider a setting where multiple active sources send real-time updates over a single-hop wireless broadcast network to a monitoring station. Our goal is to design a scheduling policy that minimizes the time-average of general non-decreasing cost functions of Age of Information. We use a Whittle index based approach to find low complexity scheduling policies that have good performance. We prove that for a system with two sources, having possibly different cost functions and reliable channels, the Whittle index policy is exactly optimal. We derive structural properties of an optimal policy, that suggest that the performance of the Whittle index policy may be close to optimal in general. These results might also be of independent interest in the study of restless multi-armed bandit problems with similar underlying structure. We further establish that minimizing monitoring error for linear time-invariant systems and symmetric Markov chains is equivalent to minimizing appropriately chosen monotone functions of Age of Information. Finally, we provide simulations comparing the Whittle index policy with optimal scheduling policies found using dynamic programming, which support our results.
MDP Playground: An Analysis and Debug Testbed for Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

We present MDP Playground, a testbed for Reinforcement Learning (RL) agents with dimensions of hardness that can be controlled independently to challenge agents in different ways and obtain varying degrees of hardness in toy and complex RL environments. We consider and allow control over a wide variety of dimensions, including delayed rewards, sequence lengths, reward density, stochasticity, image representations, irrelevant features, time unit, action range and more. We define a parameterised collection of fast-to-run toy environments in OpenAI Gym by varying these dimensions and propose to use these to understand agents better. We then show how to design experiments using MDP Playground to gain insights on the toy environments. We also provide wrappers that can inject many of these dimensions into any Gym environment. We experiment with these wrappers on Atari and Mujoco to allow for understanding the effects of these dimensions on environments that are more complex than the toy environments. We also compare the effect of the dimensions on the toy and complex environments. Finally, we show how to use MDP Playground to debug agents, to study the interaction of multiple dimensions and describe further use-cases.
BSDAR: Beam Search Decoding with Attention Reward in Neural Keyphrase Generation
Venue: arXiv cs.CL 2023
Year: 2023

This study mainly investigates two common decoding problems in neural keyphrase generation: sequence length bias and beam diversity. To tackle the problems, we introduce a beam search decoding strategy based on word-level and ngram-level reward function to constrain and refine Seq2Seq inference at test time. Results show that our simple proposal can overcome the algorithm bias to shorter and nearly identical sequences, resulting in a significant improvement of the decoding performance on generating keyphrases that are present and absent in source text.
Practical Low Latency Proof of Work Consensus
Venue: arXiv cs.DC 2023
Year: 2023

Bitcoin is the first fully-decentralized permissionless blockchain protocol to achieve a high level of security, but at the expense of poor throughput and latency. Scaling the performance of Bitcoin has a been a major recent direction of research. One successful direction of work has involved replacing proof of work (PoW) by proof of stake (PoS). Proposals to scale the performance in the PoW setting itself have focused mostly on parallelizing the mining process, scaling throughput; the few proposals to improve latency have either sacrificed throughput or the latency guarantees involve large constants rendering it practically useless. Our first contribution is to design a new PoW blockchain Prism++ that has provably low latency and high throughput; the design retains the parallel-chain approach espoused in Prism but invents a new confirmation rule to infer the permanency of a block by combining information across the parallel chains. We show security at the level of Bitcoin with very small confirmation latency (a small constant factor of block interarrival time). A key aspect to scaling the performance is to use a large number of parallel chains, which puts significant strain on the system. Our second contribution is the design and evaluation of a practical system to efficiently manage the memory, computation, and I/O imperatives of a large number of parallel chains. Our implementation of Prism++ achieves a throughput of over 80,000 transactions per second and confirmation latency of tens of seconds on networks of up to 900 EC2 Virtual Machines.
Dual-Stream Pyramid Registration Network
Venue: arXiv cs.CV 2023
Year: 2023

We propose a Dual-Stream Pyramid Registration Network (referred as Dual-PRNet) for unsupervised 3D medical image registration. Unlike recent CNN-based registration approaches, such as VoxelMorph, which explores a single-stream encoder-decoder network to compute a registration fields from a pair of 3D volumes, we design a two-stream architecture able to compute multi-scale registration fields from convolutional feature pyramids. Our contributions are two-fold: (i) we design a two-stream 3D encoder-decoder network which computes two convolutional feature pyramids separately for a pair of input volumes, resulting in strong deep representations that are meaningful for deformation estimation; (ii) we propose a pyramid registration module able to predict multi-scale registration fields directly from the decoding feature pyramids. This allows it to refine the registration fields gradually in a coarse-to-fine manner via sequential warping, and enable the model with the capability for handling significant deformations between two volumes, such as large displacements in spatial domain or slice space. The proposed Dual-PRNet is evaluated on two standard benchmarks for brain MRI registration, where it outperforms the state-of-the-art approaches by a large margin, e.g., having improvements over recent VoxelMorph [2] with 0.683->0.778 on the LPBA40, and 0.511->0.631 on the Mindboggle101, in term of average Dice score. Code is available at: https://github.com/kangmiao15/Dual-Stream-PRNet-Plus.
Effective Stabilized Self-Training on Few-Labeled Graph Data
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural networks (GNNs) are designed for semi-supervised node classification on graphs where only a subset of nodes have class labels. However, under extreme cases when very few labels are available (e.g., 1 labeled node per class), GNNs suffer from severe performance degradation. Specifically, we observe that existing GNNs suffer from unstable training process on few-labeled graphs, resulting to inferior performance on node classification. Therefore, we propose an effective framework, Stabilized Self-Training (SST), which is applicable to existing GNNs to handle the scarcity of labeled data, and consequently, boost classification accuracy. We conduct thorough empirical and theoretical analysis to support our findings and motivate the algorithmic designs in SST. We apply SST to two popular GNN models GCN and DAGNN, to get SSTGCN and SSTDA methods respectively, and evaluate the two methods against 10 competitors over 5 benchmarking datasets. Extensive experiments show that the proposed SST framework is highly effective, especially when few labeled data are available. Our methods achieve superior performance under almost all settings over all datasets. For instance, on a Cora dataset with only 1 labeled node per class, the accuracy of SSTGCN is 62.5%, 17.9% higher than GCN, and the accuracy of SSTDA is 66.4%, which outperforms DAGNN by 6.6%.