OpenRaiser/Intern-Atlas huggingface dataset:
Learning Successor States and Goal-Dependent Values: A Mathematical Viewpoint
Venue: arXiv cs.LG 2021
Year: 2021

In reinforcement learning, temporal difference-based algorithms can be sample-inefficient: for instance, with sparse rewards, no learning occurs until a reward is observed. This can be remedied by learning richer objects, such as a model of the environment, or successor states. Successor states model the expected future state occupancy from any given state for a given policy and are related to goal-dependent value functions, which learn how to reach arbitrary states. We formally derive the temporal difference algorithm for successor state and goal-dependent value function learning, either for discrete or for continuous environments with function approximation. Especially, we provide finite-variance estimators even in continuous environments, where the reward for exactly reaching a goal state becomes infinitely sparse. Successor states satisfy more than just the Bellman equation: a backward Bellman operator and a Bellman-Newton (BN) operator encode path compositionality in the environment. The BN operator is akin to second-order gradient descent methods and provides the true update of the value function when acquiring more observations, with explicit tabular bounds. In the tabular case and with infinitesimal learning rates, mixing the usual and backward Bellman operators provably improves eigenvalues for asymptotic convergence, and the asymptotic convergence of the BN operator is provably better than TD, with a rate independent from the environment. However, the BN method is more complex and less robust to sampling noise. Finally, a forward-backward (FB) finite-rank parameterization of successor states enjoys reduced variance and improved samplability, provides a direct model of the value function, has fully understood fixed points corresponding to long-range dependencies, approximates the BN method, and provides two canonical representations of states as a byproduct.
PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts
Venue: arXiv cs.SI 2021
Year: 2021

The identification and counting of small graph patterns, called network motifs, is a fundamental primitive in the analysis of networks, with application in various domains, from social networks to neuroscience. Several techniques have been designed to count the occurrences of motifs in static networks, with recent work focusing on the computational challenges provided by large networks. Modern networked datasets contain rich information, such as the time at which the events modeled by the networks edges happened, which can provide useful insights into the process modeled by the network. The analysis of motifs in temporal networks, called temporal motifs, is becoming an important component in the analysis of modern networked datasets. Several methods have been recently designed to count the number of instances of temporal motifs in temporal networks, which is even more challenging than its counterpart for static networks. Such methods are either exact, and not applicable to large networks, or approximate, but provide only weak guarantees on the estimates they produce and do not scale to very large networks. In this work we present an efficient and scalable algorithm to obtain rigorous approximations of the count of temporal motifs. Our algorithm is based on a simple but effective sampling approach, which renders our algorithm practical for very large datasets. Our extensive experimental evaluation shows that our algorithm provides estimates of temporal motif counts which are more accurate than the state-of-the-art sampling algorithms, with significantly lower running time than exact approaches, enabling the study of temporal motifs, of size larger than the ones considered in previous works, on billion edges networks.
Formal FT-based Cause-Consequence Reliability Analysis using Theorem Proving
Venue: arXiv cs.FL 2021
Year: 2021

Cause-consequence Diagram (CCD) is widely used as a deductive safety analysis technique for decision-making at the critical-system design stage. This approach models the causes of subsystem failures in a highly-critical system and their potential consequences using Fault Tree (FT) and Event Tree (ET) methods, which are well-known dependability modeling techniques. Paper-and-pencil-based approaches and simulation tools, such as the Monte-Carlo approach, are commonly used to carry out CCD analysis, but lack the ability to rigorously verify essential system reliability properties. In this work, we propose to use formal techniques based on theorem proving for the formal modeling and step-analysis of CCDs to overcome the inaccuracies of the simulation-based analysis and the error-proneness of informal reasoning by mathematical proofs. In particular, we use the HOL4 theorem prover, which is a computer-based mathematical reasoning tool. To this end, we developed a formalization of CCDs in Higher-Order Logic (HOL), based on the algebraic approach, using HOL4. We demonstrate the practical effectiveness of the proposed CCD formalization by performing the formal reliability analysis of the IEEE 39-bus electrical power network. Also, we formally determine the Forced Outage Rate (FOR) of the power generation units and the network reliability index, i.e., System Average Interruption Duration Index (SAIDI). To assess the accuracy of our proposed approach, we compare our results with those obtained with MATLAB Monte-Carlo Simulation (MCS) as well as other state-of-the-art approaches for subsystem-level reliability analysis.
"I Won the Election!": An Empirical Analysis of Soft Moderation Interventions on Twitter
Venue: arXiv cs.SI 2021
Year: 2021

