OpenRaiser/Intern-Atlas huggingface dataset:
Optimization Of Cross Domain Sentiment Analysis Using Sentiwordnet
Venue: arXiv cs.CL 2013
Year: 2013

The task of sentiment analysis of reviews is carried out using manually built / automatically generated lexicon resources of their own with which terms are matched with lexicon to compute the term count for positive and negative polarity. On the other hand the Sentiwordnet, which is quite different from other lexicon resources that gives scores (weights) of the positive and negative polarity for each word. The polarity of a word namely positive, negative and neutral have the score ranging between 0 to 1 indicates the strength/weight of the word with that sentiment orientation. In this paper, we show that using the Sentiwordnet, how we could enhance the performance of the classification at both sentence and document level.
PageRank for evolving link structures
Venue: arXiv cs.IR 2013
Year: 2013

In this article we will look at the PageRank algorithm used as part of the ranking process of different Internet pages in search engines by for example Google. This article has its main focus in the understanding of the behavior of PageRank as the system dynamically changes either by contracting or expanding such as when adding or subtracting nodes or links or groups of nodes or links. In particular we will take a look at link structures consisting of a line of nodes or a complete graph where every node links to all others. We will look at PageRank as the solution of a linear system of equations and do our examination in both the ordinary normalized version of PageRank as well as the non-normalized version found by solving the linear system. We will see that it is possible to find explicit formulas for the PageRank in some simple link structures and using these formulas take a more in-depth look at the behavior of the ranking as the system changes.
Bringing Reference Groups Back: Agent-based Modeling of the Spiral of Silence
Venue: arXiv cs.CY 2013
Year: 2013

The purpose of this study is threefold: first, to bring reference groups back into the framework of spiral of silence (SOS) by proposing an extended framework of dual opinion climate; second, to investigate the boundary conditions of SOS; third, to identify the characteristics of SOS in terms of spatial variation and temporal evolution. Modeling SOS with agent-based models, the findings suggest (1) there is no guarantee of SOS with reference groups being brought back; (2) Stable existence of SOS is contingent upon the comparative strength of mass media over reference groups; (3) SOS is size-dependent upon reference groups and the population; (4) the growth rate of SOS decreases over time. Thus, this research presents an extension of the SOS theory.
Comparative study of Authorship Identification Techniques for Cyber Forensics Analysis
Venue: arXiv cs.CY 2013
Year: 2013

Authorship Identification techniques are used to identify the most appropriate author from group of potential suspects of online messages and find evidences to support the conclusion. Cybercriminals make misuse of online communication for sending blackmail or a spam email and then attempt to hide their true identities to void detection.Authorship Identification of online messages is the contemporary research issue for identity tracing in cyber forensics. This is highly interdisciplinary area as it takes advantage of machine learning, information retrieval, and natural language processing. In this paper, a study of recent techniques and automated approaches to attributing authorship of online messages is presented. The focus of this review study is to summarize all existing authorship identification techniques used in literature to identify authors of online messages. Also it discusses evaluation criteria and parameters for authorship attribution studies and list open questions that will attract future work in this area.
smart application for AMS using Face Recognition
Venue: arXiv cs.CY 2013
Year: 2013

Attendance Management System (AMS) can be made into smarter way by using face recognition technique, where we use a CCTV camera to be fixed at the entry point of a classroom, which automatically captures the image of the person and checks the observed image with the face database using android enhanced smart phone. It is typically used for two purposes. Firstly, marking attendance for student by comparing the face images produced recently and secondly, recognition of human who are strange to the environment i.e. an unauthorized person For verification of image, a newly emerging trend 3D Face Recognition is used which claims to provide more accuracy in matching the image databases and has an ability to recognize a subject at different view angles.
GDF - A general dataformat for biosignals
Venue: arXiv cs.DL 2013
Year: 2013

Biomedical signals are stored in many different data formats. Most formats have been developed for a specific purpose of a specialized community for ECG research, EEG analysis, sleep research, etc. So far none of the existing formats can be considered a general purpose data format for biomedical signals. In order to solve this problem and to unify the various needs of the various biomedical signal processing fields, the so-called "General Data Format for biomedical signals" (GDF) is developed. This GDF format is fully described and specified. Software for reading and writing GDF data is implemented in Octave/Matlab and C/C++ and provided through BioSig - an free and open source software library for biomedical signal processing. BioSig privides also converters from various data formats to GDF, and a viewing and scoring software.
Asymptotic Capacity Bounds for Wireless Networks with Non-Uniform Traffic
Venue: arXiv cs.NI 2013
Year: 2013

