OpenRaiser/Intern-Atlas huggingface dataset:
Some properties are not even partially testable
Venue: arXiv cs.CC 2013
Year: 2013

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $ε$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, but can be partitioned into a small number of subsets for which they are partially testable with very few queries. We prove the existence of a property $P$ such that the only subsets $P'$ for which $P$ is $P'$-partially testable are very small. To prove this we introduce new techniques for proving property testing lower bounds. In addition to obtaining some broad-brush criteria for non-testability, this implies a lower bound on the possibility of PCPPs with a sublinear proof. This also implies lower bounds on MAPs, a notion newly defined by Gur and Rothblum. The new techniques rely on analyzing a proposed partial tester. We show that the queries performed by a tester must, with high probability, query indexes where a uniformly random member of the sub-property has low entropy. We then show how one can aggregate the "entropy loss" to deduce that a random choice in the sub-property must have low entropy, and therefore the sub-property must be small. We develop two techniques for aggregating the entropy loss. A simpler technique that applies to non-adaptive testers is based on partitioning the input bits into high query probability parts and parts where there is an entropy loss when conditioned on the high probability parts. Against adaptive testers we develop a technique based on constructing a decision tree. The root-to-leaf paths in this tree rearrange the input into parts where each exhibits entropy loss when conditioned on the path prefix. This decision tree is constructed by combining carefully selected decision trees from those used by the adaptive testing algorithm.
The verification of virtual community members socio-demographic profile
Venue: arXiv cs.CY 2013
Year: 2013

This article considers the current problem of investigation and development of the method of web-members' socio-demographic characteristics' profile validation based on analysis of socio-demographic characteristics. The topicality of the paper is determined by the necessity to identify the web-community member by means of computer-linguistic analysis of their information track (all information about web-community members, which posted on the Internet). The formal model of basic socio-demographic characteristics of virtual communities' member is formed. The algorithm of these characteristics verification is developed.
A Cloud Computing Survey: Developments and Future Trends in Infrastructure as a Service Computing
Venue: arXiv cs.DC 2013
Year: 2013

Cloud computing is a recent paradigm based around the notion of delivery of resources via a service model over the Internet. Despite being a new paradigm of computation, cloud computing owes its origins to a number of previous paradigms. The term cloud computing is well defined and no longer merits rigorous taxonomies to furnish a definition. Instead this survey paper considers the past, present and future of cloud computing. As an evolution of previous paradigms, we consider the predecessors to cloud computing and what significance they still hold to cloud services. Additionally we examine the technologies which comprise cloud computing and how the challenges and future developments of these technologies will influence the field. Finally we examine the challenges that limit the growth, application and development of cloud computing and suggest directions required to overcome these challenges in order to further the success of cloud computing.
The GTZAN dataset: Its contents, its faults, their effects on evaluation, and its future use
Venue: arXiv cs.SD 2013
Year: 2013

The GTZAN dataset appears in at least 100 published works, and is the most-used public dataset for evaluation in machine listening research for music genre recognition (MGR). Our recent work, however, shows GTZAN has several faults (repetitions, mislabelings, and distortions), which challenge the interpretability of any result derived using it. In this article, we disprove the claims that all MGR systems are affected in the same ways by these faults, and that the performances of MGR systems in GTZAN are still meaningfully comparable since they all face the same faults. We identify and analyze the contents of GTZAN, and provide a catalog of its faults. We review how GTZAN has been used in MGR research, and find few indications that its faults have been known and considered. Finally, we rigorously study the effects of its faults on evaluating five different MGR systems. The lesson is not to banish GTZAN, but to use it with consideration of its contents.
Highly Scalable, Parallel and Distributed AdaBoost Algorithm using Light Weight Threads and Web Services on a Network of Multi-Core Machines
Venue: arXiv cs.DC 2013
Year: 2013

AdaBoost is an important algorithm in machine learning and is being widely used in object detection. AdaBoost works by iteratively selecting the best amongst weak classifiers, and then combines several weak classifiers to obtain a strong classifier. Even though AdaBoost has proven to be very effective, its learning execution time can be quite large depending upon the application e.g., in face detection, the learning time can be several days. Due to its increasing use in computer vision applications, the learning time needs to be drastically reduced so that an adaptive near real time object detection system can be incorporated. In this paper, we develop a hybrid parallel and distributed AdaBoost algorithm that exploits the multiple cores in a CPU via light weight threads, and also uses multiple machines via a web service software architecture to achieve high scalability. We present a novel hierarchical web services based distributed architecture and achieve nearly linear speedup up to the number of processors available to us. In comparison with the previously published work, which used a single level master-slave parallel and distributed implementation [1] and only achieved a speedup of 2.66 on four nodes, we achieve a speedup of 95.1 on 31 workstations each having a quad-core processor, resulting in a learning time of only 4.8 seconds per feature.
Topological dynamics and recognition of languages
Venue: arXiv cs.FL 2013
Year: 2013

