OpenRaiser/Intern-Atlas huggingface dataset:
On Stability Property of Probability Laws with Respect to Small Violations of Algorithmic Randomness
Venue: arXiv cs.CC 2014
Year: 2014

We study a stability property of probability laws with respect to small violations of algorithmic randomness. A sufficient condition of stability is presented in terms of Schnorr tests of algorithmic randomness. Most probability laws, like the strong law of large numbers, the law of iterated logarithm, and even Birkhoff's pointwise ergodic theorem for ergodic transformations, are stable in this sense. Nevertheless, the phenomenon of instability occurs in ergodic theory. Firstly, the stability property of the Birkhoff's ergodic theorem is non-uniform. Moreover, a computable non-ergodic measure preserving transformation can be constructed such that ergodic theorem is non-stable. We also show that any universal data compression scheme is also non-stable with respect to the class of all computable ergodic measures.
The 7 Habits of Highly Effective Research Communicators
Venue: arXiv cs.DL 2014
Year: 2014

The emergence of Web 2.0 and simultaneously Library 2.0 platforms has helped the library and information professionals to outreach to new audiences beyond their physical boundaries. In a globalized society, information becomes very useful resource for socio-economic empowerment of marginalized communities, economic prosperity of common citizens, and knowledge enrichment of liberated minds. Scholarly information becomes both developmental and functional for researchers working towards advancement of knowledge. We must recognize a relay of information flow and information ecology while pursuing scholarly research. Published scholarly literatures we consult that help us in creation of new knowledge. Similarly, our published scholarly works should be outreached to future researchers for regeneration of next dimension of knowledge. Fortunately, present day research communicators have many freely available personalized digital tools to outreach to globalized research audiences having similar research interests. These tools and techniques, already adopted by many researchers in different subject areas across the world, should be enthusiastically utilized by LIS researchers in South Asia for global dissemination of their scholarly research works. This newly found enthusiasm will soon become integral part of the positive habits and cultural practices of research communicators in LIS domain.
Clear, Concise and Effective UI: Opinion and Suggestions
Venue: arXiv cs.HC 2014
Year: 2014

The most important aspect of any Software is the operability for the intended audience. This factor of operability is encompassed in the user interface, which serves as the only window to the features of the system. It is thus essential that the User Interface provided is robust, concise and lucid. Presently there are no properly defined rules or guidelines for user interface design enabling a perfect design, since such a system cannot be perceived. This article aims at providing suggestions in the design of the User Interface, which would make it easier for the user to navigate through the system features and also the developers to guide the users towards better utilization of the features.
EquiNMF: Graph Regularized Multiview Nonnegative Matrix Factorization
Venue: arXiv cs.LG 2014
Year: 2014

Nonnegative matrix factorization (NMF) methods have proved to be powerful across a wide range of real-world clustering applications. Integrating multiple types of measurements for the same objects/subjects allows us to gain a deeper understanding of the data and refine the clustering. We have developed a novel Graph-reguarized multiview NMF-based method for data integration called EquiNMF. The parameters for our method are set in a completely automated data-specific unsupervised fashion, a highly desirable property in real-world applications. We performed extensive and comprehensive experiments on multiview imaging data. We show that EquiNMF consistently outperforms other single-view NMF methods used on concatenated data and multi-view NMF methods with different types of regularizations.
Facility location problems in the constant work-space read-only memory model
Venue: arXiv cs.DS 2014
Year: 2014

Facility location problems are captivating both from theoretical and practical point of view. In this paper, we study some fundamental facility location problems from the space-efficient perspective. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available during the computation. This {\em constant-work-space model} is well-motivated for handling big-data as well as for computing in smart portable devices with small amount of extra-space. First, we propose a strategy to implement prune-and-search in this model. As a warm up, we illustrate this technique for finding the Euclidean 1-center constrained on a line for a set of points in $\IR^2$. This method works even if the input is given in a sequential access read-only memory. Using this we show how to compute (i) the Euclidean 1-center of a set of points in $\IR^2$, and (ii) the weighted 1-center and weighted 2-center of a tree network. The running time of all these algorithms are $O(n~poly(\log n))$. While the result of (i) gives a positive answer to an open question asked by Asano, Mulzer, Rote and Wang in 2011, the technique used can be applied to other problems which admit solutions by prune-and-search paradigm. For example, we can apply the technique to solve two and three dimensional linear programming in $O(n~poly(\log n))$ time in this model. To the best of our knowledge, these are the first sub-quadratic time algorithms for all the above mentioned problems in the constant-work-space model. We also present optimal linear time algorithms for finding the centroid and weighted median of a tree in this model.
On Analysis And Generation Of Biologically Important Boolean Functions
Venue: arXiv cs.SY 2014
Year: 2014

