OpenRaiser/Intern-Atlas huggingface dataset:
Neural Feature Learning From Relational Database
Venue: arXiv cs.AI 2019
Year: 2019

Feature engineering is one of the most important but most tedious tasks in data science. This work studies automation of feature learning from relational database. We first prove theoretically that finding the optimal features from relational data for predictive tasks is NP-hard. We propose an efficient rule-based approach based on heuristics and a deep neural network to automatically learn appropriate features from relational data. We benchmark our approaches in ensembles in past Kaggle competitions. Our new approach wins late medals and beats the state-of-the-art solutions with significant margins. To the best of our knowledge, this is the first time an automated data science system could win medals in Kaggle competitions with complex relational database.
A formal framework for deliberated judgment
Venue: arXiv cs.AI 2019
Year: 2019

While the philosophical literature has extensively studied how decisions relate to arguments, reasons and justifications, decision theory almost entirely ignores the latter notions and rather focuses on preference and belief. In this article, we argue that decision theory can largely benefit from explicitly taking into account the stance that decision-makers take towards arguments and counter-arguments. To that end, we elaborate a formal framework aiming to integrate the role of arguments and argumentation in decision theory and decision aid. We start from a decision situation, where an individual requests decision support. In this context, we formally define, as a commendable basis for decision-aid, this individual's deliberated judgment, popularized by Rawls. We explain how models of deliberated judgment can be validated empirically. We then identify conditions upon which the existence of a valid model can be taken for granted, and analyze how these conditions can be relaxed. We then explore the significance of our proposed framework for decision aiding practice. We argue that our concept of deliberated judgment owes its normative credentials both to its normative foundations (the idea of rationality based on arguments) and to its reference to empirical reality (the stance that real, empirical individuals hold towards arguments and counter-arguments, on due reflection). We then highlight that our framework opens promising avenues for future research involving both philosophical and decision theoretic approaches, as well as empirical implementations.
A taxonomy of video lecture styles
Venue: arXiv cs.CY 2019
Year: 2019

Many educational organizations are employing instructional video in their pedagogy, but there is limited understanding of the possible presentation styles. In practice, the presentation style of video lectures ranges from a direct recording of classroom teaching with a stationary camera and screencasts with voice-over, up to highly elaborate video post-production. Previous work evaluated the effectiveness of several presentation styles, but there has not been any consistent taxonomy, which would have made comparisons and meta-analyses possible. In this article, we surveyed the research literature and we examined contemporary video-based courses, which have been produced by diverse educational organizations and teachers across various academic disciplines. We organized video lectures in two dimensions according to the level of human presence and according to the type of instructional media. In addition to organizing existing video lectures in a comprehensive way, the proposed taxonomy offers a design space that facilitates the choice of a suitable presentation style, as well as the preparation of new ones.
Adaptive parallelism with RMI: Idle high-performance computing resources can be completely avoided
Venue: arXiv cs.DC 2019
Year: 2019

In practice, standard scheduling of parallel computing jobs almost always leaves significant portions of the available hardware unused, even with many jobs still waiting in the queue. The simple reason is that the resource requests of these waiting jobs are fixed and do not match the available, unused resources. However, with alternative but existing and well-established techniques it is possible to achieve a fully automated, adaptive parallelism that does not need pre-set, fixed resources. Here, we demonstrate that such an adaptively parallel program can indeed fill in all such scheduling gaps, even in real-life situations on large supercomputers.
Stable gonality is computable
Venue: arXiv cs.DM 2019
Year: 2019

Stable gonality is a multigraph parameter that measures the complexity of a graph. It is defined using maps to trees. Those maps, in some sense, divide the edges equally over the edges of the tree; stable gonality asks for the map with the minimum number of edges mapped to each edge of the tree. This parameter is related to treewidth, but unlike treewidth, it distinguishes multigraphs from their underlying simple graphs. Stable gonality is relevant for problems in number theory. In this paper, we show that deciding whether the stable gonality of a given graph is at most a given integer $k$ belongs to the class NP, and we give an algorithm that computes the stable gonality of a graph in $O((1.33n)^nm^m \text{poly}(n,m))$ time.
CaosDB - Research Data Management for Complex, Changing, and Automated Research Workflows
Venue: arXiv cs.DB 2019
Year: 2019

