OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Power System Simulation Using the Adomian Decomposition Method
Venue: arXiv cs.SY 2021
Year: 2021

Considering increasing distributed energy resources and responsive loads in smart grid, this paper proposes a stochastic simulation approach for stability analysis of a power system having stochastic loads. The proposed approach solves a stochastic, nonlinear differential equation model of the system in an analytical way by the Adomian decomposition method and generates semi-analytical solutions that express both deterministic and stochastic state variables explicitly as symbolic variables so as to embed stochastic processes directly into the solutions for efficient stability analysis with uncertainties. The proposed approach is tested on the New England 10-machine 39-bus system with different penetration levels of stochastic loads. The approach is also benchmarked with a traditional stochastic simulation approach based on the Euler-Maruyama method. The results show that the new approach has better time performance and a comparable accuracy.
V1: A Visual Query Language for Property Graphs
Venue: arXiv cs.DB 2021
Year: 2021

The property graph is an increasingly popular data model. Pattern construction and pattern matching are important tasks when dealing with property graphs. Given a property graph schema S, a property graph G, and a query pattern P, all expressed in language L, pattern matching is the process of finding, merging, and annotating subgraphs of G that match P. Expressive pattern languages support topological constraints, property values constraints, negations, quantifications, aggregations, and path semantics. Calculated properties may be defined for vertices, edges, and subgraphs, and constraints may be imposed on their evaluation result. Query posers would like to construct patterns with minimal effort, minimal trial and error, and in a manner that is coherent with the way they think. The ability to express patterns in a way that is aligned with their mental processes is crucial to the flow of their work and to the quality of the insights they can draw. Since the capabilities of the human visual system with respect to pattern perception are remarkable, it is a matter of course that query patterns were to be expressed visually. Visual query languages have the potential to be much more 'user-friendly' than their textual counterparts in the sense that patterns may be constructed and understood much more quickly and with much less mental effort. A long-standing challenge is to design a visual query language that is generic, has rich expressive power, and is highly receptive and productive. V1 attempts to answer this challenge. V1 is a declarative visual pattern query language for schema-based property graphs. V1 supports property graphs with mixed (both directed and undirected) edges and unary edges, with multivalued and composite properties, and with null property values. V1 is generic, concise, has rich expressive power, and is highly receptive and productive.
Small-loss bounds for online learning with partial information
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of adversarial (non-stochastic) online learning with partial information feedback, where at each round, a decision maker selects an action from a finite set of alternatives. We develop a black-box approach for such problems where the learner observes as feedback only losses of a subset of the actions that includes the selected action. When losses of actions are non-negative, under the graph-based feedback model introduced by Mannor and Shamir, we offer algorithms that attain the so called "small-loss" $o(αL^{\star})$ regret bounds with high probability, where $α$ is the independence number of the graph, and $L^{\star}$ is the loss of the best action. Prior to our work, there was no data-dependent guarantee for general feedback graphs even for pseudo-regret (without dependence on the number of actions, i.e. utilizing the increased information feedback). Taking advantage of the black-box nature of our technique, we extend our results to many other applications such as semi-bandits (including routing in networks), contextual bandits (even with an infinite comparator class), as well as learning with slowly changing (shifting) comparators. In the special case of classical bandit and semi-bandit problems, we provide optimal small-loss, high-probability guarantees of $\tilde{O}(\sqrt{dL^{\star}})$ for actual regret, where $d$ is the number of actions, answering open questions of Neu. Previous bounds for bandits and semi-bandits were known only for pseudo-regret and only in expectation. We also offer an optimal $\tilde{O}(\sqrt{κL^{\star}})$ regret guarantee for fixed feedback graphs with clique-partition number at most $κ$.
Generative Steganography with Kerckhoffs' Principle
Venue: arXiv cs.MM 2021
Year: 2021

