OpenRaiser/Intern-Atlas huggingface dataset:
ViDaExpert: user-friendly tool for nonlinear visualization and analysis of multidimensional vectorial data
Venue: arXiv cs.MS 2014
Year: 2014

ViDaExpert is a tool for visualization and analysis of multidimensional vectorial data. ViDaExpert is able to work with data tables of "object-feature" type that might contain numerical feature values as well as textual labels for rows (objects) and columns (features). ViDaExpert implements several statistical methods such as standard and weighted Principal Component Analysis (PCA) and the method of elastic maps (non-linear version of PCA), Linear Discriminant Analysis (LDA), multilinear regression, K-Means clustering, a variant of decision tree construction algorithm. Equipped with several user-friendly dialogs for configuring data point representations (size, shape, color) and fast 3D viewer, ViDaExpert is a handy tool allowing to construct an interactive 3D-scene representing a table of data in multidimensional space and perform its quick and insightfull statistical analysis, from basic to advanced methods.
All-Digital Self-interference Cancellation Technique for Full-duplex Systems
Venue: arXiv cs.IT 2014
Year: 2014

Full-duplex systems are expected to double the spectral efficiency compared to conventional half-duplex systems if the self-interference signal can be significantly mitigated. Digital cancellation is one of the lowest complexity self-interference cancellation techniques in full-duplex systems. However, its mitigation capability is very limited, mainly due to transmitter and receiver circuit's impairments. In this paper, we propose a novel digital self-interference cancellation technique for full-duplex systems. The proposed technique is shown to significantly mitigate the self-interference signal as well as the associated transmitter and receiver impairments. In the proposed technique, an auxiliary receiver chain is used to obtain a digital-domain copy of the transmitted Radio Frequency (RF) self-interference signal. The self-interference copy is then used in the digital-domain to cancel out both the self-interference signal and the associated impairments. Furthermore, to alleviate the receiver phase noise effect, a common oscillator is shared between the auxiliary and ordinary receiver chains. A thorough analytical and numerical analysis for the effect of the transmitter and receiver impairments on the cancellation capability of the proposed technique is presented. Finally, the overall performance is numerically investigated showing that using the proposed technique, the self-interference signal could be mitigated to ~3dB higher than the receiver noise floor, which results in up to 76% rate improvement compared to conventional half-duplex systems at 20dBm transmit power values.
From conformal to probabilistic prediction
Venue: arXiv cs.LG 2014
Year: 2014

This paper proposes a new method of probabilistic prediction, which is based on conformal prediction. The method is applied to the standard USPS data set and gives encouraging results.
An Effective Approach for Web Document Classification using the Concept of Association Analysis of Data Mining
Venue: arXiv cs.IR 2014
Year: 2014

Exponential growth of the web increased the importance of web document classification and data mining. To get the exact information, in the form of knowing what classes a web document belongs to, is expensive. Automatic classification of web document is of great use to search engines which provides this information at a low cost. In this paper, we propose an approach for classifying the web document using the frequent item word sets generated by the Frequent Pattern (FP) Growth which is an association analysis technique of data mining. These set of associated words act as feature set. The final classification obtained after Naïve Bayes classifier used on the feature set. For the experimental work, we use Gensim package, as it is simple and robust. Results show that our approach can be effectively classifying the web document.
How to Upgrade Wireless Networks: Small Cells or Massive MIMO?
Venue: arXiv cs.IT 2014
Year: 2014

Radio network deployment and coverage optimization are critical to next-generation wireless networks. In this paper, the problem of optimally deciding on whether to install additional small cells or to upgrade current macrocell base stations (BSs) with massive antenna arrays is studied. This integrated deployment problem is cast as a general integer optimization model by using the facility location framework. The capacity limits of both the radio access link and the backhaul link are considered. The problem is shown to be an extension of the modular capacitated location problem (MCLP) which is known to be NP-hard. To solve the problem, a novel deployment algorithm that uses Lagrangian relaxation and tabu local search is proposed. The developed tabu search is shown to have a two-level structure and to be able to search the solution space thoroughly. Simulation results show how the proposed, optimal approach to upgrading an existing wireless network infrastructure can make use of a combination of both small cells and BSs with massive antennas. The results also show that the proposed algorithm can find the optimal solution effectively while having a computational time that is up to 30% lower than that of conventional algorithms.
The asymptotic complexity of matrix reduction over finite fields
Venue: arXiv cs.DS 2014
Year: 2014