We develop bounds on the capacity of wireless networks when the traffic is non-uniform, i.e., not all nodes are required to receive and send similar volumes of traffic. Our results are asymptotic, i.e., they hold with probability going to unity as the number of nodes goes to infinity. We study \emph{(i)} asymmetric networks, where the numbers of sources and destinations of traffic are unequal, \emph{(ii)} multicast networks, in which each created packet has multiple destinations, \emph{(iii)} cluster networks, that consist of clients and a limited number of cluster heads, and each client wants to communicate with any of the cluster heads, and \emph{(iv)} hybrid networks, in which the nodes are supported by a limited infrastructure. Our findings quantify the fundamental capabilities of these wireless networks to handle traffic bottlenecks, and point to correct design principles that achieve the capacity without resorting to overly complicated protocols.
Compact Labelings For Efficient First-Order Model-Checking
Venue: arXiv cs.DS 2014
Year: 2014

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is \emph{nicely locally cwd-decomposable}. This notion generalizes that of a \emph{nicely locally tree-decomposable} class. The graphs of such classes can be covered by graphs of bounded \emph{clique-width} with limited overlaps. We also consider such labelings for \emph{bounded} first-order formulas on graph classes of \emph{bounded expansion}. Some of these results are extended to counting queries.
Fixed-point tile sets and their applications
Venue: arXiv cs.CC 2014
Year: 2014

An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals). We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. This construction it rather flexible, so it can be used in many ways: we show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, characterize effectively closed 1D subshift it terms of 2D shifts of finite type (improvement of a result by M. Hochman), to construct a tile set which has only complex tilings, and to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. For the latter we develop a hierarchical classification of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: there exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed.
A Dynamic Near-Optimal Algorithm for Online Linear Programming
Venue: arXiv cs.DS 2014
Year: 2014

A natural optimization model that formulates many online resource allocation and revenue management problems is the online linear program (LP) in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs and the goal is to maximize the overall objective function. In this paper, we provide a near-optimal algorithm for this general class of online problems under the assumption of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Due to the feature of dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst-case example showing that the performance of our algorithm is near-optimal.
On a Relation Between the Integral Image Algorithm and Calculus
Venue: arXiv cs.DM 2014
Year: 2014

The Integral Image algorithm is often applied in tasks that require efficient integration over images, such as object detection. In this paper we discuss theoretical aspects of the algorithm's continuous version. We suggest to define the coefficients at the formulation of the algorithm by applying a novel kind of discrete derivative. Based on that operator we build a novel integration method over curves in the plane, and apply it in a theorem that extends the algorithm to general continuous domains.
Split digraphs
Venue: arXiv cs.DM 2014
Year: 2014

We generalize the class of split graphs to the directed case and show that these split digraphs can be identified from their degree sequences. The first degree sequence characterization is an extension of the concept of splittance to directed graphs, while the second characterization says a digraph is split if and only if its degree sequence satisfies one of the Fulkerson inequalities (which determine when an integer-pair sequence is digraphic) with equality.
Observable dynamics and coordinate systems for automotive target tracking
Venue: arXiv cs.RO 2014
Year: 2014

We investigate several coordinate systems and dynamical vector fields for target tracking to be used in driver assistance systems. We show how to express the discrete dynamics of maneuvering target vehicles in arbitrary coordinates starting from the target's and the own (ego) vehicle's assumed dynamical model in global coordinates. We clarify the notion of "ego compensation" and show how non-inertial effects are to be included when using a body-fixed coordinate system for target tracking. We finally compare the tracking error of different combinations of target tracking coordinates and dynamical vector fields for simulated data.
Vertex Sparsifiers: New Results from Old Techniques
Venue: arXiv cs.DS 2014
Year: 2014

