OpenRaiser/Intern-Atlas huggingface dataset:
Finite-Time Resilient Formation Control with Bounded Inputs
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we consider the problem of a multi-agent system achieving a formation in the presence of misbehaving or adversarial agents. We introduce a novel continuous time resilient controller to guarantee that normally behaving agents can converge to a formation with respect to a set of leaders. The controller employs a norm-based filtering mechanism, and unlike most prior algorithms, also incorporates input bounds. In addition, the controller is shown to guarantee convergence in finite time. A sufficient condition for the controller to guarantee convergence is shown to be a graph theoretical structure which we denote as Resilient Directed Acyclic Graph (RDAG). Further, we employ our filtering mechanism on a discrete time system which is shown to have exponential convergence. Our results are demonstrated through simulations.
A Reinforcement Learning Approach to Interactive-Predictive Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

We present an approach to interactive-predictive neural machine translation that attempts to reduce human effort from three directions: Firstly, instead of requiring humans to select, correct, or delete segments, we employ the idea of learning from human reinforcements in form of judgments on the quality of partial translations. Secondly, human effort is further reduced by using the entropy of word predictions as uncertainty criterion to trigger feedback requests. Lastly, online updates of the model parameters after every interaction allow the model to adapt quickly. We show in simulation experiments that reward signals on partial translations significantly improve character F-score and BLEU compared to feedback on full translations only, while human effort can be reduced to an average number of $5$ feedback requests for every input.
When Politicians Talk About Politics: Identifying Political Tweets of Brazilian Congressmen
Venue: arXiv cs.SI 2018
Year: 2018

Since June 2013, when Brazil faced the largest and most significant mass protests in a generation, a political crisis is in course. In midst of this crisis, Brazilian politicians use social media to communicate with the electorate in order to retain or to grow their political capital. The problem is that many controversial topics are in course and deputies may prefer to avoid such themes in their messages. To characterize this behavior, we propose a method to accurately identify political and non-political tweets independently of the deputy who posted it and of the time it was posted. Moreover, we collected tweets of all congressmen who were active on Twitter and worked in the Brazilian parliament from October 2013 to October 2017. To evaluate our method, we used word clouds and a topic model to identify the main political and non-political latent topics in parliamentarian tweets. Both results indicate that our proposal is able to accurately distinguish political from non-political tweets. Moreover, our analyses revealed a striking fact: more than half of the messages posted by Brazilian deputies are non-political.
Delay Performance of the Multiuser MISO Downlink
Venue: arXiv cs.IT 2018
Year: 2018

We analyze a MISO downlink channel where a multi-antenna transmitter communicates with a large number of single-antenna receivers. Using linear beamforming or nonlinear precoding techniques, the transmitter can serve multiple users simultaneously during each transmission slot. However, increasing the number of users, i.e., the multiplexing gain, reduces the beamforming gain, which means that the average of the individual data rates decreases and their variance increases. We use stochastic network calculus to analyze the queueing delay that occurs due to the time-varying data rates. Our results show that the optimal number of users, i.e., the optimal trade-off between multiplexing gain and beamforming gain, depends on incoming data traffic and its delay requirements.
Characterizing Asynchronous Message-Passing Models Through Rounds
Venue: arXiv cs.DC 2018
Year: 2018

Message-passing models of distributed computing vary along numerous dimensions: degree of synchrony, kind of faults, number of faults... Unfortunately, the sheer number of models and their subtle distinctions hinder our ability to design a general theory of message-passing models. One way out of this conundrum restricts communication to proceed by round. A great variety of message-passing models can then be captured in the Heard-Of model, through predicates on the messages sent in a round and received during or before this round. Then, the issue is to find the most accurate Heard-Of predicate to capture a given model. This is straightforward in synchronous models, because waiting for the upper bound on communication delay ensures that all available messages are received, while not waiting forever. On the other hand, asynchrony allows unbounded message delays. Is there nonetheless a meaningful characterization of asynchronous models by a Heard-Of predicate? We formalize this characterization by introducing Delivered collections: the collections of all messages delivered at each round, whether late or not. Predicates on Delivered collections capture message-passing models. The question is to determine which Heard-Of predicates can be generated by a given Delivered predicate. We answer this by formalizing strategies for when to change round. Thanks to a partial order on these strategies, we also find the "best" strategy for multiple models, where "best" intuitively means it waits for as many messages as possible while not waiting forever. Finally, a strategy for changing round that never blocks a process forever implements a Heard-Of predicate. This allows us to translate the order on strategies into an order on Heard-Of predicates. The characterizing predicate for a model is then the greatest element for that order, if it exists.
Inductive Certificate Synthesis for Control Design
Venue: arXiv cs.SY 2018
Year: 2018