Consider an invertible n \times n matrix over some field. The Gauss-Jordan elimination reduces this matrix to the identity matrix using at most n^2 row operations and in general that many operations might be needed. In [1] the authors considered matrices in GL(n;q), the set of n \times n invertible matrices in the finite field of q elements, and provided an algorithm using only row operations which performs asymptotically better than the Gauss-Jordan elimination. More specifically their `striped elimination algorithm' has asymptotic complexity \frac{n^2}{\log_q{n}}. Furthermore they proved that up to a constant factor this algorithm is best possible as almost all matrices in GL(n;g) need asymptotically at least \frac{n^2}{2\log_q{n}} operations. In this short note we show that the `striped elimination algorithm' is asymptotically optimal by proving that almost all matrices in GL(n;q) need asymptotically at least frac{n^2}{\log_q{n}} operations.
Cost-aware caching: optimizing cache provisioning and object placement in ICN
Venue: arXiv cs.NI 2014
Year: 2014

Caching is frequently used by Internet Service Providers as a viable technique to reduce the latency perceived by end users, while jointly offloading network traffic. While the cache hit-ratio is generally considered in the literature as the dominant performance metric for such type of systems, in this paper we argue that a critical missing piece has so far been neglected. Adopting a radically different perspective, in this paper we explicitly account for the cost of content retrieval, i.e. the cost associated to the external bandwidth needed by an ISP to retrieve the contents requested by its customers. Interestingly, we discover that classical cache provisioning techniques that maximize cache efficiency (i.e., the hit-ratio), lead to suboptimal solutions with higher overall cost. To show this mismatch, we propose two optimization models that either minimize the overall costs or maximize the hit-ratio, jointly providing cache sizing, object placement and path selection. We formulate a polynomial-time greedy algorithm to solve the two problems and analytically prove its optimality. We provide numerical results and show that significant cost savings are attainable via a cost-aware design.
Is a `Wirikuta empowerment' of the Huichol measurable on the Internet?
Venue: arXiv cs.SI 2014
Year: 2014

Current social and activist movements find the opportunity in social media to effectively impact on the agenda of governing bodies and create `global' perceptions -- it is often claimed. Content related to the social and activist movements is online, to be accessed, supported or disputed and distributed from virtually anywhere at any time, in the public sphere of the Internet. This activity allows the enlargement of social movements and would increase the empowerment in the concerned communities. The aim of this explorative study is to assess whether the temporal evolution of the Normalised Web Distance (NWD) --as defined by Cilibrasi & Vitányi (2007)-- between identifying terms concerning this activism could be used to measure the progress or decline of social empowerment through the Internet. The NWD relies on the page count number of single and joint queries, which in our study have been registered using a freely available web browser (e.g. Google Search) providing a time search window for temporal query results. To explore this meta-data technique, we introduce the case of a perceived Wirikuta online movement, which originated in Mexico with the aim to protect the Huichols' sacred land and water resources from open mining projects for silver ore. We conducted a small scale Internet study relating the key terms `Wirikuta', `Huichol', and `Wixarika' and their co-occurrence with seven positive qualifiers (e.g. `sacred land'), five negative qualifiers (e.g. `violence') and one neutral qualifier (`table') over time, annually from 1994 till 2013. We confirm close semantic clustering over time of traditional indigeneous identity terms of the Huichol, and observe a slight convergence of key terms to `mines' and less pronounced to `sacred land' and a divergence with respect to `ancestors' indicating a complex image of a tendency of empowerment.
Reinforcement and Imitation Learning via Interactive No-Regret Learning
Venue: arXiv cs.LG 2014
Year: 2014

Recent work has demonstrated that problems-- particularly imitation learning and structured prediction-- where a learner's predictions influence the input-distribution it is tested on can be naturally addressed by an interactive approach and analyzed using no-regret online learning. These approaches to imitation learning, however, neither require nor benefit from information about the cost of actions. We extend existing results in two directions: first, we develop an interactive imitation learning approach that leverages cost information; second, we extend the technique to address reinforcement learning. The results provide theoretical support to the commonly observed successes of online approximate policy iteration. Our approach suggests a broad new family of algorithms and provides a unifying view of existing techniques for imitation and reinforcement learning.
Stationary Mixing Bandits
Venue: arXiv cs.LG 2014
Year: 2014

We study the bandit problem where arms are associated with stationary phi-mixing processes and where rewards are therefore dependent: the question that arises from this setting is that of recovering some independence by ignoring the value of some rewards. As we shall see, the bandit problem we tackle requires us to address the exploration/exploitation/independence trade-off. To do so, we provide a UCB strategy together with a general regret analysis for the case where the size of the independence blocks (the ignored rewards) is fixed and we go a step beyond by providing an algorithm that is able to compute the size of the independence blocks from the data. Finally, we give an analysis of our bandit problem in the restless case, i.e., in the situation where the time counters for all mixing processes simultaneously evolve.
From Black-Scholes to Online Learning: Dynamic Hedging under Adversarial Environments
Venue: arXiv cs.DS 2014
Year: 2014