Here we present CaosDB, a Research Data Management System (RDMS) designed to ensure seamless integration of inhomogeneous data sources and repositories of legacy data. Its primary purpose is the management of data from biomedical sciences, both from simulations and experiments during the complete research data lifecycle. An RDMS for this domain faces particular challenges: Research data arise in huge amounts, from a wide variety of sources, and traverse a highly branched path of further processing. To be accepted by its users, an RDMS must be built around workflows of the scientists and practices and thus support changes in workflow and data structure. Nevertheless it should encourage and support the development and observation of standards and furthermore facilitate the automation of data acquisition and processing with specialized software. The storage data model of an RDMS must reflect these complexities with appropriate semantics and ontologies while offering simple methods for finding, retrieving, and understanding relevant data. We show how CaosDB responds to these challenges and give an overview of the CaosDB Server, its data model and its easy-to-learn CaosDB Query Language. We briefly discuss the status of the implementation, how we currently use CaosDB, and how we plan to use and extend it.
Blockchain moderated by empty blocks to reduce the energetic impact of crypto-moneys
Venue: arXiv cs.CR 2019
Year: 2019

While cryptocurrencies and blockchain applications continue to gain popularity, their energy cost is evidently becoming unsustainable. In most instances, the main cost comes from the required amount of energy for the Proof-of-Work, and this cost is inherent to the design. In addition, useless costs from discarded work (e.g., the so-called Forks) and lack of scalability (in number of users and in rapid transactions) limit their practical effectiveness. In this paper, we present an innovative scheme which eliminates the nonce and thus the burden of the Proof-of-Work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. We prove that our scheme guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, thus by making the use of nonce-based techniques unnecessary, achieves scalability without the cost of consuming a large volume of energy. The technique used in the proof of our scheme is based on the analogy of the analysis of a green leader election. The additional difference with Proof-of-Work schemes (beyond the suppression of the nonce field that is triggering most of the waste), is the introduction of (what we denote as) "empty blocks" which aim are to call regular blocks following a staircase set of values. Our scheme reduces the risk of Forks and provides tunable scalability for the number of users and the speed of block generation. We also prove using game theoretical analysis that our scheme is resilient to unfair competitive investments (e.g., "51 percent" attack) and block nursing.
Logically-Constrained Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

We present the first model-free Reinforcement Learning (RL) algorithm to synthesise policies for an unknown Markov Decision Process (MDP), such that a linear time property is satisfied. The given temporal property is converted into a Limit Deterministic Buchi Automaton (LDBA) and a robust reward function is defined over the state-action pairs of the MDP according to the resulting LDBA. With this reward function, the policy synthesis procedure is "constrained" by the given specification. These constraints guide the MDP exploration so as to minimize the solution time by only considering the portion of the MDP that is relevant to satisfaction of the LTL property. This improves performance and scalability of the proposed method by avoiding an exhaustive update over the whole state space while the efficiency of standard methods such as dynamic programming is hindered by excessive memory requirements, caused by the need to store a full-model in memory. Additionally, we show that the RL procedure sets up a local value iteration method to efficiently calculate the maximum probability of satisfying the given property, at any given state of the MDP. We prove that our algorithm is guaranteed to find a policy whose traces probabilistically satisfy the LTL property if such a policy exists, and additionally we show that our method produces reasonable control policies even when the LTL property cannot be satisfied. The performance of the algorithm is evaluated via a set of numerical examples. We observe an improvement of one order of magnitude in the number of iterations required for the synthesis compared to existing approaches.
Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
Venue: arXiv cs.IT 2019
Year: 2019

This paper proposes a constrained stochastic successive convex approximation (CSSCA) algorithm to find a stationary point for a general non-convex stochastic optimization problem, whose objective and constraint functions are non-convex and involve expectations over random states. Most existing methods for non-convex stochastic optimization, such as the stochastic (average) gradient and stochastic majorization-minimization, only consider minimizing a stochastic non-convex objective over a deterministic convex set. The proposed CSSCA algorithm can also handle stochastic non-convex constraints in optimization problems, and it opens the way to solving more challenging optimization problems that occur in many applications. The algorithm is based on solving a sequence of convex objective/feasibility optimization problems obtained by replacing the objective/constraint functions in the original problems with some convex surrogate functions. The CSSCA algorithm allows a wide class of surrogate functions and thus provides many freedoms to design good surrogate functions for specific applications. Moreover, it also facilitates parallel implementation for solving large scale stochastic optimization problems, which arise naturally in today's signal processing such as machine learning and big data analysis. We establish the convergence of CSSCA algorithm with a feasible initial point, and customize the algorithmic framework to solve several important application problems. Simulations show that the CSSCA algorithm can achieve superior performance over existing solutions.
On Optimal Scheduling for Joint Spatial Division and Multiplexing Approach in FDD Massive MIMO
Venue: arXiv cs.IT 2019
Year: 2019