Given a capacitated graph $G = (V,E)$ and a set of terminals $K \subseteq V$, how should we produce a graph $H$ only on the terminals $K$ so that every (multicommodity) flow between the terminals in $G$ could be supported in $H$ with low congestion, and vice versa? (Such a graph $H$ is called a flow-sparsifier for $G$.) What if we want $H$ to be a "simple" graph? What if we allow $H$ to be a convex combination of simple graphs? Improving on results of Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier $H$ that maintains congestion up to a factor of $O(\log k/\log \log k)$, where $k = |K|$, (b) a convex combination of trees over the terminals $K$ that maintains congestion up to a factor of $O(\log k)$, and (c) for a planar graph $G$, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in $G$. Moreover, this result extends to minor-closed families of graphs. Our improved bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems.
On Unit Distances in a Convex Polygon
Venue: arXiv cs.CG 2014
Year: 2014

In 1959, Erdős and Moser asked for the maximum number of unit distances that may be formed among the vertices of a convex $n$-gon; until now, the best known upper bound has been $2πn \log_2 n + O(n)$, achieved by Füredi in 1990. In this paper, we examine two properties that any convex polygon must satisfy and use them to prove several new facts related to the question posed by Erdős and Moser. In particular, we improve on Füredi's result, and instead obtain a bound of $n \log_2 n + O(n)$; we exhibit a class of `cycles' formed by unit distances that are forbidden in convex polygons; and we provide a lower bound that shows the limitations of our methods. The second result addresses a question asked by Fishburn and Reeds regarding the possible configurations of vertices that form a convex polygon.
Unconditionally Secure Computation on Large Distributed Databases with Vanishing Cost
Venue: arXiv cs.CR 2014
Year: 2014

Consider a network of k parties, each holding a long sequence of n entries (a database), with minimum vertex-cut greater than t. We show that any empirical statistic across the network of databases can be computed by each party with perfect privacy, against any set of t < k/2 passively colluding parties, such that the worst-case distortion and communication cost (in bits per database entry) both go to zero as n, the number of entries in the databases, goes to infinity. This is based on combining a striking dimensionality reduction result for random sampling with unconditionally secure multi-party computation protocols.
Minimum Pseudoweight Analysis of 3-Dimensional Turbo Codes
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we consider pseudocodewords of (relaxed) linear programming (LP) decoding of 3-dimensional turbo codes (3D-TCs). We present a relaxed LP decoder for 3D-TCs, adapting the relaxed LP decoder for conventional turbo codes proposed by Feldman in his thesis. We show that the 3D-TC polytope is proper and $C$-symmetric, and make a connection to finite graph covers of the 3D-TC factor graph. This connection is used to show that the support set of any pseudocodeword is a stopping set of iterative decoding of 3D-TCs using maximum a posteriori constituent decoders on the binary erasure channel. Furthermore, we compute ensemble-average pseudoweight enumerators of 3D-TCs and perform a finite-length minimum pseudoweight analysis for small cover degrees. Also, an explicit description of the fundamental cone of the 3D-TC polytope is given. Finally, we present an extensive numerical study of small-to-medium block length 3D-TCs, which shows that 1) typically (i.e., in most cases) when the minimum distance $d_{\rm min}$ and/or the stopping distance $h_{\rm min}$ is high, the minimum pseudoweight (on the additive white Gaussian noise channel) is strictly smaller than both the $d_{\rm min}$ and the $h_{\rm min}$, and 2) the minimum pseudoweight grows with the block length, at least for small-to-medium block lengths.
Mobile Computing in Digital Ecosystems: Design Issues and Challenges
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we argue that the set of wireless, mobile devices (e.g., portable telephones, tablet PCs, GPS navigators, media players) commonly used by human users enables the construction of what we term a digital ecosystem, i.e., an ecosystem constructed out of so-called digital organisms (see below), that can foster the development of novel distributed services. In this context, a human user equipped with his/her own mobile devices, can be though of as a digital organism (DO), a subsystem characterized by a set of peculiar features and resources it can offer to the rest of the ecosystem for use from its peer DOs. The internal organization of the DO must address issues of management of its own resources, including power consumption. Inside the DO and among DOs, peer-to-peer interaction mechanisms can be conveniently deployed to favor resource sharing and data dissemination. Throughout this paper, we show that most of the solutions and technologies needed to construct a digital ecosystem are already available. What is still missing is a framework (i.e., mechanisms, protocols, services) that can support effectively the integration and cooperation of these technologies. In addition, in the following we show that that framework can be implemented as a middleware subsystem that enables novel and ubiquitous forms of computation and communication. Finally, in order to illustrate the effectiveness of our approach, we introduce some experimental results we have obtained from preliminary implementations of (parts of) that subsystem.
Fast restoration of natural images corrupted by high-density impulse noise
Venue: arXiv cs.MM 2014
Year: 2014