The distortion in steganography that usually comes from the modification or recoding on the cover image during the embedding process leaves the steganalyzer with possibility of discriminating. Faced with such a risk, we propose generative steganography with Kerckhoffs' principle (GSK) in this letter. In GSK, the secret messages are generated by a cover image using a generator rather than embedded into the cover, thus resulting in no modifications in the cover. To ensure the security, the generators are trained to meet Kerckhoffs' principle based on generative adversarial networks (GAN). Everything about the GSK system, except the extraction key, is public knowledge for the receivers. The secret messages can be outputted by the generator if and only if the extraction key and the cover image are both inputted. In the generator training procedures, there are two GANs, Message- GAN and Cover-GAN, designed to work jointly making the generated results under the control of the extraction key and the cover image. We provide experimental results on the training process and give an example of the working process by adopting a generator trained on MNIST, which demonstrate that GSK can use a cover image without any modification to generate messages, and without the extraction key or the cover image, only meaningless results would be obtained.
A Wavelet Plancherel Theory with Application to Multipliers and Sparse Approximations
Venue: arXiv cs.IT 2021
Year: 2021

We introduce an extension of continuous wavelet theory that enables an efficient implementation of multiplicative operators in the coefficient space. In the new theory, the signal space is embedded in a larger abstract signal space -- the so called window-signal space. There is a canonical extension of the wavelet transform to an isometric isomorphism between the window-signal space and the coefficient space. Hence, the new framework is called a wavelet-Plancherel theory, and the extended wavelet transform is called the wavelet-Plancherel transform. Since the wavelet-Plancherel transform is an isometric isomorphism, any operation in the coefficient space can be pulled-back to an operation in the window-signal space. It is then possible to improve the computational complexity of methods that involve a multiplicative operator in the coefficient space, by performing all computations directly in the window-signal space. As one example application, we show how continuous wavelet multipliers (also called Calderón-Toeplitz Operators), with polynomial symbols, can be implemented with linear complexity in the resolution of the 1D signal. As another example, we develop a framework for efficiently computing greedy sparse approximations to signals based on elements of continuous wavelet systems.
On Perfect Privacy
Venue: arXiv cs.IT 2021
Year: 2021

The problem of private data disclosure is studied from an information theoretic perspective. Considering a pair of dependent random variables $(X,Y)$, where $X$ and $Y$ denote the private and useful data, respectively, the following problem is addressed: What is the maximum information that can be revealed about $Y$ (measured by mutual information $I(Y;U)$, in which $U$ is the revealed data), while disclosing no information about $X$ (captured by the condition of statistical independence, i.e., $X\independent U$, and henceforth, called \textit{perfect privacy})? We analyze the supremization of \textit{utility}, i.e., $I(Y;U)$ under the condition of perfect privacy for two scenarios: \textit{output perturbation} and \textit{full data observation} models, which correspond to the cases where a Markov kernel, called \textit{privacy-preserving mapping}, applies to $Y$ and the pair $(X,Y)$, respectively. When both $X$ and $Y$ have a finite alphabet, the linear algebraic analysis involved in the solution provides some interesting results, such as upper/lower bounds on the size of the released alphabet and the maximum utility. Afterwards, it is shown that for the jointly Gaussian $(X,Y)$, perfect privacy is not possible in the output perturbation model in contrast to the full data observation model. Finally, an asymptotic analysis is provided to obtain the rate of released information when a sufficiently small leakage is allowed. In particular, in the context of output perturbation model, it is shown that this rate is always finite when perfect privacy is not feasible, and two lower bounds are provided for it; When perfect privacy is feasible, it is shown that under mild conditions, this rate becomes unbounded.
Spatio-Temporal Pricing for Ridesharing Platforms
Venue: arXiv cs.GT 2021
Year: 2021

Ridesharing platforms match drivers and riders to trips, using dynamic prices to balance supply and demand. A challenge is to set prices that are appropriately smooth in space and time, so that drivers with the flexibility to decide how to work will nevertheless choose to accept their dispatched trips, rather than drive to another area or wait for higher prices or a better trip. In this work, we propose a complete information model that is simple yet rich enough to incorporate spatial imbalance and temporal variations in supply and demand -- conditions that lead to market failures in today's platforms. We introduce the Spatio-Temporal Pricing (STP) mechanism. The mechanism is incentive-aligned, in that it is a subgame-perfect equilibrium for drivers to always accept their trip dispatches. From any history onward, the equilibrium outcome of the STP mechanism is welfare-optimal, envy-free, individually rational, budget balanced, and core-selecting. We also prove the impossibility of achieving the same economic properties in a dominant-strategy equilibrium. Simulation results show that the STP mechanism can achieve substantially improved social welfare and earning equity than a myopic mechanism.
Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
Venue: arXiv cs.DS 2021
Year: 2021

