OpenRaiser/Intern-Atlas huggingface dataset:
Drawing Graphs within Restricted Area
Venue: arXiv cs.CG 2014
Year: 2014

We study the problem of selecting a maximum-weight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given non-uniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) calculation graphs which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.
Transferring Landmark Annotations for Cross-Dataset Face Alignment
Venue: arXiv cs.CV 2014
Year: 2014

Dataset bias is a well known problem in object recognition domain. This issue, nonetheless, is rarely explored in face alignment research. In this study, we show that dataset plays an integral part of face alignment performance. Specifically, owing to face alignment dataset bias, training on one database and testing on another or unseen domain would lead to poor performance. Creating an unbiased dataset through combining various existing databases, however, is non-trivial as one has to exhaustively re-label the landmarks for standardisation. In this work, we propose a simple and yet effective method to bridge the disparate annotation spaces between databases, making datasets fusion possible. We show extensive results on combining various popular databases (LFW, AFLW, LFPW, HELEN) for improved cross-dataset and unseen data alignment.
Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
Venue: arXiv cs.DM 2014
Year: 2014

A graph is equitably $k$-colorable if its vertices can be partitioned into $k$ independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest $k$ for which such a coloring exists is known as the \emph{equitable chromatic number} of $G$ and it is denoted by $χ_{=}(G)$. In this paper the problem of determinig $χ_=$ for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses $χ_=(G)$ or $χ_=(G)+1$ colors. Our algorithm is best possible, unless $P=NP$. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.
Detect Adverse Drug Reactions for Drug Aspirin
Venue: arXiv cs.CE 2014
Year: 2014

Adverse drug reaction (ADR) is widely concerned for public health issue. In this study we propose an original approach to detect the ADRs using feature matrix and feature selection. The experiments are carried out on the drug Aspirin. Major side effects for the drug are detected and better performance is achieved compared to other computerized methods. The detected ADRs are based on the computerized method, further investigation is needed.
Precoding for Multiuser MIMO Systems with Single-Fed Parasitic Antenna Arrays
Venue: arXiv cs.IT 2014
Year: 2014

Transmitter (TX) cooperation at various levels has been shown to increase the sum throughput of multiuser multiple-input multiple-output (MIMO) systems. In this paper we consider a K-user MIMO system where TXs have only global channel state knowledge. It has been theoretically shown that interference alignment (IA) achieves the K/2 degrees of freedom of this K-user MIMO interference channel. However, results on IA and all proposed transceiver techniques for this channel up to date, assume conventional antenna arrays at the transceivers with multiple radio-frequency (RF) chains, each connected to a different antenna element. To reduce the consequent hardware burden and power dissipation imposed by such arrays, we propose in this paper the utilization of compact single-RF electronically steerable parasitic (passive) array radiators (ESPARs) at the cooperating TXs. A signal model capable of capturing the characteristics of the considered antenna arrays is first described and then a general precoding design methodology for the tunable parasitic loads at the TXs' ESPARs is introduced. Specific precoding techniques and an indicative ESPAR design are presented for a 3-user 2x2 MIMO system with one ESPAR TX, and the obtained performance evaluation results show that the gains of TX cooperation are still feasible.
A Novel Semi-Supervised Algorithm for Rare Prescription Side Effect Discovery
Venue: arXiv cs.LG 2014
Year: 2014

Drugs are frequently prescribed to patients with the aim of improving each patient's medical state, but an unfortunate consequence of most prescription drugs is the occurrence of undesirable side effects. Side effects that occur in more than one in a thousand patients are likely to be signalled efficiently by current drug surveillance methods, however, these same methods may take decades before generating signals for rarer side effects, risking medical morbidity or mortality in patients prescribed the drug while the rare side effect is undiscovered. In this paper we propose a novel computational meta-analysis framework for signalling rare side effects that integrates existing methods, knowledge from the web, metric learning and semi-supervised clustering. The novel framework was able to signal many known rare and serious side effects for the selection of drugs investigated, such as tendon rupture when prescribed Ciprofloxacin or Levofloxacin, renal failure with Naproxen and depression associated with Rimonabant. Furthermore, for the majority of the drug investigated it generated signals for rare side effects at a more stringent signalling threshold than existing methods and shows the potential to become a fundamental part of post marketing surveillance to detect rare side effects.
Signalling Paediatric Side Effects using an Ensemble of Simple Study Designs
Venue: arXiv cs.LG 2014
Year: 2014

