OpenRaiser/Intern-Atlas huggingface dataset:
An Initial Algebra Theorem Without Iteration
Venue: arXiv cs.LO 2022
Year: 2022

The Initial Algebra Theorem by Trnková et al.~states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point $A$ of the functor, it uses Pataraia's theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of $A$. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.
GraphGuess: Approximate Graph Processing System with Adaptive Correction
Venue: arXiv cs.DC 2022
Year: 2022

Graph-based data structures have drawn great attention in recent years. The large and rapidly growing trend on developing graph processing systems focuses mostly on improving the performance by preprocessing the input graph and modifying its layout. These systems usually take several hours to days to complete processing a single graph on high-end machines, let alone the overhead of pre-processing which most of the time can be dominant. Yet for most graph applications the exact answer is not always crucial, and providing a rough estimate of the final result is adequate. Approximate computing is introduced to trade off accuracy of results for computation or energy savings that could not be achieved by conventional techniques alone. In this work, we design, implement and evaluate GraphGuess, inspired from the domain of approximate graph theory and extend it to a general, practical graph processing system. GraphGuess is essentially an approximate graph processing technique with adaptive correction, which can be implemented on top of any graph processing system. We build a vertex-centric processing system based on GraphGuess, where it allows the user to trade off accuracy for better performance. Our experimental studies show that using GraphGuess can significantly reduce the processing time for large scale graphs while maintaining high accuracy.
Generative Transformer for Accurate and Reliable Salient Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Transformer, which originates from machine translation, is particularly powerful at modeling long-range dependencies. Currently, the transformer is making revolutionary progress in various vision tasks, leading to significant performance improvements compared with the convolutional neural network (CNN) based frameworks. In this paper, we conduct extensive research on exploiting the contributions of transformers for accurate and reliable salient object detection. For the former, we apply transformer to a deterministic model, and explain that the effective structure modeling and global context modeling abilities lead to its superior performance compared with the CNN based frameworks. For the latter, we observe that both CNN and transformer based frameworks suffer greatly from the over-confidence issue, where the models tend to generate wrong predictions with high confidence. To estimate the reliability degree of both CNN- and transformer-based frameworks, we further present a latent variable model, namely inferential generative adversarial network (iGAN), based on the generative adversarial network (GAN). The stochastic attribute of the latent variable makes it convenient to estimate the predictive uncertainty, serving as an auxiliary output to evaluate the reliability of model prediction. Different from the conventional GAN, which defines the distribution of the latent variable as fixed standard normal distribution $\mathcal{N}(0,\mathbf{I})$, the proposed iGAN infers the latent variable by gradient-based Markov Chain Monte Carlo (MCMC), namely Langevin dynamics, leading to an input-dependent latent variable model. We apply our proposed iGAN to both fully and weakly supervised salient object detection, and explain that iGAN within the transformer framework leads to both accurate and reliable salient object detection.
CVLight: Decentralized Learning for Adaptive Traffic Signal Control with Connected Vehicles
Venue: arXiv cs.LG 2022
Year: 2022

This paper develops a decentralized reinforcement learning (RL) scheme for multi-intersection adaptive traffic signal control (TSC), called "CVLight", that leverages data collected from connected vehicles (CVs). The state and reward design facilitates coordination among agents and considers travel delays collected by CVs. A novel algorithm, Asymmetric Advantage Actor-critic (Asym-A2C), is proposed where both CV and non-CV information is used to train the critic network, while only CV information is used to execute optimal signal timing. Comprehensive experiments show the superiority of CVLight over state-of-the-art algorithms under a 2-by-2 synthetic road network with various traffic demand patterns and penetration rates. The learned policy is then visualized to further demonstrate the advantage of Asym-A2C. A pre-train technique is applied to improve the scalability of CVLight, which significantly shortens the training time and shows the advantage in performance under a 5-by-5 road network. A case study is performed on a 2-by-2 road network located in State College, Pennsylvania, USA, to further demonstrate the effectiveness of the proposed algorithm under real-world scenarios. Compared to other baseline models, the trained CVLight agent can efficiently control multiple intersections solely based on CV data and achieve the best performance, especially under low CV penetration rates.
A note on some information-theoretic divergences between Zeta distributions
Venue: arXiv cs.IT 2022
Year: 2022

