OpenRaiser/Intern-Atlas huggingface dataset:
Distributional Soft Actor-Critic: Off-Policy Reinforcement Learning for Addressing Value Estimation Errors
Venue: arXiv cs.LG 2021
Year: 2021

In reinforcement learning (RL), function approximation errors are known to easily lead to the Q-value overestimations, thus greatly reducing policy performance. This paper presents a distributional soft actor-critic (DSAC) algorithm, which is an off-policy RL method for continuous control setting, to improve the policy performance by mitigating Q-value overestimations. We first discover in theory that learning a distribution function of state-action returns can effectively mitigate Q-value overestimations because it is capable of adaptively adjusting the update stepsize of the Q-value function. Then, a distributional soft policy iteration (DSPI) framework is developed by embedding the return distribution function into maximum entropy RL. Finally, we present a deep off-policy actor-critic variant of DSPI, called DSAC, which directly learns a continuous return distribution by keeping the variance of the state-action returns within a reasonable range to address exploding and vanishing gradient problems. We evaluate DSAC on the suite of MuJoCo continuous control tasks, achieving the state-of-the-art performance.
Monotone recursive types and recursive data representations in Cedille
Venue: arXiv cs.PL 2021
Year: 2021

Guided by Tarksi's fixpoint theorem in order theory, we show how to derive monotone recursive types with constant-time roll and unroll operations within Cedille, an impredicative, constructive, and logically consistent pure typed lambda calculus. This derivation takes place within the preorder on Cedille types induced by type inclusions, a notion which is expressible within the theory itself. As applications, we use monotone recursive types to generically derive two recursive representations of data in lambda calculus, the Parigot and Scott encoding. For both encodings, we prove induction and examine the computational and extensional properties of their destructor, iterator, and primitive recursor in Cedille. For our Scott encoding in particular, we translate into Cedille a construction due to Lepigre and Raffalli that equips Scott naturals with primitive recursion, then extend this construction to derive a generic induction principle. This allows us to give efficient and provably unique (up to function extensionality) solutions for the iteration and primitive recursion schemes for Scott-encoded data.
Rate-Splitting Multiple Access for Multi-antenna Downlink Communication Systems: Spectral and Energy Efficiency Tradeoff
Venue: arXiv cs.IT 2021
Year: 2021

Rate-splitting (RS) has recently been recognized as a promising physical-layer technique for multi-antenna broadcast channels (BC). Due to its ability to partially decode the interference and partially treat the remaining interference as noise, RS is an enabler for a powerful multiple access, namely rate-splitting multiple access (RSMA), that has been shown to achieve higher spectral efficiency (SE) and energy efficiency (EE) than both space division multiple access (SDMA) and non-orthogonal multiple access (NOMA) in a wide range of user deployments and network loads. As SE maximization and EE maximization are two conflicting objectives, the study of the tradeoff between the two criteria is of particular interest. In this work, we address the SE-EE tradeoff by studying the joint SE and EE maximization problem of RSMA in multiple input single output (MISO) BC with rate-dependent circuit power consumption at the transmitter. To tackle the challenges coming from multiple objective functions and rate-dependent circuit power consumption, we first propose two methods to transform the original problem into a single-objective problem, namely, weighted-sum method and weighted-power method. A successive convex approximation (SCA)-based algorithm is then proposed to jointly optimize the precoders and RS message split of the transformed problem. Numerical results show that our algorithm converges much faster than existing algorithms. In addition, the performance of RS is superior to or equal to non-RS strategy in terms of both SE and EE and their tradeoff.
Two Applications of Deep Learning in the Physical Layer of Communication Systems
Venue: arXiv cs.IT 2021
Year: 2021

Deep learning has proved itself to be a powerful tool to develop data-driven signal processing algorithms for challenging engineering problems. By learning the key features and characteristics of the input signals, instead of requiring a human to first identify and model them, learned algorithms can beat many man-made algorithms. In particular, deep neural networks are capable of learning the complicated features in nature-made signals, such as photos and audio recordings, and use them for classification and decision making. The situation is rather different in communication systems, where the information signals are man-made, the propagation channels are relatively easy to model, and we know how to operate close to the Shannon capacity limits. Does this mean that there is no role for deep learning in the development of future communication systems?
A Two-step Calibration Method for Unfocused Light Field Camera Based on Projection Model Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Accurately calibrating light field camera is essential to its applications. Rapid progress has been made in this area in the past decades. In this paper, detailed analysis was first performed towards the state of the art projection models for calibration which were further interpreted in three representations, including the correspondence between rays and pixels, 3D physical points and pixels and between 3D physical points and 3D signal structure of the captured light field. Based on the analysis, parameters in the projection model were grouped into direction parameter set and depth parameter set. A two-step calibration method was then proposed with each step dealing with each set of parameters. The proposed method is able to reuse traditional camera calibration methods for the direction parameter set. A simply raw image-based calibration of depth parameter set was further proposed. Systematic validations were conducted to evaluate the performance of the proposed calibration method. Experimental results show that the accuracy and robustness of the proposed method outperforms its counterparts under various benchmark criteria.
CDGAN: Cyclic Discriminative Generative Adversarial Networks for Image-to-Image Transformation
Venue: arXiv cs.CV 2021
Year: 2021