Background: Children are frequently prescribed medication off-label, meaning there has not been sufficient testing of the medication to determine its safety or effectiveness. The main reason this safety knowledge is lacking is due to ethical restrictions that prevent children from being included in the majority of clinical trials. Objective: The objective of this paper is to investigate whether an ensemble of simple study designs can be implemented to signal acutely occurring side effects effectively within the paediatric population by using historical longitudinal data. The majority of pharmacovigilance techniques are unsupervised, but this research presents a supervised framework. Methods: Multiple measures of association are calculated for each drug and medical event pair and these are used as features that are fed into a classiffier to determine the likelihood of the drug and medical event pair corresponding to an adverse drug reaction. The classiffier is trained using known adverse drug reactions or known non-adverse drug reaction relationships. Results: The novel ensemble framework obtained a false positive rate of 0:149, a sensitivity of 0:547 and a specificity of 0:851 when implemented on a reference set of drug and medical event pairs. The novel framework consistently outperformed each individual simple study design. Conclusion: This research shows that it is possible to exploit the mechanism of causality and presents a framework for signalling adverse drug reactions effectively.
Bypassing Captcha By Machine A Proof For Passing The Turing Test
Venue: arXiv cs.CV 2014
Year: 2014

For the last ten years, CAPTCHAs have been widely used by websites to prevent their data being automatically updated by machines. By supposedly allowing only humans to do so, CAPTCHAs take advantage of the reverse Turing test (TT), knowing that humans are more intelligent than machines. Generally, CAPTCHAs have defeated machines, but things are changing rapidly as technology improves. Hence, advanced research into optical character recognition (OCR) is overtaking attempts to strengthen CAPTCHAs against machine-based attacks. This paper investigates the immunity of CAPTCHA, which was built on the failure of the TT. We show that some CAPTCHAs are easily broken using a simple OCR machine built for the purpose of this study. By reviewing other techniques, we show that even more difficult CAPTCHAs can be broken using advanced OCR machines. Current advances in OCR should enable machines to pass the TT in the image recognition domain, which is exactly where machines are seeking to overcome CAPTCHAs. We enhance traditional CAPTCHAs by employing not only characters, but also natural language and multiple objects within the same CAPTCHA. The proposed CAPTCHAs might be able to hold out against machines, at least until the advent of a machine that passes the TT completely.
An Integer Programming Based Bound for Locally Repairable Codes
Venue: arXiv cs.IT 2014
Year: 2014

The locally repairable code (LRC) studied in this paper is an $[n,k]$ linear code of which the value at each coordinate can be recovered by a linear combination of at most $r$ other coordinates. The central problem in this work is to determine the largest possible minimum distance for LRCs. First, an integer programming based upper bound is derived for any LRC. Then by solving the programming problem under certain conditions, an explicit upper bound is obtained for LRCs with parameters $n_1>n_2$, where $n_1 = \left\lceil \frac{n}{r+1} \right\rceil$ and $n_2 = n_1 (r+1) - n$. Finally, an explicit construction for LRCs attaining this upper bound is presented over the finite field $\mathbb{F}_{2^m}$, where $m\geq n_1r$. Based on these results, the largest possible minimum distance for all LRCs with $r \le \sqrt{n}-1$ has been definitely determined, which is of great significance in practical use.
Taming the Concurrency: Controlling Concurrent Behavior while Testing Multithreaded Software
Venue: arXiv cs.SE 2014
Year: 2014

Developing multithreaded software is an extremely challenging task, even for experienced programmers. The challenge does not end after the code is written. There are other tasks associated with a development process that become exceptionally hard in a multithreaded environment. A good example of this is creating unit tests for concurrent data structures. In addition to the desired test logic, such a test contains plenty of synchronization code that makes it hard to understand and maintain. In our work we propose a novel approach for specifying and executing schedules for multithreaded tests. It allows explicit specification of desired thread scheduling for some unit test and enforces it during the test execution, giving the developer an ability to construct deterministic and repeatable unit tests. This goal is achieved by combining a few basic tools available in every modern runtime/IDE and does not require dedicated runtime environment, new specification language or code under test modifications.
Attack of the Ants: Studying Ant Routing Algorithms in Simulation and Wireless Testbeds
Venue: arXiv cs.NI 2014
Year: 2014

Wireless networks are becoming the key building block of our communications infrastructure. Examples range from cellular networks to ad hoc and sensor networks in wildlife monitoring and environmental scenarios. With the rise of the Internet of Things (IoT) millions of physical and virtual objects will communicate wireless and enhance the daily life. The adaptivity and scalability of wireless networks in the IoT is one of the most challenging tasks. Bio-inspired networking algorithms are a way to tackle these issues. In this paper we present a simulation framework based on OMNeT++ to implement ant routing algorithms to study and compare them on the algorithmic level and an approach to run large simulation studies in a comprehensive way.
Enabling Distributed Simulation of OMNeT++ INET Models
Venue: arXiv cs.NI 2014
Year: 2014