We define compact automata and show that every language has a unique minimal compact automaton. We also define recognition of languages by compact left semitopological monoids and construct the analogue of the syntactic monoid in this context. For rational languages this reduces to the usual theory of finite automata and finite monoids.
Non-constant bounded holomorphic functions of hyperbolic numbers - Candidates for hyperbolic activation functions
Venue: arXiv cs.NE 2013
Year: 2013

The Liouville theorem states that bounded holomorphic complex functions are necessarily constant. Holomorphic functions fulfill the socalled Cauchy-Riemann (CR) conditions. The CR conditions mean that a complex $z$-derivative is independent of the direction. Holomorphic functions are ideal for activation functions of complex neural networks, but the Liouville theorem makes them useless. Yet recently the use of hyperbolic numbers, lead to the construction of hyperbolic number neural networks. We will describe the Cauchy-Riemann conditions for hyperbolic numbers and show that there exists a new interesting type of bounded holomorphic functions of hyperbolic numbers, which are not constant. We give examples of such functions. They therefore substantially expand the available candidates for holomorphic activation functions for hyperbolic number neural networks. Keywords: Hyperbolic numbers, Liouville theorem, Cauchy-Riemann conditions, bounded holomorphic functions
Single Bit and Reduced Dimension Diffusion Strategies Over Distributed Networks
Venue: arXiv cs.SY 2013
Year: 2013

We introduce novel diffusion based adaptive estimation strategies for distributed networks that have significantly less communication load and achieve comparable performance to the full information exchange configurations. After local estimates of the desired data is produced in each node, a single bit of information (or a reduced dimensional data vector) is generated using certain random projections of the local estimates. This newly generated data is diffused and then used in neighboring nodes to recover the original full information. We provide the complete state-space description and the mean stability analysis of our algorithms.
The Worst Case Number of Questions in Generalized AB Game with and without White-peg Answers
Venue: arXiv cs.GT 2013
Year: 2013

The AB game is a two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. It is a variant of the famous Mastermind game, with the only difference that all pegs in both, the secret and the questions must have distinct colors. In this work, we consider the Generalized AB game, where for given arbitrary numbers $p$, $c$ with $p \le c$ the secret code consists of $p$ pegs each having one of $c$ colors and the answer consists only of a number of black and white pegs. There the number of black pegs equals the number of pegs matching in the corresponding question and the secret in position and color, and the number of white pegs equals the additional number of pegs matching in the corresponding question and the secret only in color. We consider also a variant of the Generalized AB game, where the information of white pegs is omitted. This variant is called Generalized Black-peg AB game. Let $\ab(p,c)$ and $\abb(p,c)$ be the worst case number of questions for Generalized AB game and Generalized Black-peg AB game, respectively. Combining a computer program with theoretical considerations, we confirm known exact values of $\ab(2,c)$ and $\ab(3,c)$ and prove tight bounds for $\ab(4,c)$. Furthermore, we present exact values for $\abb(2,c)$ and $\abb(3,c)$ and tight bounds for $\abb(4,c)$.
A Conceptual Metadata Framework for Spatial Data Warehouse
Venue: arXiv cs.DB 2013
Year: 2013

Metadata represents the information about data to be stored in Data Warehouses.It is a mandatory element of Data Warehouse to build an efficient Data Warehouse.Metadata helps in data integration,lineage,data quality and populating transformed data into data warehouse.Spatial data warehouses are based on spatial data mostly collected from Geographical Information Systems(GIS)and the transactional systems that are specific to an application or enterprise.Metadata design and deployment is the most critical phase in building of data warehouse where it is mandatory to bring the spatial information and data modeling together.In this paper,we present a holistic metadata framework that drives metadata creation for spatial data warehouse. Theoretically, the proposed metadata framework improves the efficiency of accessing of data in response to frequent queries on SDWs.In other words, the proposed framework decreases the response time of the query and accurate information is fetched from Data Warehouse including the spatial information.
Toward the Performance vs. Feedback Tradeoff for the Two-User MISO Broadcast Channel
Venue: arXiv cs.IT 2013
Year: 2013