Massive MIMO is widely considered as a key enabler of the next generation 5G networks. With a large number of antennas at the Base Station, both spectral and energy efficiencies can be enhanced. Unfortunately, the downlink channel estimation overhead scales linearly with the number of antennas. This burden is easily mitigated in TDD systems by the use of the channel reciprocity property. However, this is unfeasible for FDD systems and the method of two-stage beamforming was therefore developed to reduce the amount of channel state information feedback. The performance of this scheme being highly dependent on the users grouping and scheduling mechanims, we introduce in this paper a new similarity measure coupled with a novel clustering procedure to achieve the appropriate users grouping. We also proceed to formulate the optimal users scheduling policy in JSDM and prove that it is NP-hard. This result is of paramount importance since it suggests that, unless P=NP, there are no polynomial time algorithms that solve the general scheduling problem to global optimality and the use of sub-optimal scheduling strategies is more realistic in practice. We therefore use graph theory to develop a sub-optimal users scheduling scheme that runs in polynomial time and outperforms the scheduling schemes previously introduced in the literature for JSDM in both sum-rate and throughput fairness.
Distributed Computing with Heterogeneous Communication Constraints: The Worst-Case Computation Load and Proof by Contradiction
Venue: arXiv cs.IT 2019
Year: 2019

We consider a distributed computing framework where the distributed nodes have different communication capabilities, motivated by the heterogeneous networks in data centers and mobile edge computing systems. Following the structure of MapReduce, this framework consists of Map computation phase, Shuffle phase, and Reduce computation phase. The Shuffle phase allows distributed nodes to exchange intermediate values, in the presence of heterogeneous communication bottlenecks for different nodes (heterogeneous communication load constraints). For this setting, we characterize the minimum total computation load and the minimum worst-case computation load in some cases, under the heterogeneous communication load constraints. While the total computation load depends on the sum of the computation loads of all the nodes, the worst-case computation load depends on the computation load of a node with the heaviest job. We show an interesting insight that, for some cases, there is a tradeoff between the minimum total computation load and the minimum worst-case computation load, in the sense that both cannot be achieved at the same time. The achievability schemes are proposed with careful design on the file assignment and the data shuffling. Beyond the cut-set bound, a novel converse is proposed using the proof by contradiction. For the general case, we identify two extreme regimes in which both the scheme with coding and the scheme without coding are optimal, respectively.
When Good Components Go Bad: Formally Secure Compilation Despite Dynamic Compromise
Venue: arXiv cs.CR 2019
Year: 2019

We propose a new formal criterion for evaluating secure compilation schemes for unsafe languages, expressing end-to-end security guarantees for software components that may become compromised after encountering undefined behavior---for example, by accessing an array out of bounds. Our criterion is the first to model dynamic compromise in a system of mutually distrustful components with clearly specified privileges. It articulates how each component should be protected from all the others---in particular, from components that have encountered undefined behavior and become compromised. Each component receives secure compilation guarantees---in particular, its internal invariants are protected from compromised components---up to the point when this component itself becomes compromised, after which we assume an attacker can take complete control and use this component's privileges to attack other components. More precisely, a secure compilation chain must ensure that a dynamically compromised component cannot break the safety properties of the system at the target level any more than an arbitrary attacker-controlled component (with the same interface and privileges, but without undefined behaviors) already could at the source level. To illustrate the model, we construct a secure compilation chain for a small unsafe language with buffers, procedures, and components, targeting a simple abstract machine with built-in compartmentalization. We give a machine-checked proof in Coq that this compiler satisfies our secure compilation criterion. Finally, we show that the protection guarantees offered by the compartmentalized abstract machine can be achieved at the machine-code level using either software fault isolation or a tag-based reference monitor.
Incremental Control and Guidance of Hybrid Aircraft Applied to a Tailsitter UAV
Venue: arXiv cs.RO 2019
Year: 2019