Generative Adversarial Networks (GANs) have facilitated a new direction to tackle the image-to-image transformation problem. Different GANs use generator and discriminator networks with different losses in the objective function. Still there is a gap to fill in terms of both the quality of the generated images and close to the ground truth images. In this work, we introduce a new Image-to-Image Transformation network named Cyclic Discriminative Generative Adversarial Networks (CDGAN) that fills the above mentioned gaps. The proposed CDGAN generates high quality and more realistic images by incorporating the additional discriminator networks for cycled images in addition to the original architecture of the CycleGAN. The proposed CDGAN is tested over three image-to-image transformation datasets. The quantitative and qualitative results are analyzed and compared with the state-of-the-art methods. The proposed CDGAN method outperforms the state-of-the-art methods when compared over the three baseline Image-to-Image transformation datasets. The code is available at https://github.com/KishanKancharagunta/CDGAN.
Show, Recall, and Tell: Image Captioning with Recall Mechanism
Venue: arXiv cs.CV 2021
Year: 2021

Generating natural and accurate descriptions in image cap-tioning has always been a challenge. In this paper, we pro-pose a novel recall mechanism to imitate the way human con-duct captioning. There are three parts in our recall mecha-nism : recall unit, semantic guide (SG) and recalled-wordslot (RWS). Recall unit is a text-retrieval module designedto retrieve recalled words for images. SG and RWS are de-signed for the best use of recalled words. SG branch cangenerate a recalled context, which can guide the process ofgenerating caption. RWS branch is responsible for copyingrecalled words to the caption. Inspired by pointing mecha-nism in text summarization, we adopt a soft switch to balancethe generated-word probabilities between SG and RWS. Inthe CIDEr optimization step, we also introduce an individualrecalled-word reward (WR) to boost training. Our proposedmethods (SG+RWS+WR) achieve BLEU-4 / CIDEr / SPICEscores of 36.6 / 116.9 / 21.3 with cross-entropy loss and 38.7 /129.1 / 22.4 with CIDEr optimization on MSCOCO Karpathytest split, which surpass the results of other state-of-the-artmethods.
Strong-Separation Logic
Venue: arXiv cs.LO 2021
Year: 2021

Most automated verifiers for separation logic target the symbolic-heap fragment, disallowing both the magic-wand operator and the application of classical Boolean operators to spatial formulas. This is not surprising, as support for the magic wand quickly leads to undecidability, especially when combined with inductive predicates for reasoning about data structures. To circumvent these undecidability results, we propose to assign a more restrictive semantics to the separating conjunction. We argue that the resulting logic, strong-separation logic, can be used for compositional program verification and bi-abductive static analysis just like "standard" separation logic, while remaining decidable even in the presence of both the magic wand and the list-segment predicate -- a combination of features that leads to undecidability assuming the standard semantics.
An Interdisciplinary Guideline for the Production of Videos and Vision Videos by Software Professionals
Venue: arXiv cs.SE 2021
Year: 2021

Background and Motivation: In recent years, the topic of applying videos in requirements engineering has been discussed and its contributions are of interesting potential. In the last 35 years, several researchers proposed approaches for applying videos in requirements engineering due to their communication richness and effectiveness. However, these approaches mainly use videos but omit the details about how to produce them. This lack of guidance is one crucial reason why videos are not an established documentation option for successful requirements communication and thus shared understanding. Software professionals are not directors and thus they do not necessarily know what constitutes a good video in general and for an existing approach. Therefore, this lack of knowledge and skills on how to produce and use videos for visual communication impedes the application of videos by software professionals in requirements engineering. How to Create Effective Videos and Vision Videos?: This technical report addresses this lack of knowledge and skills by software professionals. We provide two guidelines that can be used as checklists to avoid frequent flaws in the production and use of videos respectively vision videos. Software professionals without special training should be able to follow these guidelines to achieve the basic capabilities to produce (vision) videos that are accepted by their stakeholders. These guidelines represent a core set of those capabilities in the preproduction, shooting, postproduction, and viewing of (vision) videos. We do not strive for perfection in any of these capabilities, .e.g., technical handling of video equipment, storytelling, or video editing. Instead, these guidelines support all steps of the (vision) video production and use process to a balanced way.
Infinitary Action Logic with Exponentiation
Venue: arXiv cs.LO 2021
Year: 2021