For the two-user MISO broadcast channel with imperfect and delayed channel state information at the transmitter (CSIT), the work explores the tradeoff between performance on the one hand, and CSIT timeliness and accuracy on the other hand. The work considers a broad setting where communication takes place in the presence of a random fading process, and in the presence of a feedback process that, at any point in time, may provide CSIT estimates - of some arbitrary accuracy - for any past, current or future channel realization. This feedback quality may fluctuate in time across all ranges of CSIT accuracy and timeliness, ranging from perfectly accurate and instantaneously available estimates, to delayed estimates of minimal accuracy. Under standard assumptions, the work derives the degrees-of-freedom (DoF) region, which is tight for a large range of CSIT quality. This derived DoF region concisely captures the effect of channel correlations, the accuracy of predicted, current, and delayed-CSIT, and generally captures the effect of the quality of CSIT offered at any time, about any channel. The work also introduces novel schemes which - in the context of imperfect and delayed CSIT - employ encoding and decoding with a phase-Markov structure. The results hold for a large class of block and non-block fading channel models, and they unify and extend many prior attempts to capture the effect of imperfect and delayed feedback. This generality also allows for consideration of novel pertinent settings, such as the new periodically evolving feedback setting, where a gradual accumulation of feedback bits progressively improves CSIT as time progresses across a finite coherence period.
Illumination-invariant face recognition from a single image across extreme pose using a dual dimension AAM ensemble in the thermal infrared spectrum
Venue: arXiv cs.CV 2013
Year: 2013

Over the course of the last decade, infrared (IR) and particularly thermal IR imaging based face recognition has emerged as a promising complement to conventional, visible spectrum based approaches which continue to struggle when applied in practice. While inherently insensitive to visible spectrum illumination changes, IR data introduces specific challenges of its own, most notably sensitivity to factors which affect facial heat emission patterns, e.g. emotional state, ambient temperature, and alcohol intake. In addition, facial expression and pose changes are more difficult to correct in IR images because they are less rich in high frequency detail which is an important cue for fitting any deformable model. In this paper we describe a novel method which addresses these major challenges. Specifically, when comparing two thermal IR images of faces, we mutually normalize their poses and facial expressions by using an active appearance model (AAM) to generate synthetic images of the two faces with a neutral facial expression and in the same view (the average of the two input views). This is achieved by piecewise affine warping which follows AAM fitting. A major contribution of our work is the use of an AAM ensemble in which each AAM is specialized to a particular range of poses and a particular region of the thermal IR face space. Combined with the contributions from our previous work which addressed the problem of reliable AAM fitting in the thermal IR spectrum, and the development of a person-specific representation robust to transient changes in the pattern of facial temperature emissions, the proposed ensemble framework accurately matches faces across the full range of yaw from frontal to profile, even in the presence of scale variation (e.g. due to the varying distance of a subject from the camera).
Enhancement of a Novel Method for Mutational Disease Prediction using Bioinformatics Techniques and Backpropagation Algorithm
Venue: arXiv cs.CE 2013
Year: 2013

The noval method for mutational disease prediction using bioinformatics tools and datasets for diagnosis the malignant mutations with powerful Artificial Neural Network (Backpropagation Network) for classifying these malignant mutations are related to gene(s) (like BRCA1 and BRCA2) cause a disease (breast cancer). This noval method did not take in consideration just like adopted for dealing, analyzing and treat the gene sequences for extracting useful information from the sequence, also exceeded the environment factors which play important roles in deciding and calculating some of genes features in order to view its functional parts and relations to diseases. This paper is proposed an enhancement of a novel method as a first way for diagnosis and prediction the disease by mutations considering and introducing multi other features show the alternations, changes in the environment as well as genes, comparing sequences to gain information about the structure or function of a query sequence, also proposing optimal and more accurate system for classification and dealing with specific disorder using backpropagation with mean square rate 0.000000001. Index Terms (Homology sequence, GC content and AT content, Bioinformatics, Backpropagation Network, BLAST, DNA Sequence, Protein Sequence)
Communication is bounded by root of rank
Venue: arXiv cs.CC 2013
Year: 2013

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on the rank over previous results.
A Formal Approach To Firewalls Testing Techniques
Venue: arXiv cs.CR 2013
Year: 2013

Traditional technologies of firewall testing are overlooked. A new formalized approach is presented. Recommendations on optimization of test procedures are given.
Software Testing Models Against Information Security Requirements
Venue: arXiv cs.SE 2013
Year: 2013

