OpenRaiser/Intern-Atlas huggingface dataset:
A new interval-based aggregation approach based on bagging and Interval Agreement Approach (IAA) in ensemble learning
Venue: arXiv cs.LG 2020
Year: 2020

The main aim in ensemble learning is using multiple individual classifiers outputs rather than one classifier output to aggregate them for more accurate classification. Generating an ensemble classifier generally is composed of three steps: selecting the base classifier, applying a sampling strategy to generate different individual classifiers and aggregation the classifiers outputs. This paper focuses on the classifiers outputs aggregation step and presents a new interval-based aggregation modeling using bagging resampling approach and Interval Agreement Approach (IAA) in ensemble learning. IAA is an interesting and practical aggregation approach in decision making which was introduced to combine decision makers opinions when they present their opinions by intervals. In this paper, in addition to implementing a new aggregation approach in ensemble learning, we designed some experiments to encourage researchers to use interval modeling in ensemble learning because it preserves more uncertainty and this leads to more accurate classification. For this purpose, we compared the results of implementing the proposed method to the majority vote as the most common and successful aggregation function in the literature on 10 medical data sets to show the better performance of the interval modeling and the proposed interval-based aggregation function in binary classification when it comes to ensemble learning. The results confirm the good performance of our proposed approach.
Reliability Aware Multiple Path Installation in Software Defined Networking
Venue: arXiv cs.NI 2020
Year: 2020

Being a state-of-the-art network, Software Defined Networking (SDN) decouples control and management planes from data plane of the forwarding devices by implementing both the control and management planes at logically centralized entity, called controller. This helps to make simple and easy both the network control and management. Failure of links occurs frequently in a computer network. To deal with the link failures, the existing approaches computes and installs multiple paths for a flow at the switches in SDN without considering the reliability value of the primary path. This incurs extra computation to compute multiple paths, and both increased computation time and traffic to install extra flow rules in the network. In this research work we propose a new approach that calculates the link reliability and then installs the number of multiple paths based on the reliability value of the primary path. More specifically, if a primary path has higher reliability then a smaller number of alternative paths should be installed. This shall decrease the path computational time and flow rule installation load at controller. Resultantly there shall be less flow rule entries in switch flow table which in turn will avoid the overflow of the flow table. Through simulation results, our proposed approach performs better as compared to the existing approach in term of computational overhead at controller, end-to-end delay for packet deliver and the traffic overhead for flow rule installation.
Deep Evolutionary Learning for Molecular Design
Venue: arXiv cs.NE 2020
Year: 2020

In this paper, we propose a deep evolutionary learning (DEL) process that integrates fragment-based deep generative model and multi-objective evolutionary computation for molecular design. Our approach enables (1) evolutionary operations in the latent space of the generative model, rather than the structural space, to generate novel promising molecular structures for the next evolutionary generation, and (2) generative model fine-tuning using newly generated high-quality samples. Thus, DEL implements a data-model co-evolution concept which improves both sample population and generative model learning. Experiments on two public datasets indicate that sample population obtained by DEL exhibits improved property distributions, and dominates samples generated by multi-objective Bayesian optimization algorithms.
Optimal Rate and Maximum Erasure Probability LDPC Codes in Binary Erasure Channel
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we present a novel way for solving the main problem of designing the capacity approaching irregular low-density parity-check (LDPC) code ensemble over binary erasure channel (BEC). The proposed method is much simpler, faster, accurate and practical than other methods. Our method does not use any relaxation or any approximate solution like previous works. Our method works and finds optimal answer for any given check node degree distribution. The proposed method was implemented and it works well in practice with polynomial time complexity. As a result, we represent some degree distributions that their rates are close to the capacity with maximum erasure probability and maximum code rate.
Innovation éducative en sciences de l'information
Venue: arXiv cs.CY 2021
Year: 2021

Concerning its development in the virtual classroom, the web 2.0 educational innovation means the use and the production of textbooks and the personalisation of the classnotes. The controversy, that is a precondition of awareness, organized around the assignment of knowledge to a central authority vs its grant to individuals who need it to share their plans with others, would meet the present dynamism of e-learning. To introduce these training strategies with scientific information in marine sciences, an online course was transformed into an opportunity for evaluating and living open access.
The length of a minimal synchronizing word and the Černy conjecture
Venue: arXiv cs.FL 2021
Year: 2021