We consider a non-stochastic online learning approach to price financial options by modeling the market dynamic as a repeated game between the nature (adversary) and the investor. We demonstrate that such framework yields analogous structure as the Black-Scholes model, the widely popular option pricing model in stochastic finance, for both European and American options with convex payoffs. In the case of non-convex options, we construct approximate pricing algorithms, and demonstrate that their efficiency can be analyzed through the introduction of an artificial probability measure, in parallel to the so-called risk-neutral measure in the finance literature, even though our framework is completely adversarial. Continuous-time convergence results and extensions to incorporate price jumps are also presented.
Mining Recurrent Concepts in Data Streams using the Discrete Fourier Transform
Venue: arXiv cs.LG 2014
Year: 2014

In this research we address the problem of capturing recurring concepts in a data stream environment. Recurrence capture enables the re-use of previously learned classifiers without the need for re-learning while providing for better accuracy during the concept recurrence interval. We capture concepts by applying the Discrete Fourier Transform (DFT) to Decision Tree classifiers to obtain highly compressed versions of the trees at concept drift points in the stream and store such trees in a repository for future use. Our empirical results on real world and synthetic data exhibiting varying degrees of recurrence show that the Fourier compressed trees are more robust to noise and are able to capture recurring concepts with higher precision than a meta learning approach that chooses to re-use classifiers in their originally occurring form.
Generalized Mixability via Entropic Duality
Venue: arXiv cs.LG 2014
Year: 2014

Mixability is a property of a loss which characterizes when fast convergence is possible in the game of prediction with expert advice. We show that a key property of mixability generalizes, and the exp and log operations present in the usual theory are not as special as one might have thought. In doing this we introduce a more general notion of $Φ$-mixability where $Φ$ is a general entropy (\ie, any convex function on probabilities). We show how a property shared by the convex dual of any such entropy yields a natural algorithm (the minimizer of a regret bound) which, analogous to the classical aggregating algorithm, is guaranteed a constant regret when used with $Φ$-mixable losses. We characterize precisely which $Φ$ have $Φ$-mixable losses and put forward a number of conjectures about the optimality and relationships between different choices of entropy.
Dynamic Selection of Symmetric Key Cryptographic Algorithms for Securing Data Based on Various Parameters
Venue: arXiv cs.CR 2014
Year: 2014

Most of the information is in the form of electronic data. A lot of electronic data exchanged takes place through computer applications. Therefore information exchange through these applications needs to be secure. Different cryptographic algorithms are usually used to address these security concerns. However, along with security there are other factors that need to be considered for practical implementation of different cryptographic algorithms like implementation cost and performance. This paper provides comparative analysis of time taken for encryption by seven symmetric key cryptographic algorithms (AES, DES, Triple DES, RC2, Skipjack, Blowfish and RC4) with variation of parameters like different data types, data density, data size and key sizes.
Complexity of validity for propositional dependence logics
Venue: arXiv cs.LO 2014
Year: 2014

We study the validity problem for propositional dependence logic, modal dependence logic and extended modal dependence logic. We show that the validity problem for propositional dependence logic is NEXPTIME-complete. In addition, we establish that the corresponding problem for modal dependence logic and extended modal dependence logic is NEXPTIME-hard and in NEXPTIME^NP.
Combined Global and Local Search for the Falsification of Hybrid Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we solve the problem of finding a trajectory that shows that a given hybrid dynamical system with deterministic evolution leaves a given set of states considered to be safe. The algorithm combines local with global search for achieving both efficiency and global convergence. In local search, it exploits derivatives for efficient computation. Unlike other methods for falsification of hybrid systems with deterministic evolution, we do not restrict our search to trajectories of a certain bounded length but search for error trajectories of arbitrary length.
Specifying and Verifying Properties of Space - Extended Version
Venue: arXiv cs.LO 2014
Year: 2014

The interplay between process behaviour and spatial aspects of computation has become more and more relevant in Computer Science, especially in the field of collective adaptive systems, but also, more generally, when dealing with systems distributed in physical space. Traditional verification techniques are well suited to analyse the temporal evolution of programs; properties of space are typically not explicitly taken into account. We propose a methodology to verify properties depending upon physical space. We define an appropriate logic, stemming from the tradition of topological interpretations of modal logics, dating back to earlier logicians such as Tarski, where modalities describe neighbourhood. We lift the topological definitions to a more general setting, also encompassing discrete, graph-based structures. We further extend the framework with a spatial until operator, and define an efficient model checking procedure, implemented in a proof-of-concept tool.
Performance Comparison of Linear Prediction based Vocoders in Linux Platform
Venue: arXiv cs.MM 2014
Year: 2014