Parallel and distributed simulation have been extensively researched for a long time. Nevertheless, many simulation models are still executed sequentially. We attribute this to the fact that many of those models are simply not capable of being executed in parallel since they violate particular constraints. In this paper, we analyze the INET model suite, which enables network simulation in OMNeT++, with regard to parallelizability. We uncovered several issues preventing parallel execution of INET models. We analyzed those issues and developed solutions allowing INET models to be run in parallel. A case study shows the feasibility of our approach. Though there are parts of the model suite that we didn't investigate yet and the performance can still be improved, the results show parallelization speedup for most configurations. The source code of our implementation is available through our web site at code.comsys.rwth-aachen.de.
The planar minimum linear arrangement problem is different from the minimum linear arrangement problem
Venue: arXiv cs.DS 2014
Year: 2014

In various research papers, such as [2], one will find the claim that the minLA is optimally solvable on outerplanar graphs, with a reference to [1]. However, the problem solved in that publication, which we refer to as the planar minimum linear arrangement problem (planar minLA), is different from the minimum linear arrangement problem (minLA), as we show in this article.
Tuning a Multiple Classifier System for Side Effect Discovery using Genetic Algorithms
Venue: arXiv cs.LG 2014
Year: 2014

In previous work, a novel supervised framework implementing a binary classifier was presented that obtained excellent results for side effect discovery. Interestingly, unique side effects were identified when different binary classifiers were used within the framework, prompting the investigation of applying a multiple classifier system. In this paper we investigate tuning a side effect multiple classifying system using genetic algorithms. The results of this research show that the novel framework implementing a multiple classifying system trained using genetic algorithms can obtain a higher partial area under the receiver operating characteristic curve than implementing a single classifier. Furthermore, the framework is able to detect side effects efficiently and obtains a low false positive rate.
Kolmogorov complexity and the geometry of Brownian motion
Venue: arXiv cs.CC 2014
Year: 2014

In this paper, we continue the study of the geometry of Brownian motions which are encoded by Kolmogorov-Chaitin random reals (complex oscillations). We unfold Kolmogorov-Chaitin complexity in the context of Brownian motion and specifically to phenomena emerging from the random geometric patterns generated by a Brownian motion.
Mining and Analyzing Twitter trends: Frequency based ranking of descriptive Tweets
Venue: arXiv cs.SI 2014
Year: 2014

One of the major sources of trending news, events and opinion in the current age is micro blogging. Twitter, being one of them, is extensively used to mine data about public responses and event updates. This paper intends to propose methods to filter tweets to obtain the most accurately descriptive tweets, which communicates the content of the trend. It also potentially ranks the tweets according to relevance. The principle behind the ranking mechanism would be the assumed tendencies in the natural language used by the users. The mapping frequencies of occurrence of words and related hash tags is used to create a weighted score for each tweet in the sample space obtained from twitter on a particular trend.
Tunably Rugged Landscapes with Known Maximum and Minimum
Venue: arXiv cs.NE 2014
Year: 2014

We propose NM landscapes as a new class of tunably rugged benchmark problems. NM landscapes are well-defined on alphabets of any arity, including both discrete and real-valued alphabets, include epistasis in a natural and transparent manner, are proven to have known value and location of the global maximum and, with some additional constraints, are proven to also have a known global minimum. Empirical studies are used to illustrate that, when coefficients are selected from a recommended distribution, the ruggedness of NM landscapes is smoothly tunable and correlates with several measures of search difficulty. We discuss why these properties make NM landscapes preferable to both NK landscapes and Walsh polynomials as benchmark landscape models with tunable epistasis.
Optimal Spectrum Access for a Rechargeable Cognitive Radio User Based on Energy Buffer State
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the maximum throughput for a rechargeable secondary user (SU) sharing the spectrum with a primary user (PU) plugged to a reliable power supply. The SU maintains a finite energy queue and harvests energy from natural resources, e.g., solar, wind and acoustic noise. We propose a probabilistic access strategy by the SU based on the number of packets at its energy queue. We investigate the effect of the energy arrival rate, the amount of energy per energy packet, and the capacity of the energy queue on the SU throughput under fading channels. Results reveal that the proposed access strategy can enhance the performance of the SU.
Impact of Received Signal on Self-interference Channel Estimation and Achievable Rates in In-band Full-duplex Transceivers
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we analyze the effect of the calibration period, or lack of, on self-interference channel estimation in the digital domain of in-band full-duplex radio transceivers. In particular, we consider a scenario where the channel estimation must be performed without a separate calibration period, which means that the received signal of interest will act as an additional noise source from the estimation perspective. We will explicitly analyze its effect, and quantify the increase in the parameter estimation variance, or sample size, if similar accuracy for the channel estimate is to be achieved as with a separate calibration period. In addition, we will analyze how the calibration period, or its absence, affects the overall achievable rates. Full waveform simulations are then used to determine the validity of the obtained results, as well as provide numerical results regarding the achievable rates. It is shown that, even though a substantial increase in the parameter sample size is required if there is no calibration period, the achievable rates are still comparable for the two scenarios.
Run Vector Analysis and Barker Sequences of Odd Length
Venue: arXiv cs.IT 2014
Year: 2014