A word w of letters on edges of underlying graph Gamma of deterministic finite automaton (DFA) is called the synchronizing word if w sends all states of the automaton to a unique state. J. Cerny discovered in 1964 a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)^2. The hypothesis, well known today as the Cerny conjecture, claims that it is also precise upper bound on the length of such a word for a complete DFA. This simple looking conjecture is arguably the most fascinating and longstanding open problem in the theory of finite automaton. The hypothesis was formulated in 1966 by Starke. The problem has motivated great and constantly growing number of investigations and generalizations. To prove the conjecture, we use algebra with non-standard operations on a special class of matrices (row monomial), induced by words in the alphabet of labels on edges. These matrices generate a space with respect to the mentioned operation. The proof is based on connection between length of words u and dimension of the space generated by solutions Lx of matrix equation MuLx =Ms for synchronizing word s, as well as on the relation between ranks of Mu and Lx.
A benchmark generator for boolean quadratic programming
Venue: arXiv cs.NA 2021
Year: 2021

For boolean quadratic programming (BQP), we will show that there is no duality gap between the primal and dual problems under some conditions by using the classical Lagrangian duality. A benchmark generator is given to create random BQP problems which can be solved in polynomial time. Several numerical examples are generated to demonstrate the effectiveness of the proposed method.
Multiple Depot Ring Star Problem: A polyhedral study and exact algorithm
Venue: arXiv cs.DS 2021
Year: 2021

The Multiple Depot Ring-Star Problem (MDRSP) is an important combinatorial optimization problem that arises in the context of optical fiber network design, and in applications pertaining to collecting data using stationary sensing devices and autonomous vehicles. Given the locations of a set of customers and a set of depots, the goal is to (i) find a set of simple cycles such that each cycle (ring) passes through a subset of customers and exactly one depot, (ii) assign each non-visited customer to a visited customer or a depot, and (iii) minimize the sum of the routing costs, i.e., the cost of the cycles and the assignment costs. We present a mixed integer linear programming formulation for the MDRSP and propose valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis and derive facet-inducing results for the MDRSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the MDRSP. The performance of the branch-and-cut algorithm is evaluated through extensive computational experiments on several classes of test instances.
Perfect Prediction Equilibrium
Venue: arXiv cs.GT 2021
Year: 2021