An overview and classification of software testing models are done. Recommendations on the choice of models are proposed
Secrecy Rates in the Broadcast Channel with Confidential Messages and External Eavesdroppers
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the broadcast channel with confidential messages and external eavesdroppers (BCCE), where a multi-antenna base station simultaneously communicates to multiple potentially malicious users, in the presence of randomly located external eavesdroppers. Using the proposed model, we study the secrecy rates achievable by regularized channel inversion (RCI) precoding by performing a large-system analysis that combines tools from stochastic geometry and random matrix theory. We obtain explicit expressions for the probability of secrecy outage and an upper bound on the rate loss due to the presence of external eavesdroppers. We show that both these quantities scale as $\frac{λ_e}{\sqrt{N}}$, where $N$ is the number of transmit antennas and $λ_e$ is the density of external eavesdroppers, irrespective of their collusion strategy. Furthermore, we derive a practical rule for the choice of the regularization parameter, which is agnostic of channel state information and location of eavesdroppers, and yet provides close to optimal performance.
On the zone of the boundary of a convex body
Venue: arXiv cs.CG 2013
Year: 2013

We consider an arrangement $\A$ of $n$ hyperplanes in $\R^d$ and the zone $\Z$ in $\A$ of the boundary of an arbitrary convex set in $\R^d$ in such an arrangement. We show that, whereas the combinatorial complexity of $\Z$ is known only to be $O<n^{d-1}\log n>$ \cite{APS}, the outer part of the zone has complexity $O<n^{d-1}>$ (without the logarithmic factor). Whether this bound also holds for the complexity of the inner part of the zone is still an open question (even for $d=2$).
ATLAAS-P2P: a two layer network solution for easing the resource discovery process in unstructured networks
Venue: arXiv cs.NI 2013
Year: 2013

ATLAAS-P2P is a two-layered P2P architecture for developing systems providing resource aggregation and approximated discovery in P2P networks. Such systems allow users to search the desired resources by specifying their requirements in a flexible and easy way. From the point of view of resource providers, this system makes available an effective solution supporting providers in being reached by resource requests.
Multi-Path TCP with Network Coding for Mobile Devices in Heterogeneous Networks
Venue: arXiv cs.NI 2013
Year: 2013

Existing mobile devices have the capability to use multiple network technologies simultaneously to help increase performance; but they rarely, if at all, effectively use these technologies in parallel. We first present empirical data to help understand the mobile environment when three heterogeneous networks are available to the mobile device (i.e., a WiFi network, WiMax network, and an Iridium satellite network). We then propose a reliable, multi-path protocol called Multi-Path TCP with Network Coding (MPTCP/NC) that utilizes each of these networks in parallel. An analytical model is developed and a mean-field approximation is derived that gives an estimate of the protocol's achievable throughput. Finally, a comparison between MPTCP and MPTCP/NC is presented using both the empirical data and mean-field approximation. Our results show that network coding can provide users in mobile environments a higher quality of service by enabling the use of multiple network technologies and the capability to overcome packet losses due to lossy, wireless network connections.
Efficient and Global Optimization-Based Smoothing Methods for Mixed-Volume Meshes
Venue: arXiv cs.CG 2013
Year: 2013

Some methods based on simple regularizing geometric element transformations have heuristically been shown to give runtime efficient and quality effective smoothing algorithms for meshes. We describe the mathematical framework and a systematic approach to global optimization-based versions of such methods for mixed volume meshes. In particular, we identify efficient smoothing algorithms for certain algebraic mesh quality measures. We also provide explicit constructions of potentially useful smoothing algorithms.
Joint Transmit Diversity Optimization and Relay Selection for Cooperative MIMO Systems using Discrete Stochastic Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

We propose a joint discrete stochastic optimization based transmit diversity selection (TDS) and relay selection (RS) algorithm for decode-and-forward (DF), cooperative MIMO systems with a non-negligible direct path. TDS and RS are performed jointly with continuous least squares channel estimation (CE), linear minimum mean square error (MMSE) receivers are used at all nodes and no inter-relay communication is required. The performance of the proposed scheme is evaluated via bit-error rate (BER) comparisons and diversity analysis, and is shown to converge to the optimum exhaustive solution.
Bidirectional MMSE Algorithms for Interference Mitigation in CDMA Systems over Fast Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents adaptive bidirectional minimum mean-square error (MMSE) parameter estimation algorithms for fast-fading channels. The time correlation between successive channel gains is exploited to improve the estimation and tracking capabilities of adaptive algorithms and provide robustness against time-varying channels. Bidirectional normalized least mean-square (NLMS) and conjugate gradient (CG) algorithms are devised along with adaptive mixing parameters that adjust to the time-varying channel correlation properties. An analysis of the proposed algorithms is provided along with a discussion of their performance advantages. Simulations for an application to interference suppression in DS-CDMA systems show the advantages of the proposed algorithms.