This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser known topics like stochastic domination and coupling or Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, some, however, only in recent conference publications. While the focus is on collecting tools for the analysis of randomized search heuristics, many of these may be useful as well in the analysis of classic randomized algorithms or discrete random structures.
On p/q-recognisable sets
Venue: arXiv cs.LO 2021
Year: 2021

Let p/q be a rational number. Numeration in base p/q is defined by a function that evaluates each finite word over A_p={0,1,...,p-1} to some rational number. We let N_p/q denote the image of this evaluation function. In particular, N_p/q contains all nonnegative integers and the literature on base p/q usually focuses on the set of words that are evaluated to nonnegative integers; it is a rather chaotic language which is not context-free. On the contrary, we study here the subsets of (N_p/q)^d that are p/q-recognisable, i.e. realised by finite automata over (A_p)^d. First, we give a characterisation of these sets as those definable in a first-order logic, similar to the one given by the Büchi-Bruyère Theorem for integer bases numeration systems. Second, we show that the natural order relation and the modulo-q operator are not p/q-recognisable.
Learning from Informants: Relations between Learning Success Criteria
Venue: arXiv cs.FL 2021
Year: 2021

Learning from positive and negative information, so-called \emph{informants}, being one of the models for human and machine learning introduced by E.~M.~Gold, is investigated. Particularly, naturally arising questions about this learning setting, originating in results on learning from solely positive information, are answered. By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data (such a learning behavior is called \emph{conservative}). The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for \emph{delayability} being the right structural property to gain a deeper understanding concerning the nature of learning success criteria. Moreover, we obtain an anomalous \emph{hierarchy} when allowing for an increasing finite number of \emph{anomalies} of the hypothesized language by the learner compared with the language to be learned. In contrast to the vacillatory hierarchy for learning from solely positive information, we observe a \emph{duality} depending on whether infinitely many \emph{vacillations} between different (almost) correct hypotheses are still considered a successful learning behavior.
Decidability for Entailments of Symbolic Heaps with Arrays
Venue: arXiv cs.LO 2021
Year: 2021

This paper presents two decidability results on the validity checking problem for entailments of symbolic heaps in separation logic with Presburger arithmetic and arrays. The first result is for a system with arrays and existential quantifiers. The correctness of the decision procedure is proved under the condition that sizes of arrays in the succedent are not existentially quantified. This condition is different from that proposed by Brotherston et al. in 2017 and one of them does not imply the other. The main idea is a novel translation from an entailment of symbolic heaps into a formula in Presburger arithmetic. The second result is the decidability for a system with both arrays and lists. The key idea is to extend the unroll collapse technique proposed by Berdine et al. in 2005 to arrays and arithmetic as well as double-linked lists.
Structural Properties of Bichromatic Non-crossing Matchings
Venue: arXiv cs.CG 2021
Year: 2021

Given a set of $n$ red and $n$ blue points in the plane, we are interested in matching red points with blue points by straight line segments so that the segments do not cross. We develop a range of tools for dealing with the non-crossing matchings of points in convex position. It turns out that the points naturally partition into groups that we refer to as orbits, with a number of properties that prove useful for studying and efficiently processing the non-crossing matchings. Bottleneck matching is such a matching that minimizes the length of the longest segment. Illustrating the use of the developed tools, we solve the problem of finding bottleneck matchings of points in convex position in $O(n^2)$ time. Subsequently, combining our tools with a geometric analysis we design an $O(n)$-time algorithm for the case where the given points lie on a circle. Previously best known results were $O(n^3)$ for points in convex position, and $O(n \log n$) for points on a circle.
Learning Representative Temporal Features for Action Recognition
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, a novel video classification method is presented that aims to recognize different categories of third-person videos efficiently. Our motivation is to achieve a light model that could be trained with insufficient training data. With this intuition, the processing of the 3-dimensional video input is broken to 1D in temporal dimension on top of the 2D in spatial. The processes related to 2D spatial frames are being done by utilizing pre-trained networks with no training phase. The only step which involves training is to classify the 1D time series resulted from the description of the 2D signals. As a matter of fact, optical flow images are first calculated from consecutive frames and described by pre-trained CNN networks. Their dimension is then reduced using PCA. By stacking the description vectors beside each other, a multi-channel time series is created for each video. Each channel of the time series represents a specific feature and follows it over time. The main focus of the proposed method is to classify the obtained time series effectively. Towards this, the idea is to let the machine learn temporal features. This is done by training a multi-channel one dimensional Convolutional Neural Network (1D-CNN). The 1D-CNN learns the features along the only temporal dimension. Hence, the number of training parameters decreases significantly which would result in the trainability of the method on even smaller datasets. It is illustrated that the proposed method could reach the state-of-the-art results on two public datasets UCF11, jHMDB and competitive results on HMDB51.
Distributed Compression of Graphical Data
Venue: arXiv cs.IT 2021
Year: 2021