The focus of this thesis is developing a framework for designing correct-by-construction controllers using control certificates. We use nonlinear dynamical systems to model the physical environment (plants). The goal is to synthesize controllers for these plants while guaranteeing formal correctness w.r.t. given specifications. We consider different fundamental specifications including stability, safety, and reach-while-stay. Stability specification states that the execution traces of the system remain close to an equilibrium state and approach it asymptotically. Safety specification requires the execution traces to stay in a safe region. Finally, for reach-while-stay specification, safety is needed until a target set is reached. The design task consists of two phases. In the first phase, the control design problem is reduced to the question of finding a control certificate. More precisely, the goal of the first phase is to define a class of control certificates with a specific structure. This definition should guarantee the following: "Having a control certificate, one can systematically design a controller and prove its correctness at the same time." The goal in the second phase is to find such a control certificate. We define a potential control certificate space (hypothesis space) using parameterized functions. Next, we provide an inductive search framework to find proper parameters, which yield a control certificate. Finally, we evaluate our framework. We show that discovering control certificates is practically feasible and demonstrate the effectiveness of the automatically designed controllers through simulations and real physical systems experiments.
A New Perspective on FO Model Checking of Dense Graph Classes
Venue: arXiv cs.LO 2018
Year: 2018

We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking of any graph class which is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.
Detecting Mutations by eBWT
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides sequenced from a genome G. Our theory accurately predicts how many copies of any nucleotide are expected inside each such cluster, and how an elegant and precise LCP array based procedure can locate these clusters in the eBWT. Our findings are very general and can be applied to a wide range of different problems. In this paper, we consider the case of alignment-free and reference-free SNPs discovery in multiple collections of reads. We note that, in accordance with our theoretical results, SNPs are clustered in the eBWT of the reads collection, and we develop a tool finding SNPs with a simple scan of the eBWT and LCP arrays. Preliminary results show that our method requires much less coverage than state-of-the-art tools while drastically improving precision and sensitivity.
Collaborations on YouTube: From Unsupervised Detection to the Impact on Video and Channel Popularity
Venue: arXiv cs.CV 2018
Year: 2018

YouTube is one of the most popular platforms for streaming of user-generated video. Nowadays, professional YouTubers are organized in so called multi-channel networks (MCNs). These networks offer services such as brand deals, equipment, and strategic advice in exchange for a share of the YouTubers' revenue. A major strategy to gain more subscribers and, hence, revenue is collaborating with other YouTubers. Yet, collaborations on YouTube have not been studied in a detailed quantitative manner. This paper aims to close this gap with the following contributions. First, we collect a YouTube dataset covering video statistics over three months for 7,942 channels. Second, we design a framework for collaboration detection given a previously unknown number of persons featuring in YouTube videos. We denote this framework for the analysis of collaborations in YouTube videos using a Deep Neural Network (DNN) based approach as CATANA. Third, we analyze about 2.4 years of video content and use CATANA to answer research questions providing guidance for YouTubers and MCNs for efficient collaboration strategies. Thereby, we focus on (i) collaboration frequency and partner selectivity, (ii) the influence of MCNs on channel collaborations, (iii) collaborating channel types, and (iv) the impact of collaborations on video and channel popularity. Our results show that collaborations are in many cases significantly beneficial in terms of viewers and newly attracted subscribers for both collaborating channels, showing often more than 100% popularity growth compared with non-collaboration videos.
Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination
Venue: arXiv cs.CV 2018
Year: 2018

Neural net classifiers trained on data with annotated class labels can also capture apparent visual similarity among categories without being directed to do so. We study whether this observation can be extended beyond the conventional domain of supervised learning: Can we learn a good feature representation that captures apparent similarity among instances, instead of classes, by merely asking the feature to be discriminative of individual instances? We formulate this intuition as a non-parametric classification problem at the instance-level, and use noise-contrastive estimation to tackle the computational challenges imposed by the large number of instance classes. Our experimental results demonstrate that, under unsupervised learning settings, our method surpasses the state-of-the-art on ImageNet classification by a large margin. Our method is also remarkable for consistently improving test performance with more training data and better network architectures. By fine-tuning the learned feature, we further obtain competitive results for semi-supervised learning and object detection tasks. Our non-parametric model is highly compact: With 128 features per image, our method requires only 600MB storage for a million images, enabling fast nearest neighbour retrieval at the run time.
Confluent terminating extensional lambda-calculi with surjective pairing and terminal type
Venue: arXiv cs.LO 2018
Year: 2018