Hybrid unmanned aircraft can significantly increase the potential of micro air vehicles, because they combine hovering capability with a wing for fast and efficient forward flight. However, these vehicles are very difficult to control, because their aerodynamics are hard to model and they are susceptible to wind gusts. This often leads to composite and complex controllers, with different modes for hover, transition and forward flight. In this paper, we propose incremental nonlinear dynamic inversion control for the attitude and position control. The result is a single, continuous controller, that is able to track the desired acceleration of the vehicle across the flight envelope. The proposed controller is implemented on the Cyclone hybrid UAV. Multiple outdoor experiments are performed, showing that unmodeled forces and moments are effectively compensated by the incremental control structure. Finally, we provide a comprehensive procedure for the implementation of the controller on other types of hybrid UAVs.
QoS-aware Dynamic Fog Service Provisioning
Venue: arXiv cs.NI 2019
Year: 2019

Recent advances in the areas of Internet of Things (IoT), Big Data, and Machine Learning have contributed to the rise of a growing number of complex applications. These applications will be data-intensive, delay-sensitive, and real-time as smart devices prevail more in our daily life. Ensuring Quality of Service (QoS) for delay-sensitive applications is a must, and fog computing is seen as one of the primary enablers for satisfying such tight QoS requirements, as it puts compute, storage, and networking resources closer to the user. In this paper, we first introduce FogPlan, a framework for QoS-aware Dynamic Fog Service Provisioning (QDFSP). QDFSP concerns the dynamic deployment of application services on fog nodes, or the release of application services that have previously been deployed on fog nodes, in order to meet low latency and QoS requirements of applications while minimizing cost. FogPlan framework is practical and operates with no assumptions and minimal information about IoT nodes. Next, we present a possible formulation (as an optimization problem) and two efficient greedy algorithms for addressing the QDFSP at one instance of time. Finally, the FogPlan framework is evaluated using a simulation based on real-world traffic traces.
Incorporating Literals into Knowledge Graph Embeddings
Venue: arXiv cs.AI 2019
Year: 2019

Knowledge graphs, on top of entities and their relationships, contain other important elements: literals. Literals encode interesting properties (e.g. the height) of entities that are not captured by links between entities alone. Most of the existing work on embedding (or latent feature) based knowledge graph analysis focuses mainly on the relations between entities. In this work, we study the effect of incorporating literal information into existing link prediction methods. Our approach, which we name LiteralE, is an extension that can be plugged into existing latent feature methods. LiteralE merges entity embeddings with their literal information using a learnable, parametrized function, such as a simple linear or nonlinear transformation, or a multilayer neural network. We extend several popular embedding models based on LiteralE and evaluate their performance on the task of link prediction. Despite its simplicity, LiteralE proves to be an effective way to incorporate literal information into existing embedding based methods, improving their performance on different standard datasets, which we augmented with their literals and provide as testbed for further research.
Multi-snapshot Newtonized Orthogonal Matching Pursuit for Line Spectrum Estimation with Multiple Measurement Vectors
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, multi-snapshot Newtonized orthogonal matching pursuit (MNOMP) algorithm is proposed to deal with the line spectrum estimation with multiple measurement vectors (MMVs). MNOMP has the low computation complexity and state-of-the-art performance advantage of NOMP, and also includes two key steps: Detecting a new sinusoid on an oversampled discrete Fourier transform (DFT) grid and refining the parameters of already detected sinusoids to avoid the problem of basis mismatch. We provide a stopping criterion based on the overestimating probability of the model order. In addition, the convergence of the proposed algorithm is also proved. Finally, numerical results are conducted to show that the performance of MNOMP benefits from MMVs, and the effectiveness of MNOMP when compared against the state-of-the-art algorithms in terms of frequency estimation accuracy and computation complexity.
Alleviating catastrophic forgetting using context-dependent gating and synaptic stabilization
Venue: arXiv cs.LG 2019
Year: 2019

Humans and most animals can learn new tasks without forgetting old ones. However, training artificial neural networks (ANNs) on new tasks typically cause it to forget previously learned tasks. This phenomenon is the result of "catastrophic forgetting", in which training an ANN disrupts connection weights that were important for solving previous tasks, degrading task performance. Several recent studies have proposed methods to stabilize connection weights of ANNs that are deemed most important for solving a task, which helps alleviate catastrophic forgetting. Here, drawing inspiration from algorithms that are believed to be implemented in vivo, we propose a complementary method: adding a context-dependent gating signal, such that only sparse, mostly non-overlapping patterns of units are active for any one task. This method is easy to implement, requires little computational overhead, and allows ANNs to maintain high performance across large numbers of sequentially presented tasks when combined with weight stabilization. This work provides another example of how neuroscience-inspired algorithms can benefit ANN design and capability.