In this paper, we suggest a general model for the fixed-valued impulse noise and propose a two-stage method for high density noise suppression while preserving the image details. In the first stage, we apply an iterative impulse detector, exploiting the image entropy, to identify the corrupted pixels and then employ an Adaptive Iterative Mean filter to restore them. The filter is adaptive in terms of the number of iterations, which is different for each noisy pixel, according to the Euclidean distance from the nearest uncorrupted pixel. Experimental results show that the proposed filter is fast and outperforms the best existing techniques in both objective and subjective performance measures.
Data Stability in Clustering: A Closer Look
Venue: arXiv cs.LG 2014
Year: 2014

We consider the model introduced by Bilu and Linial (2010), who study problems for which the optimal clustering does not change when distances are perturbed. They show that even when a problem is NP-hard, it is sometimes possible to obtain efficient algorithms for instances resilient to certain multiplicative perturbations, e.g. on the order of $O(\sqrt{n})$ for max-cut clustering. Awasthi et al. (2010) consider center-based objectives, and Balcan and Liang (2011) analyze the $k$-median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations. Here, we are motivated by the question of to what extent these assumptions can be relaxed while allowing for efficient algorithms. We show there is little room to improve these results by giving NP-hardness lower bounds for both the $k$-median and min-sum objectives. On the other hand, we show that constant multiplicative resilience parameters can be so strong as to make the clustering problem trivial, leaving only a narrow range of resilience parameters for which clustering is interesting. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results provide a close examination of the consequences of assuming stability in data.
Capacity Analysis of Linear Operator Channels over Finite Fields
Venue: arXiv cs.IT 2014
Year: 2014

Motivated by communication through a network employing linear network coding, capacities of linear operator channels (LOCs) with arbitrarily distributed transfer matrices over finite fields are studied. Both the Shannon capacity $C$ and the subspace coding capacity $C_{\text{SS}}$ are analyzed. By establishing and comparing lower bounds on $C$ and upper bounds on $C_{\text{SS}}$, various necessary conditions and sufficient conditions such that $C=C_{\text{SS}}$ are obtained. A new class of LOCs such that $C=C_{\text{SS}}$ is identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that $C_{\text{SS}}$ is strictly less than $C$ for a broad class of LOCs. In general, an optimal subspace coding scheme is difficult to find because it requires to solve the maximization of a non-concave function. However, for a LOC with a unique subspace degradation, $C_{\text{SS}}$ can be obtained by solving a convex optimization problem over rank distribution. Classes of LOCs with a unique subspace degradation are characterized. Since LOCs with uniform-given-rank transfer matrices have unique subspace degradations, some existing results on LOCs with uniform-given-rank transfer matrices are explained from a more general way.
Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we address the following matrix recovery problem: suppose we are given a set of data points containing two parts, one part consists of samples drawn from a union of multiple subspaces and the other part consists of outliers. We do not know which data points are outliers, or how many outliers there are. The rank and number of the subspaces are unknown either. Can we detect the outliers and segment the samples into their right subspaces, efficiently and exactly? We utilize a so-called {\em Low-Rank Representation} (LRR) method to solve this problem, and prove that under mild technical conditions, any solution to LRR exactly recovers the row space of the samples and detect the outliers as well. Since the subspace membership is provably determined by the row space, this further implies that LRR can perform exact subspace segmentation and outlier detection, in an efficient way.
Nouvelle représentation concise exacte des motifs corrélés rares : Application à la détection d'intrusions
Venue: arXiv cs.DB 2014
Year: 2014

Correlated rare pattern mining is an interesting issue in Data mining. In this respect, the set of correlated rare patterns w.r.t. to the bond correlation measure was studied in a recent work, in which the RCPR concise exact representation of the set of correlated rare patterns was proposed. However, none algorithm was proposed in order to mine this representation and none experiment was carried out to evaluate it. In this paper, we introduce the new RcprMiner algorithm allowing an efficient extraction of RCPR. We also present the IsRCP algorithm allowing the query of the RCPR representation in addition to the RCPRegeneration algorithm allowing the regeneration of the whole set RCP of rare correlated patterns starting from this representation. The carried out experiments highlight interesting compactness rates offered by RCPR. The effectiveness of the proposed classification method, based on generic rare correlated association rules derived from RCPR, has also been proved in the context of intrusion detection.