We introduce infinitary action logic with exponentiation -- that is, the multiplicative-additive Lambek calculus extended with Kleene star and with a family of subexponential modalities, which allows some of the structural rules (contraction, weakening, permutation). The logic is presented in the form of an infinitary sequent calculus. We prove cut elimination and, in the case where at least one subexponential allows non-local contraction, establish exact complexity boundaries in two senses. First, we show that the derivability problem for this logic is $Π_1^1$-complete. Second, we show that the closure ordinal of its derivability operator is $ω_1^{\mathrm{CK}}$. In the case where no subexponential allows contraction, we show that complexity is the same as for infinitary action logic itself. Namely, the derivability problem in this case is $Π^0_1$-complete and the closure ordinal is not greater than $ω^ω$.
Nonlinear Blockchain Scalability: a Game-Theoretic Perspective
Venue: arXiv cs.CR 2021
Year: 2021

Recent advances in the blockchain research have been made in two important directions. One is refined resilience analysis utilizing game theory to study the consequences of selfish behaviors of users (miners), and the other is the extension from a linear (chain) structure to a non-linear (graphical) structure for performance improvements, such as IOTA and Graphcoin. The first question that comes to people's minds is what improvements that a blockchain system would see by leveraging these new advances. In this paper, we consider three major metrics for a blockchain system: full verification, scalability, and finality-duration. We { establish a formal framework and} prove that no blockchain system can achieve full verification, high scalability, and low finality-duration simultaneously. We observe that classical blockchain systems like Bitcoin achieves full verification and low finality-duration, Harmony and Ethereum 2.0 achieve low finality-duration and high scalability. As a complementary, we design a non-linear blockchain system that achieves full verification and scalability. We also establish, for the first time, the trade-off between scalability and finality-duration.
Learning Distributional Programs for Relational Autocompletion
Venue: arXiv cs.AI 2021
Year: 2021

Relational autocompletion is the problem of automatically filling out some missing values in multi-relational data. We tackle this problem within the probabilistic logic programming framework of Distributional Clauses (DC), which supports both discrete and continuous probability distributions. Within this framework, we introduce DiceML { an approach to learn both the structure and the parameters of DC programs from relational data (with possibly missing data). To realize this, DiceML integrates statistical modeling and distributional clauses with rule learning. The distinguishing features of DiceML are that it 1) tackles autocompletion in relational data, 2) learns distributional clauses extended with statistical models, 3) deals with both discrete and continuous distributions, 4) can exploit background knowledge, and 5) uses an expectation-maximization based algorithm to cope with missing data. The empirical results show the promise of the approach, even when there is missing data.
Active Learning for Entity Alignment
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we propose a novel framework for the labeling of entity alignments in knowledge graph datasets. Different strategies to select informative instances for the human labeler build the core of our framework. We illustrate how the labeling of entity alignments is different from assigning class labels to single instances and how these differences affect the labeling efficiency. Based on these considerations we propose and evaluate different active and passive learning strategies. One of our main findings is that passive learning approaches, which can be efficiently precomputed and deployed more easily, achieve performance comparable to the active learning strategies.
Semantic Sensitive TF-IDF to Determine Word Relevance in Documents
Venue: arXiv cs.IR 2021
Year: 2021

Keyword extraction has received an increasing attention as an important research topic which can lead to have advancements in diverse applications such as document context categorization, text indexing and document classification. In this paper we propose STF-IDF, a novel semantic method based on TF-IDF, for scoring word importance of informal documents in a corpus. A set of nearly four million documents from health-care social media was collected and was trained in order to draw semantic model and to find the word embeddings. Then, the features of semantic space were utilized to rearrange the original TF-IDF scores through an iterative solution so as to improve the moderate performance of this algorithm on informal texts. After testing the proposed method with 200 randomly chosen documents, our method managed to decrease the TF-IDF mean error rate by a factor of 50% and reaching the mean error of 13.7%, as opposed to 27.2% of the original TF-IDF.
On the All-Or-Nothing Behavior of Bernoulli Group Testing
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study the problem of non-adaptive group testing, in which one seeks to identify which items are defective given a set of suitably-designed tests whose outcomes indicate whether or not at least one defective item was included in the test. The most widespread recovery criterion seeks to exactly recover the entire defective set, and relaxed criteria such as approximate recovery and list decoding have also been considered. In this paper, we study the fundamental limits of group testing under the significantly relaxed {\em weak recovery} criterion, which only seeks to identify a small fraction (e.g., $0.01$) of the defective items. Given the near-optimality of i.i.d.~Bernoulli testing for exact recovery in sufficiently sparse scaling regimes, it is natural to ask whether this design additionally succeeds with much fewer tests under weak recovery. Our main negative result shows that this is not the case, and in fact, under i.i.d.~Bernoulli random testing in the sufficiently sparse regime, an {\em all-or-nothing} phenomenon occurs: When the number of tests is slightly below a threshold, weak recovery is impossible, whereas when the number of tests is slightly above the same threshold, high-probability exact recovery is possible. In establishing this result, we additionally prove similar negative results under Bernoulli designs for the weak detection problem (distinguishing between the group testing model vs.~completely random outcomes) and the problem of identifying a single item that is definitely defective. On the positive side, we show that all three relaxed recovery criteria can be attained using considerably fewer tests under suitably-chosen non-Bernoulli designs.
A CNN With Multi-scale Convolution for Hyperspectral Image Classification using Target-Pixel-Orientation scheme
Venue: arXiv cs.CV 2021
Year: 2021