Boolean networks are used to model biological networks such as gene regulatory networks. Often Boolean networks show very chaotic behavior which is sensitive to any small perturbations.In order to reduce the chaotic behavior and to attain stability in the gene regulatory network,nested canalizing functions(NCF)are best suited NCF and its variants have a wide range of applications in system biology. Previously many work were done on the application of canalizing functions but there were fewer methods to check if any arbitrary Boolean function is canalizing or not. In this paper, by using Karnaugh Map this problem gas been solved and also it has been shown that when the canalizing functions of n variable is given, all the canalizing functions of n+1 variable could be generated by the method of concatenation. In this paper we have uniquely identified the number of NCFs having a particular hamming distance (H.D) generated by each variable x as starting canalizing input. Partially nested canalizing functions of 4 variables have also been studied in this paper. Keywords: Karnaugh Map, Canalizing function, Nested canalizing function, Partially nested canalizing function,concatenation
Performance analysis of a 240 thread tournament level MCTS Go program on the Intel Xeon Phi
Venue: arXiv cs.PF 2014
Year: 2014

In 2013 Intel introduced the Xeon Phi, a new parallel co-processor board. The Xeon Phi is a cache-coherent many-core shared memory architecture claiming CPU-like versatility, programmability, high performance, and power efficiency. The first published micro-benchmark studies indicate that many of Intel's claims appear to be true. The current paper is the first study on the Phi of a complex artificial intelligence application. It contains an open source MCTS application for playing tournament quality Go (an oriental board game). We report the first speedup figures for up to 240 parallel threads on a real machine, allowing a direct comparison to previous simulation studies. After a substantial amount of work, we observed that performance scales well up to 32 threads, largely confirming previous simulation results of this Go program, although the performance surprisingly deteriorates between 32 and 240 threads. Furthermore, we report (1) unexpected performance anomalies between the Xeon Phi and Xeon CPU for small problem sizes and small numbers of threads, and (2) that performance is sensitive to scheduling choices. Achieving good performance on the Xeon Phi for complex programs is not straightforward; it requires a deep understanding of (1) search patterns, (2) of scheduling, and (3) of the architecture and its many cores and caches. In practice, the Xeon Phi is less straightforward to program for than originally envisioned by Intel.
A bound on a convexity measure for point sets
Venue: arXiv cs.CG 2014
Year: 2014

A planar point set is in convex position precisely when it has a convex polygonization, that is, a polygonization with maximum interior angle measure at most π. We can thus talk about the convexity of a set of points in terms of the minimum, taken over all polygonizations, of the maximum interior angle. The main result presented here is a nontrivial combinatorial upper bound of this min-max value in terms of the number of points in the set. Motivated by a particular construction, we also pose a natural conjecture for the best upper bound.
A Survey and Taxonomy of Urban Traffic Management: Towards Vehicular Networks
Venue: arXiv cs.NI 2014
Year: 2014

Urban Traffic Management (UTM) topics have been tackled since long time, mainly by civil engineers and by city planners. The introduction of new communication technologies - such as cellular systems, satellite positioning systems and inter-vehicle communications - has significantly changed the way researchers deal with UTM issues. In this survey, we provide a review and a classification of how UTM has been addressed in the literature. We start from the recent achievements of "classical" approaches to urban traffic estimation and optimization, including methods based on the analysis of data collected by fixed sensors (e.g., cameras and radars), as well as methods based on information provided by mobile phones, such as Floating Car Data (FCD). Afterwards, we discuss urban traffic optimization, presenting the most recent works on traffic signal control and vehicle routing control. Then, after recalling the main concepts of Vehicular Ad-Hoc Networks (VANETs), we classify the different VANET-based approaches to UTM, according to three categories ("pure" VANETs, hybrid vehicular-sensor networks and hybrid vehicular-cellular networks), while illustrating the major research issues for each of them. The main objective of this survey is to provide a comprehensive view on UTM to researchers with focus on VANETs, in order to pave the way for the design and development of novel techniques for mitigating urban traffic problems, based on inter-vehicle communications.
Adaptive Content Control for Communication amongst Cooperative Automated Vehicles
Venue: arXiv cs.NI 2014
Year: 2014