In the framework of finite games in extensive form with perfect information and strict preferences, this paper introduces a new equilibrium concept: the Perfect Prediction Equilibrium (PPE). In the Nash paradigm, rational players consider that the opponent's strategy is fixed while maximizing their payoff. The PPE, on the other hand, models the behavior of agents with an alternate form of rationality that involves a Stackelberg competition with the past. Agents with this form of rationality integrate in their reasoning that they have such accurate logical and predictive skills, that the world is fully transparent: all players share the same knowledge and know as much as an omniscient external observer. In particular, there is common knowledge of the solution of the game including the reached outcome and the thought process leading to it. The PPE is stable given each player's knowledge of its actual outcome and uses no assumptions at unreached nodes. This paper gives the general definition and construction of the PPE as a fixpoint problem, proves its existence, uniqueness and Pareto optimality, and presents two algorithms to compute it. Finally, the PPE is put in perspective with existing literature (Newcomb's Problem, Superrationality, Nash Equilibrium, Subgame Perfect Equilibrium, Backward Induction Paradox, Forward Induction).
The $π$-Calculus is Behaviourally Complete and Orbit-Finitely Executable
Venue: arXiv cs.LO 2021
Year: 2021

Reactive Turing machines extend classical Turing machines with a facility to model observable interactive behaviour. We call a behaviour (finitely) executable if, and only if, it is equivalent to the behaviour of a (finite) reactive Turing machine. In this paper, we study the relationship between executable behaviour and behaviour that can be specified in the $π$-calculus. We establish that every finitely executable behaviour can be specified in the $π$-calculus up to divergence-preserving branching bisimilarity. The converse, however, is not true due to (intended) limitations of the model of reactive Turing machines. That is, the $π$-calculus allows the specification of behaviour that is not finitely executable up to divergence-preserving branching bisimilarity. We shall prove, however, that if the finiteness requirement on reactive Turing machines and the associated notion of executability is relaxed to orbit-finiteness, then the $π$-calculus is executable up to (divergence-insensitive) branching bisimilarity.
Super-Resolution Radar
Venue: arXiv cs.IT 2021
Year: 2021

In this paper we study the identification of a time-varying linear system from its response to a known input signal. More specifically, we consider systems whose response to the input signal is given by a weighted superposition of delayed and Doppler shifted versions of the input. This problem arises in a multitude of applications such as wireless communications and radar imaging. Due to practical constraints, the input signal has finite bandwidth B, and the received signal is observed over a finite time interval of length T only. This gives rise to a delay and Doppler resolution of 1/B and 1/T. We show that this resolution limit can be overcome, i.e., we can exactly recover the continuous delay-Doppler pairs and the corresponding attenuation factors, by solving a convex optimization problem. This result holds provided that the distance between the delay-Doppler pairs is at least 2.37/B in time or 2.37/T in frequency. Furthermore, this result allows the total number of delay-Doppler pairs to be linear up to a log-factor in BT, the dimensionality of the response of the system, and thereby the limit for identifiability. Stated differently, we show that we can estimate the time-frequency components of a signal that is S-sparse in the continuous dictionary of time-frequency shifts of a random window function, from a number of measurements, that is linear up to a log-factor in S.
Reactive Synthesis Without Regret
Venue: arXiv cs.GT 2021
Year: 2021

Two-player zero-sum games of infinite duration and their quantitative versions are used in verification to model the interaction between a controller (Eve) and its environment (Adam). The question usually addressed is that of the existence (and computability) of a strategy for Eve that can maximize her payoff against any strategy of Adam. In this work, we are interested in strategies of Eve that minimize her regret, i.e. strategies that minimize the difference between her actual payoff and the payoff she could have achieved if she had known the strategy of Adam in advance. We give algorithms to compute the strategies of Eve that ensure minimal regret against an adversary whose choice of strategy is (i) unrestricted, (ii) limited to positional strategies, or (iii) limited to word strategies. We also establish relations between the latter version and other problems studied in the literature.
Better Distance Preservers and Additive Spanners
Venue: arXiv cs.DS 2021
Year: 2021

We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency, stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any $p$ demand pairs in an $n$-node undirected unweighted graph have a distance preserver on $O(n^{2/3}p^{2/3} + np^{1/3})$ edges. We leave a conjecture that the right bound is $O(n^{2/3}p^{2/3} + n)$ or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners, which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on $O(n)$ edges with $+O(n^{3/7 + \varepsilon})$ error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
Sensitivity Analysis for Binary Sampling Systems via Quantitative Fisher Information Lower Bounds
Venue: arXiv cs.IT 2021
Year: 2021

The problem of determining the achievable sensitivity with digitization exhibiting minimal complexity is addressed. In this case, measurements are exclusively available in hard-limited form. Assessing the achievable sensitivity via the Cramér-Rao lower bound requires characterization of the likelihood function, which is intractable for multivariate binary distributions. In this context, the Fisher matrix of the exponential family and a lower bound for arbitrary probabilistic models are discussed. The conservative approximation for Fisher's information matrix rests on a surrogate exponential family distribution connected to the actual data-generating system by two compact equivalences. Without characterizing the likelihood and its support, this probabilistic notion enables designing estimators that consistently achieve the sensitivity as defined by the inverse of the conservative information matrix. For parameter estimation with multivariate binary samples, a quadratic exponential surrogate distribution tames statistical complexity such that a quantitative assessment of an achievable sensitivity level becomes tractable. This fact is exploited for the performance analysis concerning parameter estimation with an array of low-complexity binary sensors in comparison to an ideal system featuring infinite amplitude resolution. Additionally, data-driven assessment by estimating a conservative approximation for the Fisher matrix under recursive binary sampling as implemented in $ΣΔ$-modulating analog-to-digital converters is demonstrated.
Collaborative Information Bottleneck
Venue: arXiv cs.IT 2021
Year: 2021

This paper investigates a multi-terminal source coding problem under a logarithmic loss fidelity which does not necessarily lead to an additive distortion measure. The problem is motivated by an extension of the Information Bottleneck method to a multi-source scenario where several encoders have to build cooperatively rate-limited descriptions of their sources in order to maximize information with respect to other unobserved (hidden) sources. More precisely, we study fundamental information-theoretic limits of the so-called: (i) Two-way Collaborative Information Bottleneck (TW-CIB) and (ii) the Collaborative Distributed Information Bottleneck (CDIB) problems. The TW-CIB problem consists of two distant encoders that separately observe marginal (dependent) components $X_1$ and $X_2$ and can cooperate through multiple exchanges of limited information with the aim of extracting information about hidden variables $(Y_1,Y_2)$, which can be arbitrarily dependent on $(X_1,X_2)$. On the other hand, in CDIB there are two cooperating encoders which separately observe $X_1$ and $X_2$ and a third node which can listen to the exchanges between the two encoders in order to obtain information about a hidden variable $Y$. The relevance (figure-of-merit) is measured in terms of a normalized (per-sample) multi-letter mutual information metric (log-loss fidelity) and an interesting tradeoff arises by constraining the complexity of descriptions, measured in terms of the rates needed for the exchanges between the encoders and decoders involved. Inner and outer bounds to the complexity-relevance region of these problems are derived from which optimality is characterized for several cases of interest. Our resulting theoretical complexity-relevance regions are finally evaluated for binary symmetric and Gaussian statistical models.
Belief-Invariant and Quantum Equilibria in Games of Incomplete Information
Venue: arXiv cs.GT 2021
Year: 2021

Drawing on ideas from game theory and quantum physics, we investigate nonlocal correlations from the point of view of equilibria in games of incomplete information. These equilibria can be classified in decreasing power as communication equilibria, belief-invariant equilibria, and correlated equilibria, all of which contain the familiar Nash equilibria. The notion of belief-invariant equilibrium appeared in game theory in the 90s. However, the class of non-signalling correlations associated to belief-invariance arose naturally already in the 80s in the foundations of quantum mechanics. In the present work, we explain and unify these two origins of the idea and study the above classes of equilibria, together with quantum correlated equilibria, using tools from quantum information but the language of (algorithmic) game theory. We present a general framework of belief-invariant communication equilibria, which contains correlated equilibria and quantum correlated equilibria as special cases. Our framework also contains the theory of Bell inequalities and their violations due to non-locality, which is a question of intense interest in the foundations of quantum mechanics, and it was indeed the original motivation for the aforementioned studies. Moreover, in our framework we can also model quantum games where players have conflicting interests, a recent developing topic in physics. We then use our framework to show new results related to the social welfare of equilibria. Namely, we exhibit a game where belief-invariance is socially better than any correlated equilibrium, and a game where all non-belief-invariant communication equilibria have a suboptimal social welfare. We also show that optimal social welfare can sometimes be achieved by quantum mechanical correlations, which do not need an informed mediator to be implemented, and go beyond the classical shared randomness approach.
Evaluating Distributed Execution of Workloads
Venue: arXiv cs.DC 2021
Year: 2021

Resource selection and task placement for distributed execution poses conceptual and implementation difficulties. Although resource selection and task placement are at the core of many tools and workflow systems, the methods are ad hoc rather than being based on models. Consequently, partial and non-interoperable implementations proliferate. We address both the conceptual and implementation difficulties by experimentally characterizing diverse modalities of resource selection and task placement. We compare the architectures and capabilities of two systems: the AIMES middleware and Swift workflow scripting language and runtime. We integrate these systems to enable the distributed execution of Swift workflows on Pilot-Jobs managed by the AIMES middleware. Our experiments characterize and compare alternative execution strategies by measuring the time to completion of heterogeneous uncoupled workloads executed at diverse scale and on multiple resources. We measure the adverse effects of pilot fragmentation and early binding of tasks to resources and the benefits of backfill scheduling across pilots on multiple resources. We then use this insight to execute a multi-stage workflow across five production-grade resources. We discuss the importance and implications for other tools and workflow systems.
A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
Venue: arXiv cs.LG 2021
Year: 2021

The task of aggregating and denoising crowd-labeled data has gained increased significance with the advent of crowdsourcing platforms and massive datasets. We propose a permutation-based model for crowd labeled data that is a significant generalization of the classical Dawid-Skene model, and introduce a new error metric by which to compare different estimators. We derive global minimax rates for the permutation-based model that are sharp up to logarithmic factors, and match the minimax lower bounds derived under the simpler Dawid-Skene model. We then design two computationally-efficient estimators: the WAN estimator for the setting where the ordering of workers in terms of their abilities is approximately known, and the OBI-WAN estimator where that is not known. For each of these estimators, we provide non-asymptotic bounds on their performance. We conduct synthetic simulations and experiments on real-world crowdsourcing data, and the experimental results corroborate our theoretical findings.