For the lambda-calculus with surjective pairing and terminal type, Curien and Di Cosmo were inspired by Knuth-Bendix completion, and introduced a confluent rewriting system that (1) extends the naive rewriting system, and (2) is stable under contexts. The rewriting system has (i) a rule that rewrites term of a terminal type rewrites to a term constant *, unless the term is not *, (ii) rewrite rules for the extensionality of function types and product types, and rewrite rules mediating the rewrite rules (i) and (ii). Curien and Di Cosmo supposed that because of (iii), any reducibility method cannot prove the strong normalization (SN) of Curien-Di Cosmo's rewriting system, and they left the SN open. By relativizing Girard's reducibility method to the *-free terms, we prove SN of their rewriting, and SN of the extension by polymorphism. The relativization works because: for any SN term t, and for any variable z of terminal type not occurring in $t$, t with all the occurrences of * of terminal type replaced by the variable z is SN.
An efficient Moving Morphable Component (MMC)-based approach for multi-resolution topology optimization
Venue: arXiv cs.CE 2018
Year: 2018

In the present work, a highly efficient Moving Morphable Component (MMC) based approach for multi-resolution topology optimization is proposed. In this approach, high-resolution optimization results can be obtained with much less number of degrees of freedoms (DOFs) and design variables since the finite element analysis model and the design optimization model are totally decoupled in the MMC-based problem formulation. This is achieved by introducing super-elements for structural response analysis and adopting a domain decomposition strategy to preserve the topology complexity of optimized structures. Both two-and three-dimensional numerical results demonstrate that substantial computational efforts can be saved with use of the proposed approach.
Generalised Dining Philosophers as Feedback Control
Venue: arXiv cs.SY 2018
Year: 2018

We revisit the Generalised Dining Philosophers problem through the perspective of feedback control. The result is a modular development of the solution using the notions of system and system composition (the latter due to Tabuada) in a formal setting that employs simple equational reasoning. The modular approach separates the solution architecture from the algorithmic minutiae and has the benefit of simplifying the design and correctness proofs. Three variants of the problem are considered: N=1, and N>1 with centralised and distributed topology. The base case (N=1) reveals important insights into the problem specification and the architecture of the solution. In each case, solving the Generalised Dining Philosophers reduces to designing an appropriate feedback controller.
DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
Venue: arXiv cs.DS 2018
Year: 2018

This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned. We introduce DISPATCH, a 0.5-competitive, randomized algorithm. We also prove that 0.5-competitive is the best possible. DISPATCH first selects a "preferred worker" and assigns the job to this worker if it is available. The preferred worker is determined based on an optimal solution to a fractional transportation problem. If the preferred worker is not available, DISPATCH randomly selects a worker from the available workers. We show that DISPATCH maintains a uniform distribution over the workers even when the distribution over the job types is non-uniform.
Position Estimation of Camera Based on Unsupervised Learning
Venue: arXiv cs.CV 2018
Year: 2018

It is an exciting task to recover the scene's 3d-structure and camera pose from the video sequence. Most of the current solutions divide it into two parts, monocular depth recovery and camera pose estimation. The monocular depth recovery is often studied as an independent part, and a better depth estimation is used to solve the pose. While camera pose is still estimated by traditional SLAM (Simultaneous Localization And Mapping) methods in most cases. The use of unsupervised method for monocular depth recovery and pose estimation has benefited from the study of [1] and achieved good results. In this paper, we improve the method of [1]. Our emphasis is laid on the improvement of the idea and related theory, introducing a more reasonable inter frame constraints and finally synthesize the camera trajectory with inter frame pose estimation in the unified world coordinate system. And our results get better performance.
Optimal Harvest-or-Transmit Strategy for Energy Harvesting Underlay Cognitive Radio Network
Venue: arXiv cs.IT 2018
Year: 2018