In contrast to time series, graphical data is data indexed by the vertices and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian-Wolf theorem. We characterize the rate region when the statistical description of the distributed graphical data can be modeled as being one of two types - as a member of a sequence of marked sparse Erdos-Renyi ensembles or as a member of a sequence of marked configuration model ensembles. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs. Furthermore, we give a generalization of this result for Erdos-Renyi and configuration model ensembles with more than two sources.
Manipulating and Measuring Model Interpretability
Venue: arXiv cs.AI 2021
Year: 2021

With machine learning models being increasingly used to aid decision making even in high-stakes domains, there has been a growing interest in developing interpretable models. Although many supposedly interpretable models have been proposed, there have been relatively few experimental studies investigating whether these models achieve their intended effects, such as making people more closely follow a model's predictions when it is beneficial for them to do so or enabling them to detect when a model has made a mistake. We present a sequence of pre-registered experiments (N=3,800) in which we showed participants functionally identical models that varied only in two factors commonly thought to make machine learning models more or less interpretable: the number of features and the transparency of the model (i.e., whether the model internals are clear or black box). Predictably, participants who saw a clear model with few features could better simulate the model's predictions. However, we did not find that participants more closely followed its predictions. Furthermore, showing participants a clear model meant that they were less able to detect and correct for the model's sizable mistakes, seemingly due to information overload. These counterintuitive findings emphasize the importance of testing over intuition when developing interpretable models.
Training Deep Learning Based Denoisers without Ground Truth Data
Venue: arXiv cs.CV 2021
Year: 2021

Recently developed deep-learning-based denoisers often outperform state-of-the-art conventional denoisers such as the BM3D. They are typically trained to minimize the mean squared error (MSE) between the output image of a deep neural network (DNN) and a ground truth image. Thus, it is important for deep-learning-based denoisers to use high quality noiseless ground truth data for high performance. However, it is often challenging or even infeasible to obtain noiseless images in some applications. Here, we propose a method based on Stein's unbiased risk estimator (SURE) for training DNN denoisers based only on the use of noisy images in the training data with Gaussian noise. We demonstrate that our SURE-based method, without the use of ground truth data, is able to train DNN denoisers to yield performances close to those networks trained with ground truth for both grayscale and color images. We also propose a SURE-based refining method with a noisy test image for further performance improvement. Our quick refining method outperformed conventional BM3D, deep image prior, and often the networks trained with ground truth. Potential extension of our SURE-based methods to Poisson noise model was also investigated.
Comparative Statics via Stochastic Orderings in a Two-Echelon Market with Upstream Demand Uncertainty
Venue: arXiv cs.GT 2021
Year: 2021

We revisit the classic Cournot model and extend it to a two-echelon supply chain with an upstream supplier who operates under demand uncertainty and multiple downstream retailers who compete over quantity. The supplier's belief about retail demand is modeled via a continuous probability distribution function F. If F has the decreasing generalized mean residual life (DGMRL) property, then the supplier's optimal pricing policy exists and is the unique fixed point of the mean residual life (MRL) function. This closed form representation of the supplier's equilibrium strategy facilitates a transparent comparative statics and sensitivity analysis. We utilize the theory of stochastic orderings to study the response of the equilibrium fundamentals - wholesale price, retail price and quantity - to different demand distribution parameters. We examine supply chain performance, in terms of the distribution of profits, supply chain efficiency, in terms of the Price of Anarchy, and complement our findings with numerical results.
A Tutorial On Autonomous Vehicle Steering Controller Design, Simulation and Implementation
Venue: arXiv cs.RO 2021
Year: 2021

In this tutorial, we detailed simple controllers for autonomous parking and path following for self-driving cars providing practical methods for curvature computation.
Definable decompositions for graphs of bounded linear cliquewidth
Venue: arXiv cs.LO 2021
Year: 2021

We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of CMSO_1-definability and recognizability on graphs of bounded linear cliquewidth.