Linear predictive coders form an important class of speech coders. This paper describes the software level implementation of linear prediction based vocoders, viz. Code Excited Linear Prediction (CELP), Low-Delay CELP (LD-CELP) and Mixed Excitation Linear Prediction (MELP) at bit rates of 4.8 kb/s, 16 kb/s and 2.4 kb/s respectively. The C programs of the vocoders have been compiled and executed in Linux platform. Subjective testing with the help of Mean Opinion Score test has been performed. Waveform analysis has been done using Praat and Adobe Audition software. The results show that MELP and CELP produce comparable quality while the quality of LD-CELP coder is much higher, at the expense of higher bit rate.
Strong Regularities in Growth and Decline of Popularity of Social Media Services
Venue: arXiv cs.SI 2014
Year: 2014

We analyze general trends and pattern in time series that characterize the dynamics of collective attention to social media services and Web-based businesses. Our study is based on search frequency data available from Google Trends and considers 175 different services. For each service, we collect data from 45 different countries as well as global averages. This way, we obtain more than 8,000 time series which we analyze using diffusion models from the economic sciences. We find that these models accurately characterize the empirical data and our analysis reveals that collective attention to social media grows and subsides in a highly regular and predictable manner. Regularities persist across regions, cultures, and topics and thus hint at general mechanisms that govern the adoption of Web-based services. We discuss several cases in detail to highlight interesting findings. Our methods are of economic interest as they may inform investment decisions and can help assessing at what stage of the general life-cycle a Web service is at.
Convex Hulls under Uncertainty
Venue: arXiv cs.CG 2014
Year: 2014

We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input site is described by a probability distribution over a finite number of possible locations including a \emph{null} location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of $\some$-hull that may be a useful representation of uncertain hulls.
Extract Secrets from Wireless Channel: A New Shape-based Approach
Venue: arXiv cs.CR 2014
Year: 2014

Existing secret key extraction techniques use quantization to map wireless channel amplitudes to secret bits. This pa- per shows that such techniques are highly prone to environ- ment and local noise effects: They have very high mismatch rates between the two nodes that measure the channel be- tween them. This paper advocates using the shape of the channel instead of the size (or amplitude) of the channel. It shows that this new paradigm shift is significantly ro- bust against environmental and local noises. We refer to this shape-based technique as Puzzle. Implementation in a software-defined radio (SDR) platform demonstrates that Puzzle has a 63% reduction in bit mismatch rate than the state-of-art frequency domain approach (CSI-2bit). Exper- iments also show that unlike the state-of-the-art received signal strength (RSS)-based methods like ASBG, Puzzle is robust against an attack in which an eavesdropper can pre- dict the secret bits using planned movements.
Performance Comparison of Two Streaming Data Clustering Algorithms
Venue: arXiv cs.DB 2014
Year: 2014

The weighted fuzzy c-mean clustering algorithm and weighted fuzzy c-mean-adaptive cluster number are extension of traditional fuzzy c-mean Algorithm to stream data clustering algorithm.
3D Texture Coordinates on Polygon Mesh Sequences
Venue: arXiv cs.GR 2014
Year: 2014

A method for creating 3D texture coordinates for a sequence of polygon meshes with changing topology and vertex motion vectors.
FrameNet Resource Grammar Library for GF
Venue: arXiv cs.CL 2014
Year: 2014

In this paper we present an ongoing research investigating the possibility and potential of integrating frame semantics, particularly FrameNet, in the Grammatical Framework (GF) application grammar development. An important component of GF is its Resource Grammar Library (RGL) that encapsulates the low-level linguistic knowledge about morphology and syntax of currently more than 20 languages facilitating rapid development of multilingual applications. In the ideal case, porting a GF application grammar to a new language would only require introducing the domain lexicon - translation equivalents that are interlinked via common abstract terms. While it is possible for a highly restricted CNL, developing and porting a less restricted CNL requires above average linguistic knowledge about the particular language, and above average GF experience. Specifying a lexicon is mostly straightforward in the case of nouns (incl. multi-word units), however, verbs are the most complex category (in terms of both inflectional paradigms and argument structure), and adding them to a GF application grammar is not a straightforward task. In this paper we are focusing on verbs, investigating the possibility of creating a multilingual FrameNet-based GF library. We propose an extension to the current RGL, allowing GF application developers to define clauses on the semantic level, thus leaving the language-specific syntactic mapping to this extension. We demonstrate our approach by reengineering the MOLTO Phrasebook application grammar.