Cooperative automated vehicles exchange information to assist each other in creating a more precise and extended view of their surroundings, with the aim of improving automated-driving decisions. This paper addresses the need for scalable communication among these vehicles. To this end, a general communication framework is proposed through which automated cars exchange information derived from multi-resolution maps created using their local sensing modalities. This method can extend the region visible to a car beyond the area directly sensed by its own sensors. An adaptive, probabilistic, distance-dependent strategy is proposed that controls the content of the messages exchanged among vehicles based on performance measures associated with the load on the communication channel.
Projective Root-Locus: An Extension of Root-Locus Plot to the Projective Plane
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we present an extension of the classical Root-Locus (RL) method where the points are calculated in the real projective plane instead of the conventional affine real plane; we denominate this extension of the Root-Locus as "Projective Root-Locus (PjRL)". To plot the PjRL we use the concept of "Gnomonic Projection" in order to have a representation of the projective real plane as a simi-sphere of radius one in ${\mathbb R}^3$. We will see that the PjRL reduces to the RL in the affine $XY$ plane, but also we can plot the RL onto another affine component of the projective plane, like $ZY$ affine plane for instance, to obtain what we denominate complementary plots of the conventional RL. We also show that with the PjRL the points at infinity of the RL can be computed as solutions of a set algebraic equations.
Real-time Crowd Tracking using Parameter Optimized Mixture of Motion Models
Venue: arXiv cs.CV 2014
Year: 2014

We present a novel, real-time algorithm to track the trajectory of each pedestrian in moderately dense crowded scenes. Our formulation is based on an adaptive particle-filtering scheme that uses a combination of various multi-agent heterogeneous pedestrian simulation models. We automatically compute the optimal parameters for each of these different models based on prior tracked data and use the best model as motion prior for our particle-filter based tracking algorithm. We also use our "mixture of motion models" for adaptive particle selection and accelerate the performance of the online tracking algorithm. The motion model parameter estimation is formulated as an optimization problem, and we use an approach that solves this combinatorial optimization problem in a model independent manner and hence scalable to any multi-agent pedestrian motion model. We evaluate the performance of our approach on different crowd video datasets and highlight the improvement in accuracy over homogeneous motion models and a baseline mean-shift based tracker. In practice, our formulation can compute trajectories of tens of pedestrians on a multi-core desktop CPU in in real time and offer higher accuracy as compared to prior real time pedestrian tracking algorithms.
Voting for Deceptive Opinion Spam Detection
Venue: arXiv cs.CL 2014
Year: 2014

Consumers' purchase decisions are increasingly influenced by user-generated online reviews. Accordingly, there has been growing concern about the potential for posting deceptive opinion spam fictitious reviews that have been deliberately written to sound authentic, to deceive the readers. Existing approaches mainly focus on developing automatic supervised learning based methods to help users identify deceptive opinion spams. This work, we used the LSI and Sprinkled LSI technique to reduce the dimension for deception detection. We make our contribution to demonstrate what LSI is capturing in latent semantic space and reveal how deceptive opinions can be recognized automatically from truthful opinions. Finally, we proposed a voting scheme which integrates different approaches to further improve the classification performance.
Similarity of closed polygonal curves in Frechet metric
Venue: arXiv cs.CG 2014
Year: 2014

The article analyzes similarity of closed polygonal curves in Frechet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm that determines whether the Frechet distance between two closed polygonal curves with m and n vertices is less than a given number is described. The described algorithm takes O(mn) time whereas the previously known algorithms take O(mn log(mn)) time.
The Role of Emotions in Propagating Brands in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

A key aspect of word of mouth marketing are emotions. Emotions in texts help propagating messages in conventional advertising. In word of mouth scenarios, emotions help to engage consumers and incite to propagate the message further. While the function of emotions in offline marketing in general and word of mouth marketing in particular is rather well understood, online marketing can only offer a limited view on the function of emotions. In this contribution we seek to close this gap. We therefore investigate how emotions function in social media. To do so, we collected more than 30,000 brand marketing messages from the Google+ social networking site. Using state of the art computational linguistics classifiers, we compute the sentiment of these messages. Starting out with Poisson regression-based baseline models, we seek to replicate earlier findings using this large data set. We extend upon earlier research by computing multi-level mixed effects models that compare the function of emotions across different industries. We find that while the well known notion of activating emotions propagating messages holds in general for our data as well. But there are significant differences between the observed industries.
Resolute: An Assurance Case Language for Architecture Models
Venue: arXiv cs.SE 2014
Year: 2014