We consider the zeta distributions which are discrete power law distributions that can be interpreted as the counterparts of the continuous Pareto distributions with unit scale. The family of zeta distributions forms a discrete exponential family with normalizing constants expressed using the Riemann zeta function. We report several information-theoretic measures between zeta distributions and study their underlying information geometry.
What are higher-order networks?
Venue: arXiv cs.SI 2022
Year: 2022

Network-based modeling of complex systems and data using the language of graphs has become an essential topic across a range of different disciplines. Arguably, this graph-based perspective derives its success from the relative simplicity of graphs: A graph consists of nothing more than a set of vertices and a set of edges, describing relationships between pairs of such vertices. This simple combinatorial structure makes graphs interpretable and flexible modeling tools. The simplicity of graphs as system models, however, has been scrutinized in the literature recently. Specifically, it has been argued from a variety of different angles that there is a need for higher-order networks, which go beyond the paradigm of modeling pairwise relationships, as encapsulated by graphs. In this survey article we take stock of these recent developments. Our goals are to clarify (i) what higher-order networks are, (ii) why these are interesting objects of study, and (iii) how they can be used in applications.
Eigenbackground Revisited: Can We Model the Background with Eigenvectors?
Venue: arXiv cs.CV 2022
Year: 2022

Using dominant eigenvectors for background modeling (usually known as Eigenbackground) is a common technique in the literature. However, its results suffer from noticeable artifacts. Thus have been many attempts to reduce the artifacts by making some improvements/enhancement in the Eigenbackground algorithm. In this paper, we show the main problem of the Eigenbackground is in its own core and in fact, it is not a good idea to use strongest eigenvectors for modeling the background. Instead, we propose an alternative solution by exploiting the weakest eigenvectors (which are usually thrown away and treated as garbage data) for background modeling. MATLAB codes are available at \url{https://github.com/mamintoosi/Eigenbackground-Revisited}
Reflexive combinatory algebras
Venue: arXiv cs.LO 2022
Year: 2022

We introduce the notion of reflexivity for combinatory algebras. Reflexivity can be thought of as an equational counterpart of the Meyer-Scott axiom of combinatory models, which indeed allows us to characterise an equationally definable counterpart of combinatory models. This new structure, called strongly reflexive combinatory algebra, admits a finite axiomatisation with seven closed equations, and the structure is shown to be exactly the retract of combinatory models. Lambda algebras can be characterised as strongly reflexive combinatory algebras which are stable. Moreover, there is a canonical construction of a lambda algebra from a strongly reflexive combinatory algebra. The resulting axiomatisation of lambda algebras by the seven axioms for strong reflexivity together with those for stability is shown to correspond to the axiomatisation of lambda algebras due to Selinger [J.Funct.Programming, 12(6), 549--566, 2002].
Time Series Forecasting via Learning Convolutionally Low-Rank Models
Venue: arXiv cs.LG 2022
Year: 2022

Recently, Liu and Zhang studied the rather challenging problem of time series forecasting from the perspective of compressed sensing. They proposed a no-learning method, named Convolution Nuclear Norm Minimization (CNNM), and proved that CNNM can exactly recover the future part of a series from its observed part, provided that the series is convolutionally low-rank. While impressive, the convolutional low-rankness condition may not be satisfied whenever the series is far from being seasonal, and is in fact brittle to the presence of trends and dynamics. This paper tries to approach the issues by integrating a learnable, orthonormal transformation into CNNM, with the purpose for converting the series of involute structures into regular signals of convolutionally low-rank. We prove that the resultant model, termed Learning-Based CNNM (LbCNNM), strictly succeeds in identifying the future part of a series, as long as the transform of the series is convolutionally low-rank. To learn proper transformations that may meet the required success conditions, we devise an interpretable method based on Principal Component Pursuit (PCP). Equipped with this learning method and some elaborate data argumentation skills, LbCNNM not only can handle well the major components of time series (including trends, seasonality and dynamics), but also can make use of the forecasts provided by some other forecasting methods; this means LbCNNM can be used as a general tool for model combination. Extensive experiments on 100,452 real-world time series from Time Series Data Library (TSDL) and M4 Competition (M4) demonstrate the superior performance of LbCNNM.
A Review on C3I Systems' Security: Vulnerabilities, Attacks, and Countermeasures
Venue: arXiv cs.CR 2022
Year: 2022

Command, Control, Communication, and Intelligence (C3I) systems are increasingly used in critical civil and military domains for achieving information superiority, operational efficacy, and greater situational awareness. Unlike traditional systems facing widespread cyber-attacks, the sensitive nature of C3I tactical operations make their cybersecurity a critical concern. For instance, tampering or intercepting confidential information in military battlefields not only damages C3I operations, but also causes irreversible consequences such as loss of human lives and mission failures. Therefore, C3I systems have become a focal point for cyber adversaries. Moreover, technological advancements and modernization of C3I systems have significantly increased the potential risk of cyber-attacks on C3I systems. Consequently, cyber adversaries leverage highly sophisticated attack vectors to exploit security vulnerabilities in C3I systems. Despite the burgeoning significance of cybersecurity for C3I systems, the existing literature lacks a comprehensive review to systematize the body of knowledge on C3I systems' security. Therefore, in this paper, we have gathered, analyzed, and synthesized the state-of-the-art on the cybersecurity of C3I systems. In particular, this paper has identified security vulnerabilities, attack vectors, and countermeasures/defenses for C3I systems. Furthermore, our survey has enabled us to: (i) propose a taxonomy for security vulnerabilities, attack vectors and countermeasures; (ii) interrelate attack vectors with security vulnerabilities and countermeasures; and (iii) propose future research directions for advancing the state-of-the-art on the cybersecurity of C3I systems.
ECLIPSE : Envisioning CLoud Induced Perturbations in Solar Energy
Venue: arXiv cs.CV 2022
Year: 2022

Efficient integration of solar energy into the electricity mix depends on a reliable anticipation of its intermittency. A promising approach to forecast the temporal variability of solar irradiance resulting from the cloud cover dynamics is based on the analysis of sequences of ground-taken sky images or satellite observations. Despite encouraging results, a recurrent limitation of existing deep learning approaches lies in the ubiquitous tendency of reacting to past observations rather than actively anticipating future events. This leads to a frequent temporal lag and limited ability to predict sudden events. To address this challenge, we introduce ECLIPSE, a spatio-temporal neural network architecture that models cloud motion from sky images to not only predict future irradiance levels and associated uncertainties, but also segmented images, which provide richer information on the local irradiance map. We show that ECLIPSE anticipates critical events and reduces temporal delay while generating visually realistic futures. The model characteristics and properties are investigated with an ablation study and a comparative study on the benefits and different ways to integrate auxiliary data into the modelling. The model predictions are also interpreted through an analysis of the principal spatio-temporal components learned during network training.
A Splicing Approach to Best Subset of Groups Selection
Venue: arXiv cs.LG 2022
Year: 2022

Best subset of groups selection (BSGS) is the process of selecting a small part of non-overlapping groups to achieve the best interpretability on the response variable. It has attracted increasing attention and has far-reaching applications in practice. However, due to the computational intractability of BSGS in high-dimensional settings, developing efficient algorithms for solving BSGS remains a research hotspot. In this paper,we propose a group-splicing algorithm that iteratively detects the relevant groups and excludes the irrelevant ones. Moreover, coupled with a novel group information criterion, we develop an adaptive algorithm to determine the optimal model size. Under mild conditions, it is certifiable that our algorithm can identify the optimal subset of groups in polynomial time with high probability. Finally, we demonstrate the efficiency and accuracy of our methods by comparing them with several state-of-the-art algorithms on both synthetic and real-world datasets.
Unsupervised Instance Selection with Low-Label, Supervised Learning for Outlier Detection
Venue: arXiv cs.LG 2022
Year: 2022

The laborious process of labeling data often bottlenecks projects that aim to leverage the power of supervised machine learning. Active Learning (AL) has been established as a technique to ameliorate this condition through an iterative framework that queries a human annotator for labels of instances with the most uncertain class assignment. Via this mechanism, AL produces a binary classifier trained on less labeled data but with little, if any, loss in predictive performance. Despite its advantages, AL can have difficulty with class-imbalanced datasets and results in an inefficient labeling process. To address these drawbacks, we investigate our unsupervised instance selection (UNISEL) technique followed by a Random Forest (RF) classifier on 10 outlier detection datasets under low-label conditions. These results are compared to AL performed on the same datasets. Further, we investigate the combination of UNISEL and AL. Results indicate that UNISEL followed by an RF performs comparably to AL with an RF and that the combination of UNISEL and AL demonstrates superior performance. The practical implications of these findings in terms of time savings and generalizability afforded by UNISEL are discussed.
Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Distributionally robust supervised learning (DRSL) is emerging as a key paradigm for building reliable machine learning systems for real-world applications -- reflecting the need for classifiers and predictive models that are robust to the distribution shifts that arise from phenomena such as selection bias or nonstationarity. Existing algorithms for solving Wasserstein DRSL -- one of the most popular DRSL frameworks based around robustness to perturbations in the Wasserstein distance -- have serious limitations that limit their use in large-scale problems -- in particular they involve solving complex subproblems and they fail to make use of stochastic gradients. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable stochastic extra-gradient algorithms which provably achieve faster convergence rates than existing approaches. We demonstrate their effectiveness on synthetic and real data when compared to existing DRSL approaches. Key to our results is the use of variance reduction and random reshuffling to accelerate stochastic min-max optimization, the analysis of which may be of independent interest.
A ridesharing simulation platform that considers dynamic supply-demand interactions
Venue: arXiv cs.MA 2022
Year: 2022

This paper presents a new ridesharing simulation platform that accounts for dynamic driver supply and passenger demand, and complex interactions between drivers and passengers. The proposed simulation platform explicitly considers driver and passenger acceptance/rejection on the matching options, and cancellation before/after being matched. New simulation events, procedures and modules have been developed to handle these realistic interactions. The capabilities of the simulation platform are illustrated using numerical experiments. The experiments confirm the importance of considering supply and demand interactions and provide new insights to ridesharing operations. Results show that increase of driver supply does not always increase matching option accept rate, and larger matching window could have negative impacts on overall ridesharing success rate. These results emphasize the importance of a careful planning of a ridesharing system.
Truth and Knowledge
Venue: arXiv cs.LO 2022
Year: 2022

The main subjects of this text are: (1) Generalization of concepts and operations, like distance and size, to situations where they are not definable in the usual way. (2) A pragmatic theory of handling contradictions using reliability of the information sources. (3) Relation of formal semantics to brain processes. (4) Remarks on Yablo's coding of the liar paradox in infinite acyclic graphs.
Graph Decoupling Attention Markov Networks for Semi-supervised Graph Node Classification
Venue: arXiv cs.LG 2022
Year: 2022

Graph neural networks (GNN) have been ubiquitous in graph node classification tasks. Most of GNN methods update the node embedding iteratively by aggregating its neighbors' information. However, they often suffer from negative disturbance, due to edges connecting nodes with different labels. One approach to alleviate this negative disturbance is to use attention to learn the weights of aggregation, but current attention-based GNNs only consider feature similarity and also suffer from the lack of supervision. In this paper, we consider the label dependency of graph nodes and propose a decoupling attention mechanism to learn both hard and soft attention. The hard attention is learned on labels for a refined graph structure with fewer inter-class edges, so that the aggregation's negative disturbance can be reduced. The soft attention aims to learn the aggregation weights based on features over the refined graph structure to enhance information gains during message passing. Particularly, we formulate our model under the EM framework, and the learned attention is used to guide the label propagation in the M-step and the feature propagation in the E-step, respectively. Extensive experiments are performed on six well-known benchmark graph datasets to verify the effectiveness of the proposed method.
One-to-Two-Player Lifting for Mildly Growing Memory
Venue: arXiv cs.GT 2022
Year: 2022

We investigate a phenomenon of "one-to-two-player lifting" in infinite-duration two-player games on graphs with zero-sum objectives. More specifically, let $C$ be a class of strategies. It turns out that in many cases, to show that all two-player games on graphs with a given payoff function are determined in $C$, it is sufficient to do so for one-player games. That is, in many cases the determinacy in $C$ can be "lifted" from one-player games to two-player games. Namely, Gimbert and Zielonka~(CONCUR 2005) have shown this for the class of positional strategies. Recently, Bouyer et al. (CONCUR 2020) have extended this to the classes of arena-independent finite-memory strategies. Informally, these are finite-memory strategies that use the same way of storing memory in all game graphs. In this paper, we put the lifting technique into the context of memory complexity. The memory complexity of a payoff function measures, how many states of memory we need to play optimally in game graphs with up to $n$ nodes, depending on $n$. Now, assume that we know the memory complexity of our payoff function in one-player games. Then what can be said about its memory complexity in two-player games? In particular, when is it finite? Previous one-to-two-player lifting theorems only cover the case when the memory complexity is $O(1)$. In turn, we obtain the following results. Assume that the memory complexity in one-player games is sublinear in $n$ on some infinite subsequence. Then the memory complexity in two-player games is finite. We provide an example in which (a) the memory complexity in one-player games is linear in $n$; (b) the memory complexity in two-player games is infinite. Thus, we obtain the exact barrier for the one-to-two-player lifting theorems.