An underlay cognitive radio network with energy harvesting is considered which operates in slotted fashion. The primary user (PU) transmits with a constant power in each slot, while the secondary user (SU) either harvests energy from primary's transmission or transmits its data. We propose an optimal offline harvest-or-transmit strategy where in each slot, SU takes a decision whether to harvest energy or transmit its data limiting interference at the primary receiver. We aim to maximize the achievable rate of SU under energy causality and interference constraints. The optimization problem is formulated as a mixed integer non-linear program and the optimal harvest-or-transmit policy is obtained using generalized Benders decomposition algorithm. Through simulations, we analyze the effects of various system parameters and interference constraint at the primary receiver on the optimal policy.
Weakly-supervised Visual Instrument-playing Action Detection in Videos
Venue: arXiv cs.MM 2018
Year: 2018

Instrument playing is among the most common scenes in music-related videos, which represent nowadays one of the largest sources of online videos. In order to understand the instrument-playing scenes in the videos, it is important to know what instruments are played, when they are played, and where the playing actions occur in the scene. While audio-based recognition of instruments has been widely studied, the visual aspect of the music instrument playing remains largely unaddressed in the literature. One of the main obstacles is the difficulty in collecting annotated data of the action locations for training-based methods. To address this issue, we propose a weakly-supervised framework to find when and where the instruments are played in the videos. We propose to use two auxiliary models, a sound model and an object model, to provide supervisions for training the instrument-playing action model. The sound model provides temporal supervisions, while the object model provides spatial supervisions. They together can simultaneously provide temporal and spatial supervisions. The resulted model only needs to analyze the visual part of a music video to deduce which, when and where instruments are played. We found that the proposed method significantly improves the localization accuracy. We evaluate the result of the proposed method temporally and spatially on a small dataset (totally 5,400 frames) that we manually annotated.
Bone marrow cells detection: A technique for the microscopic image analysis
Venue: arXiv cs.CV 2018
Year: 2018

In the detection of myeloproliferative, the number of cells in each type of bone marrow cells (BMC) is an important parameter for the evaluation. In this study, we propose a new counting method, which also consists of three modules including localization, segmentation and classification. The localization of BMC is achieved from a color transformation enhanced BMC sample image and stepwise averaging method (SAM). In the nucleus segmentation, both SAM and Otsu's method will be applied to obtain a weighted threshold for segmenting the patch into nucleus and non-nucleus. In the cytoplasm segmentation, a color weakening transformation, an improved region growing method and the K-Means algorithm are used. The connected cells with BMC will be separated by the marker-controlled watershed algorithm. The features will be extracted for the classification after the segmentation. In this study, the BMC are classified using the SVM, Random Forest, Artificial Neural Networks, Adaboost and Bayesian Networks into five classes including one outlier, namely, neutrophilic split granulocyte, neutrophilic stab granulocyte, metarubricyte, mature lymphocytes and the outlier (all other cells not listed). Our experimental results show that the best average recognition rate is 87.49% for the SVM.
Dynamic relations in sampled processes
Venue: arXiv cs.SY 2018
Year: 2018

Linear dynamical relations that may exist in continuous-time, or at some natural sampling rate, are not directly discernable at reduced observational sampling rates. Indeed, at reduced rates, matricial spectral densities of vectorial time series have maximal rank and thereby cannot be used to ascertain potential dynamic relations between their entries. This hitherto undeclared source of inaccuracies appears to plague off-the-shelf identification techniques seeking remedy in hypothetical observational noise. In this paper we explain the exact relation between stochastic models at different sampling rates and show how to construct stochastic models at the finest time scale that data allows. We then point out that the correct number of dynamical dependences can only be ascertained by considering stochastic models at this finest time scale, which in general is faster than the observational sampling rate.
Modelling Competitive marketing strategies in Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

In a competitive marketing, there are a large number of players which produce the same product. Each firm aims to diffuse its product information widely so that it's product will become popular among potential buyers. The more popular is a product of a firm, the higher is the revenue for the firm. A model is developed in which two players compete to spread information in the large network. Players choose their initial seed nodes simultaneously and the information is diffused according to Independent Cascade model (ICM). The main aim of the player is to choose the seed nodes such that they will spread its information to as many nodes as possible in a social network. The rate of spreading of information also plays a very important role in information diffusion process. Any node in a social network will get influenced by none or one or more than one information. We also analyzed how much fraction of nodes in different compartment changes by changing the rate of spreading of information. Finally, a game theory model is developed to obtain the Nash equilibrium based on best response function of the players. This model is based on Hotelling's model of electoral competition.