The run vector of a binary sequence reflects the run structure of the sequence, which is given by the set of all substrings of the run length encoding. The run vector and the aperiodic autocorrelations of a binary sequence are strongly related. In this paper, we analyze the run vector of skew-symmetric binary sequences. Using the derived results we present a new and different proof that there exists no Barker sequence of odd length n > 13. Barker sequences are binary sequences whose off-peak aperiodic autocorrelations are all in magnitude at most 1.
Fundamental Limits on Communication for Oblivious Updates in Storage Networks
Venue: arXiv cs.IT 2014
Year: 2014

In distributed storage systems, storage nodes intermittently go offline for numerous reasons. On coming back online, nodes need to update their contents to reflect any modifications to the data in the interim. In this paper, we consider a setting where no information regarding modified data needs to be logged in the system. In such a setting, a 'stale' node needs to update its contents by downloading data from already updated nodes, while neither the stale node nor the updated nodes have any knowledge as to which data symbols are modified and what their value is. We investigate the fundamental limits on the amount of communication necessary for such an "oblivious" update process. We first present a generic lower bound on the amount of communication that is necessary under any storage code with a linear encoding (while allowing non-linear update protocols). This lower bound is derived under a set of extremely weak conditions, giving all updated nodes access to the entire modified data and the stale node access to the entire stale data as side information. We then present codes and update algorithms that are optimal in that they meet this lower bound. Next, we present a lower bound for an important subclass of codes, that of linear Maximum-Distance-Separable (MDS) codes. We then present an MDS code construction and an associated update algorithm that meets this lower bound. These results thus establish the capacity of oblivious updates in terms of the communication requirements under these settings.
Spectral Super-resolution With Prior Knowledge
Venue: arXiv cs.IT 2014
Year: 2014

We address the problem of super-resolution frequency recovery using prior knowledge of the structure of a spectrally sparse, undersampled signal. In many applications of interest, some structure information about the signal spectrum is often known. The prior information might be simply knowing precisely some signal frequencies or the likelihood of a particular frequency component in the signal. We devise a general semidefinite program to recover these frequencies using theories of positive trigonometric polynomials. Our theoretical analysis shows that, given sufficient prior information, perfect signal reconstruction is possible using signal samples no more than thrice the number of signal frequencies. Numerical experiments demonstrate great performance enhancements using our method. We show that the nominal resolution necessary for the grid-free results can be improved if prior information is suitably employed.
Simulating Non Stationary Operators in Search Algorithms
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we propose a model for simulating search operators whose behaviour often changes continuously during the search. In these scenarios, the performance of the operators decreases when they are applied. This is motivated by the fact that operators for optimization problems are often roughly classified into exploitation operators and exploration operators. Our simulation model is used to compare the different performances of operator selection policies and clearly identify their ability to adapt to such specific operators behaviours. The experimental study provides interesting results on the respective behaviours of operator selection policies when faced to such non stationary search scenarios.
The Homogeneity Indicator of Learners in Project-based Learning
Venue: arXiv cs.CY 2014
Year: 2014

The development of ICT has emerged a new way of learning using electronic platforms: E-learning. In addition, pedagogical approaches have been adopted in teaching based on group learning, such as the project-based teaching. The project-based teaching is an active learning method, based on group work to develop skills and acquire knowledge. However, the group of students is facing several challenges throughout the project, such as the decision-making group. The group decision generates convergences and divergences among members. Our approach in this article relates to the calculation of the homogeneity of a group of learners during decision making in an educational project.
Scalability Concept for Predictable Closed-Loop Response of Adaptive Controllers
Venue: arXiv cs.SY 2014
Year: 2014

We introduce a new concept called scalability to adaptive control in this paper. In particular, we analyze how to scale learning rates of adaptive weight update laws of various adaptive control schemes with respect to given command profiles to achieve a predictable closed-loop response. An illustrative numerical example is provided to demonstrate the proposed concept, which emphasize that it can be an effective tool for validation and verification of adaptive controllers.