Recently, CNN is a popular choice to handle the hyperspectral image classification challenges. In spite of having such large spectral information in Hyper-Spectral Image(s) (HSI), it creates a curse of dimensionality. Also, large spatial variability of spectral signature adds more difficulty in classification problem. Additionally, training a CNN in the end to end fashion with scarced training examples is another challenging and interesting problem. In this paper, a novel target-patch-orientation method is proposed to train a CNN based network. Also, we have introduced a hybrid of 3D-CNN and 2D-CNN based network architecture to implement band reduction and feature extraction methods, respectively. Experimental results show that our method outperforms the accuracies reported in the existing state of the art methods.
Goal-directed graph construction using reinforcement learning
Venue: arXiv cs.LG 2021
Year: 2021

Graphs can be used to represent and reason about systems and a variety of metrics have been devised to quantify their global characteristics. However, little is currently known about how to construct a graph or improve an existing one given a target objective. In this work, we formulate the construction of a graph as a decision-making process in which a central agent creates topologies by trial and error and receives rewards proportional to the value of the target objective. By means of this conceptual framework, we propose an algorithm based on reinforcement learning and graph neural networks to learn graph construction and improvement strategies. Our core case study focuses on robustness to failures and attacks, a property relevant for the infrastructure and communication networks that power modern society. Experiments on synthetic and real-world graphs show that this approach can outperform existing methods while being cheaper to evaluate. It also allows generalization to out-of-sample graphs, as well as to larger out-of-distribution graphs in some cases. The approach is applicable to the optimization of other global structural properties of graphs.
STRIPS Action Discovery
Venue: arXiv cs.AI 2021
Year: 2021

The problem of specifying high-level knowledge bases for planning becomes a hard task in realistic environments. This knowledge is usually handcrafted and is hard to keep updated, even for system experts. Recent approaches have shown the success of classical planning at synthesizing action models even when all intermediate states are missing. These approaches can synthesize action schemas in Planning Domain Definition Language (PDDL) from a set of execution traces each consisting, at least, of an initial and final state. In this paper, we propose a new algorithm to unsupervisedly synthesize STRIPS action models with a classical planner when action signatures are unknown. In addition, we contribute with a compilation to classical planning that mitigates the problem of learning static predicates in the action model preconditions, exploits the capabilities of SAT planners with parallel encodings to compute action schemas and validate all instances. Our system is flexible in that it supports the inclusion of partial input information that may speed up the search. We show through several experiments how learned action models generalize over unseen planning instances.
A new 1.375-approximation algorithm for Sorting By Transpositions
Venue: arXiv cs.DS 2021
Year: 2021

In genome rearrangements, the mutational event transposition swaps two adjacent blocks of genes in one chromosome. The Transposition Distance Problem (TDP) aims to find the minimum number of transpositions required to transform one chromosome into another, both represented as permutations. The TDP can be reduced to the problem of Sorting by Transpositions (SBT). SBT is $\mathcal{NP}$-hard and the best approximation algorithm with a $1.375$ ratio was proposed by Elias and Hartman. Their algorithm employs simplification, a technique used to transform an input permutation $π$ into a simple permutation $\hatπ$, presumably easier to handle with. The permutation $\hatπ$ is obtained by inserting new symbols into $π$ in a way that the lower bound of the transposition distance of $π$ is kept on $\hatπ$. The simplification is guaranteed to keep the lower bound, not the transposition distance. In this paper, we first show that the algorithm of Elias and Hartman (EH algorithm) may require one extra transposition above the approximation ratio of $1.375$, depending on how the input permutation is simplified. Next, using an algebraic approach, we propose a new upper bound for the transposition distance and a new $1.375$-approximation algorithm to solve SBT skipping simplification and ensuring the approximation ratio of $1.375$ for all $S_n$. We implemented our algorithm and EH's. Regarding the implementation of the EH algorithm, two issues needed to be fixed. We tested both algorithms against all permutations of size $n$, $2\leq n \leq 12$. The results show that the EH algorithm exceeds the approximation ratio of $1.375$ for permutations with a size greater than $7$. Finally, we investigate the performance of both implementations on longer permutations of maximum length $500$.