Over the past few years, there is a heated debate and serious public concerns regarding online content moderation, censorship, and the principle of free speech on the Web. To ease these concerns, social media platforms like Twitter and Facebook refined their content moderation systems to support soft moderation interventions. Soft moderation interventions refer to warning labels attached to potentially questionable or harmful content to inform other users about the content and its nature while the content remains accessible, hence alleviating concerns related to censorship and free speech. In this work, we perform one of the first empirical studies on soft moderation interventions on Twitter. Using a mixed-methods approach, we study the users who share tweets with warning labels on Twitter and their political leaning, the engagement that these tweets receive, and how users interact with tweets that have warning labels. Among other things, we find that 72% of the tweets with warning labels are shared by Republicans, while only 11% are shared by Democrats. By analyzing content engagement, we find that tweets with warning labels had more engagement compared to tweets without warning labels. Also, we qualitatively analyze how users interact with content that has warning labels finding that the most popular interactions are related to further debunking false claims, mocking the author or content of the disputed tweet, and further reinforcing or resharing false claims. Finally, we describe concrete examples of inconsistencies, such as warning labels that are incorrectly added or warning labels that are not added on tweets despite sharing questionable and potentially harmful information.
Impact of COVID-19 on IoT Adoption in Healthcare, Smart Homes, Smart Buildings, Smart Cities, Transportation and Industrial IoT
Venue: arXiv cs.CY 2021
Year: 2021

COVID-19 has disrupted normal life and has enforced a substantial change in the policies, priorities and activities of individuals, organisations and governments. These changes are proving to be a catalyst for technology and innovation. In this paper, we discuss the pandemic's potential impact on the adoption of the Internet of Things (IoT) in various broad sectors namely healthcare, smart homes, smart buildings, smart cities, transportation and industrial IoT. Our perspective and forecast of this impact on IoT adoption is based on a thorough research literature review, a careful examination of reports from leading consulting firms and interactions with several industry experts. For each of these sectors, we also provide the details of notable IoT initiatives taken in wake of COVID-19. We also highlight the challenges that need to be addressed and important research directions that will facilitate accelerated IoT adoption.
Syntroids: Synthesizing a Game for FPGAs using Temporal Logic Specifications
Venue: arXiv cs.LO 2021
Year: 2021

We present Syntroids, a case study for the automatic synthesis of hardware from a temporal logic specification. Syntroids is a space shooter arcade game realized on an FPGA, where the control flow architecture has been completely specified in Temporal Stream Logic (TSL) and implemented using reactive synthesis. TSL is a recently introduced temporal logic that separates control and data. This leads to scalable synthesis, because the cost of the synthesis process is independent of the complexity of the handled data. In this case study, we report on our experience with the TSL-based development of the Syntroids game and on the implementation quality obtained with synthesis in comparison to manual programming. We also discuss solved and open challenges with respect to currently available synthesis tools.
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim
Venue: arXiv cs.CC 2021
Year: 2021

In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, contrasting intractability, and intrinsic connection to two other combinatorial games, one inspired by social influence and another inspired by quantum superpositions. More precisely, we show that Transverse Wave is at the intersection of social-influence-inspired Friend Circle and superposition-based Demi-Quantum Nim. Transverse Wave is also connected with Schaefer's logic game Avoid True. In addition to analyzing the mathematical structures and computational complexity of Transverse Wave, we provide a web-based version of the game, playable at https://turing.plymouth.edu/~kgb1013/DB/combGames/transverseWave.html. Furthermore, we formulate a basic network-influence inspired game, called Demographic Influence, which simultaneously generalizes Node-Kyles and Demi-Quantum Nim (which in turn contains as special cases Nim, Avoid True, and Transverse Wave). These connections illuminate the lattice order, induced by special-case/generalization relationships over mathematical games, fundamental to both the design and comparative analyses of combinatorial games.
Guided parallelized stochastic gradient descent for delay compensation
Venue: arXiv cs.LG 2021
Year: 2021

Stochastic gradient descent (SGD) algorithm and its variations have been effectively used to optimize neural network models. However, with the rapid growth of big data and deep learning, SGD is no longer the most suitable choice due to its natural behavior of sequential optimization of the error function. This has led to the development of parallel SGD algorithms, such as asynchronous SGD (ASGD) and synchronous SGD (SSGD) to train deep neural networks. However, it introduces a high variance due to the delay in parameter (weight) update. We address this delay in our proposed algorithm and try to minimize its impact. We employed guided SGD (gSGD) that encourages consistent examples to steer the convergence by compensating the unpredictable deviation caused by the delay. Its convergence rate is also similar to A/SSGD, however, some additional (parallel) processing is required to compensate for the delay. The experimental results demonstrate that our proposed approach has been able to mitigate the impact of delay for the quality of classification accuracy. The guided approach with SSGD clearly outperforms sequential SGD and even achieves the accuracy close to sequential SGD for some benchmark datasets.
Semi-Blind Cascaded Channel Estimation for Reconfigurable Intelligent Surface Aided Massive MIMO
Venue: arXiv cs.IT 2021
Year: 2021