Arguments about the safety, security, and correctness of a complex system are often made in the form of an assurance case. An assurance case is a structured argument, often represented with a graphical interface, that presents and supports claims about a system's behavior. The argument may combine different kinds of evidence to justify its top level claim. While assurance cases deliver some level of guarantee of a system's correctness, they lack the rigor that proofs from formal methods typically provide. Furthermore, changes in the structure of a model during development may result in inconsistencies between a design and its assurance case. Our solution is a framework for automatically generating assurance cases based on 1) a system model specified in an architectural design language, 2) a set of logical rules expressed in a domain specific language that we have developed, and 3) the results of other formal analyses that have been run on the model. We argue that the rigor of these automatically generated assurance cases exceeds those of traditional assurance case arguments because of their more formal logical foundation and direct connection to the architectural model.
Automatic Error Localization for Software using Deductive Verification
Venue: arXiv cs.LO 2014
Year: 2014

Even competent programmers make mistakes. Automatic verification can detect errors, but leaves the frustrating task of finding the erroneous line of code to the user. This paper presents an automatic approach for identifying potential error locations in software. It is based on a deductive verification engine, which detects errors in functions annotated with pre- and post-conditions. Using an automatic theorem prover, our approach finds expressions in the code that can be modified such that the program satisfies its specification. Scalability is achieved by analyzing each function in isolation. We have implemented our approach in the widely used Frama-C framework and present first experimental results. This is an extended version of [8], featuring an additional appendix.
Position Auctions with Externalities and Brand Effects
Venue: arXiv cs.GT 2014
Year: 2014

This paper presents models for predicted click-through rates in position auctions that take into account two possibilities that are not normally considered---that the identities of ads shown in other positions may affect the probability that an ad in a particular position receives a click (externalities) and that some ads may be less adversely affected by being shown in a lower position than others (brand effects). We present a general axiomatic methodology for how click probabilities are affected by the qualities of the ads in the other positions, and illustrate that using these axioms will increase revenue as long as higher quality ads tend to be ranked ahead of lower quality ads. We also present appropriate algorithms for selecting the optimal allocation of ads when predicted click-through rates are governed by either the models of externalities or brand effects that we consider. Finally, we analyze the performance of a greedy algorithm of ranking the ads by their expected cost-per-1000-impressions bids when the true click-through rates are governed by our model of predicted click-through rates with brand effects and illustrate that such an algorithm will potentially cost as much as half of the total possible social welfare.
Collapsed Variational Bayes Inference of Infinite Relational Model
Venue: arXiv cs.LG 2014
Year: 2014

The Infinite Relational Model (IRM) is a probabilistic model for relational data clustering that partitions objects into clusters based on observed relationships. This paper presents Averaged CVB (ACVB) solutions for IRM, convergence-guaranteed and practically useful fast Collapsed Variational Bayes (CVB) inferences. We first derive ordinary CVB and CVB0 for IRM based on the lower bound maximization. CVB solutions yield deterministic iterative procedures for inferring IRM given the truncated number of clusters. Our proposal includes CVB0 updates of hyperparameters including the concentration parameter of the Dirichlet Process, which has not been studied in the literature. To make the CVB more practically useful, we further study the CVB inference in two aspects. First, we study the convergence issues and develop a convergence-guaranteed algorithm for any CVB-based inferences called ACVB, which enables automatic convergence detection and frees non-expert practitioners from difficult and costly manual monitoring of inference processes. Second, we present a few techniques for speeding up IRM inferences. In particular, we describe the linear time inference of CVB0, allowing the IRM for larger relational data uses. The ACVB solutions of IRM showed comparable or better performance compared to existing inference methods in experiments, and provide deterministic, faster, and easier convergence detection.
Identification of core-periphery structure in networks
Venue: arXiv cs.SI 2014
Year: 2014

Many networks can be usefully decomposed into a dense core plus an outlying, loosely-connected periphery. Here we propose an algorithm for performing such a decomposition on empirical network data using methods of statistical inference. Our method fits a generative model of core-periphery structure to observed data using a combination of an expectation--maximization algorithm for calculating the parameters of the model and a belief propagation algorithm for calculating the decomposition itself. We find the method to be efficient, scaling easily to networks with a million or more nodes and we test it on a range of networks, including real-world examples as well as computer-generated benchmarks, for which it successfully identifies known core-periphery structure with low error rate. We also demonstrate that the method is immune from the detectability transition observed in the related community detection problem, which prevents the detection of community structure when that structure is too weak. There is no such transition for core-periphery structure, which is detectable, albeit with some statistical error, no matter how weak it is.