Reconfigurable intelligent surface (RIS) is envisioned to be a promising green technology to reduce the energy consumption and improve the coverage and spectral efficiency of massive multiple-input multiple-output (MIMO) wireless networks. In a RIS-aided MIMO system, the acquisition of channel state information (CSI) is important for achieving passive beamforming gains of the RIS, but is also challenging due to the cascaded property of the transmitter-RIS-receiver channel and the lack of signal processing capability of the passive RIS elements. The state-of-the-art approach for CSI acquisition in such a system is a pure training-based strategy that depends on a long sequence of pilot symbols. In this paper, we investigate semi-blind cascaded channel estimation for RIS-aided massive MIMO systems, in which the receiver simultaneously estimates the channel coefficients and the partially unknown transmit signal with a small number of pilot sequences. Specifically, we formulate the semi-blind cascaded channel estimation as a trilinear matrix factorization task. Under the Bayesian inference framework, we develop a computationally efficient iterative algorithm using the approximate message passing principle to resolve the trilinear inference problem. Meanwhile, we present an analytical framework to characterize the theoretical performance bound of the proposed approach in the large-system limit via the replica method developed in statistical physics. Extensive simulation results demonstrate the effectiveness of the proposed semi-blind cascaded channel estimation algorithm.
Classification of Pedagogical content using conventional machine learning and deep learning model
Venue: arXiv cs.AI 2021
Year: 2021

The advent of the Internet and a large number of digital technologies has brought with it many different challenges. A large amount of data is found on the web, which in most cases is unstructured and unorganized, and this contributes to the fact that the use and manipulation of this data is quite a difficult process. Due to this fact, the usage of different machine and deep learning techniques for Text Classification has gained its importance, which improved this discipline and made it more interesting for scientists and researchers for further study. This paper aims to classify the pedagogical content using two different models, the K-Nearest Neighbor (KNN) from the conventional models and the Long short-term memory (LSTM) recurrent neural network from the deep learning models. The result indicates that the accuracy of classifying the pedagogical content reaches 92.52 % using KNN model and 87.71 % using LSTM model.
Dissonance Between Human and Machine Understanding
Venue: arXiv cs.AI 2021
Year: 2021

Complex machine learning models are deployed in several critical domains including healthcare and autonomous vehicles nowadays, albeit as functional black boxes. Consequently, there has been a recent surge in interpreting decisions of such complex models in order to explain their actions to humans. Models that correspond to human interpretation of a task are more desirable in certain contexts and can help attribute liability, build trust, expose biases and in turn build better models. It is, therefore, crucial to understand how and which models conform to human understanding of tasks. In this paper, we present a large-scale crowdsourcing study that reveals and quantifies the dissonance between human and machine understanding, through the lens of an image classification task. In particular, we seek to answer the following questions: Which (well-performing) complex ML models are closer to humans in their use of features to make accurate predictions? How does task difficulty affect the feature selection capability of machines in comparison to humans? Are humans consistently better at selecting features that make image recognition more accurate? Our findings have important implications on human-machine collaboration, considering that a long term goal in the field of artificial intelligence is to make machines capable of learning and reasoning like humans.
SOSD-Net: Joint Semantic Object Segmentation and Depth Estimation from Monocular images
Venue: arXiv cs.CV 2021
Year: 2021

Depth estimation and semantic segmentation play essential roles in scene understanding. The state-of-the-art methods employ multi-task learning to simultaneously learn models for these two tasks at the pixel-wise level. They usually focus on sharing the common features or stitching feature maps from the corresponding branches. However, these methods lack in-depth consideration on the correlation of the geometric cues and the scene parsing. In this paper, we first introduce the concept of semantic objectness to exploit the geometric relationship of these two tasks through an analysis of the imaging process, then propose a Semantic Object Segmentation and Depth Estimation Network (SOSD-Net) based on the objectness assumption. To the best of our knowledge, SOSD-Net is the first network that exploits the geometry constraint for simultaneous monocular depth estimation and semantic segmentation. In addition, considering the mutual implicit relationship between these two tasks, we exploit the iterative idea from the expectation-maximization algorithm to train the proposed network more effectively. Extensive experimental results on the Cityscapes and NYU v2 dataset are presented to demonstrate the superior performance of the proposed approach.
Fast Convergence of DETR with Spatially Modulated Co-Attention
Venue: arXiv cs.CV 2021
Year: 2021

The recently proposed Detection Transformer (DETR) model successfully applies Transformer to objects detection and achieves comparable performance with two-stage object detection frameworks, such as Faster-RCNN. However, DETR suffers from its slow convergence. Training DETR \cite{carion2020end} from scratch needs 500 epochs to achieve a high accuracy. To accelerate its convergence, we propose a simple yet effective scheme for improving the DETR framework, namely Spatially Modulated Co-Attention (SMCA) mechanism. The core idea of SMCA is to conduct regression-aware co-attention in DETR by constraining co-attention responses to be high near initially estimated bounding box locations. Our proposed SMCA increases DETR's convergence speed by replacing the original co-attention mechanism in the decoder while keeping other operations in DETR unchanged. Furthermore, by integrating multi-head and scale-selection attention designs into SMCA, our fully-fledged SMCA can achieve better performance compared to DETR with a dilated convolution-based backbone (45.6 mAP at 108 epochs vs. 43.3 mAP at 500 epochs). We perform extensive ablation studies on COCO dataset to validate the effectiveness of the proposed SMCA.
Wide Color Gamut Image Content Characterization: Method, Evaluation, and Applications
Venue: arXiv cs.MM 2021
Year: 2021

In this paper, we propose a novel framework to characterize a wide color gamut image content based on perceived quality due to the processes that change color gamut, and demonstrate two practical use cases where the framework can be applied. We first introduce the main framework and implementation details. Then, we provide analysis for understanding of existing wide color gamut datasets with quantitative characterization criteria on their characteristics, where four criteria, i.e., coverage, total coverage, uniformity, and total uniformity, are proposed. Finally, the framework is applied to content selection in a gamut mapping evaluation scenario in order to enhance reliability and robustness of the evaluation results. As a result, the framework fulfils content characterization for studies where quality of experience of wide color gamut stimuli is involved.
PICA: A Pixel Correlation-based Attentional Black-box Adversarial Attack
Venue: arXiv cs.CV 2021
Year: 2021

The studies on black-box adversarial attacks have become increasingly prevalent due to the intractable acquisition of the structural knowledge of deep neural networks (DNNs). However, the performance of emerging attacks is negatively impacted when fooling DNNs tailored for high-resolution images. One of the explanations is that these methods usually focus on attacking the entire image, regardless of its spatial semantic information, and thereby encounter the notorious curse of dimensionality. To this end, we propose a pixel correlation-based attentional black-box adversarial attack, termed as PICA. Firstly, we take only one of every two neighboring pixels in the salient region as the target by leveraging the attentional mechanism and pixel correlation of images, such that the dimension of the black-box attack reduces. After that, a general multiobjective evolutionary algorithm is employed to traverse the reduced pixels and generate perturbations that are imperceptible by the human vision. Extensive experimental results have verified the effectiveness of the proposed PICA on the ImageNet dataset. More importantly, PICA is computationally more efficient to generate high-resolution adversarial examples compared with the existing black-box attacks.
Local Complexity of Polygons
Venue: arXiv cs.CG 2021
Year: 2021

Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underlying polygonal region has low local complexity. One obstacle to make this intuition rigorous, is the lack of a formal definition of local complexity. Here, we give two possible definitions and show how they are related in a combinatorial sense. We say that a polygon $P$ has point visibility width $w=pvw$, if there is no point $q\in P$ that sees more than $w$ reflex vertices. We say that a polygon $P$ has chord visibility width $w=cvw $, if there is no chord $c=\textrm{seg}(a,b)\subset P$ that sees more than w reflex vertices. We show that \[ cvw \leq pvw ^{O( pvw )},\] for any simple polygon. Furthermore, we show that there exists a simple polygon with \[ cvw \geq 2^{Ω( pvw )}.\]
Single-RF Multi-User Communication Through Reconfigurable Intelligent Surfaces: An Information-Theoretic Analysis
Venue: arXiv cs.IT 2021
Year: 2021

Reconfigurable intelligent surfaces (RISs) are typically used in multi-user systems to mitigate interference among active transmitters. In contrast, this paper studies a setting with a conventional active encoder as well as a passive encoder that modulates the reflection pattern of the RIS. The RIS hence serves the dual purpose of improving the rate of the active encoder and of enabling communication from the second encoder. The capacity region is characterized, and information-theoretic insights regarding the trade-offs between the rates of the two encoders are derived by focusing on the high- and low-power regimes.
Self-Organizing Intelligent Matter: A blueprint for an AI generating algorithm
Venue: arXiv cs.NE 2021
Year: 2021

We propose an artificial life framework aimed at facilitating the emergence of intelligent organisms. In this framework there is no explicit notion of an agent: instead there is an environment made of atomic elements. These elements contain neural operations and interact through exchanges of information and through physics-like rules contained in the environment. We discuss how an evolutionary process can lead to the emergence of different organisms made of many such atomic elements which can coexist and thrive in the environment. We discuss how this forms the basis of a general AI generating algorithm. We provide a simplified implementation of such system and discuss what advances need to be made to scale it up further.