OpenRaiser/Intern-Atlas huggingface dataset:
Learning, Generalization, and Functional Entropy in Random Automata Networks
Venue: arXiv cs.NE 2013
Year: 2013

It has been shown \citep{broeck90:physicalreview,patarnello87:europhys} that feedforward Boolean networks can learn to perform specific simple tasks and generalize well if only a subset of the learning examples is provided for learning. Here, we extend this body of work and show experimentally that random Boolean networks (RBNs), where both the interconnections and the Boolean transfer functions are chosen at random initially, can be evolved by using a state-topology evolution to solve simple tasks. We measure the learning and generalization performance, investigate the influence of the average node connectivity $K$, the system size $N$, and introduce a new measure that allows to better describe the network's learning and generalization behavior. We show that the connectivity of the maximum entropy networks scales as a power-law of the system size $N$. Our results show that networks with higher average connectivity $K$ (supercritical) achieve higher memorization and partial generalization. However, near critical connectivity, the networks show a higher perfect generalization on the even-odd task.
Understanding the Predictive Power of Computational Mechanics and Echo State Networks in Social Media
Venue: arXiv cs.SI 2013
Year: 2013

There is a large amount of interest in understanding users of social media in order to predict their behavior in this space. Despite this interest, user predictability in social media is not well-understood. To examine this question, we consider a network of fifteen thousand users on Twitter over a seven week period. We apply two contrasting modeling paradigms: computational mechanics and echo state networks. Both methods attempt to model the behavior of users on the basis of their past behavior. We demonstrate that the behavior of users on Twitter can be well-modeled as processes with self-feedback. We find that the two modeling approaches perform very similarly for most users, but that they differ in performance on a small subset of the users. By exploring the properties of these performance-differentiated users, we highlight the challenges faced in applying predictive models to dynamic social data.
Competency Tracking for English as a Second or Foreign Language Learners
Venue: arXiv cs.CL 2013
Year: 2013

My system utilizes the outcomes feature found in Moodle and other learning content management systems (LCMSs) to keep track of where students are in terms of what language competencies they have mastered and the competencies they need to get where they want to go. These competencies are based on the Common European Framework for (English) Language Learning. This data can be available for everyone involved with a given student's progress (e.g. educators, parents, supervisors and the students themselves). A given student's record of past accomplishments can also be meshed with those of his classmates. Not only are a student's competencies easily seen and tracked, educators can view competencies of a group of students that were achieved prior to enrollment in the class. This should make curriculum decision making easier and more efficient for educators.
A Study of Library Migration in Java Software
Venue: arXiv cs.SE 2013
Year: 2013

Software intensively depends on external libraries whose relevance may change during its life cycle. As a consequence, software developers must periodically reconsider the libraries they depend on, and must think about \textit{library migration}. To our knowledge, no existing study has been done to understand library migration although it is known to be an expensive maintenance task. Are library migrations frequent? For which software are they performed and when? For which libraries? For what reasons? The purpose of this paper is to answer these questions with the intent to help software developers that have to replace their libraries. To that extent, we have performed a statistical analysis of a large set of open source software to mine their library migration. To perform this analysis we have defined an approach that identifies library migrations in a pseudo-automatic fashion by analyzing the source code of the software. We have implemented this approach for the Java programming language and applied it on Java Open Source Software stored in large hosting services. The main result of our study is that library migration is not a frequent practice but depends a lot on the nature of the software as well as the nature of the libraries.
Social Ranking Techniques for the Web
Venue: arXiv cs.SI 2013
Year: 2013

The proliferation of social media has the potential for changing the structure and organization of the web. In the past, scientists have looked at the web as a large connected component to understand how the topology of hyperlinks correlates with the quality of information contained in the page and they proposed techniques to rank information contained in web pages. We argue that information from web pages and network data on social relationships can be combined to create a personalized and socially connected web. In this paper, we look at the web as a composition of two networks, one consisting of information in web pages and the other of personal data shared on social media web sites. Together, they allow us to analyze how social media tunnels the flow of information from person to person and how to use the structure of the social network to rank, deliver, and organize information specifically for each individual user. We validate our social ranking concepts through a ranking experiment conducted on web pages that users shared on Google Buzz and Twitter.
Robust Reduced-Rank Adaptive Processing Based on Parallel Subgradient Projection and Krylov Subspace Techniques
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a novel reduced-rank adaptive filtering algorithm by blending the idea of the Krylov subspace methods with the set-theoretic adaptive filtering framework. Unlike the existing Krylov-subspace-based reduced-rank methods, the proposed algorithm tracks the optimal point in the sense of minimizing the \sinq{true} mean square error (MSE) in the Krylov subspace, even when the estimated statistics become erroneous (e.g., due to sudden changes of environments). Therefore, compared with those existing methods, the proposed algorithm is more suited to adaptive filtering applications. The algorithm is analyzed based on a modified version of the adaptive projected subgradient method (APSM). Numerical examples demonstrate that the proposed algorithm enjoys better tracking performance than the existing methods for the interference suppression problem in code-division multiple-access (CDMA) systems as well as for simple system identification problems.
A null space analysis of the L1 synthesis method in dictionary-based compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

An interesting topic in compressed sensing aims to recover signals with sparse representations in a dictionary. Recently the performance of the L1-analysis method has been a focus, while some fundamental problems for the L1-synthesis method are still unsolved. For example, what are the conditions for it to stably recover compressible signals under noise? Whether coherent dictionaries allow the existence of sensing matrices that guarantee good performances of the L1-synthesis method? To answer these questions, we build up a framework for the L1-synthesis method. In particular, we propose a dictionary-based null space property DNSP which, to the best of our knowledge, is the first sufficient and necessary condition for the success of L1-synthesis without measurement noise. With this new property, we show that when the dictionary D is full spark, it cannot be too coherent otherwise the method fails for all sensing matrices. We also prove that in the real case, DNSP is equivalent to the stability of L1-synthesis under noise.
Group testing algorithms: bounds and simulations
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of non-adaptive noiseless group testing of $N$ items of which $K$ are defective. We describe four detection algorithms: the COMP algorithm of Chan et al.; two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective; and an essentially optimal but computationally difficult algorithm called SSS. By considering the asymptotic rate of these algorithms with Bernoulli designs we see that DD outperforms COMP, that DD is essentially optimal in regimes where $K \geq \sqrt N$, and that no algorithm with a nonadaptive Bernoulli design can perform as well as the best non-random adaptive designs when $K > N^{0.35}$. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger $K$.
Multi-Structural Signal Recovery for Biomedical Compressive Sensing
Venue: arXiv cs.IT 2013
Year: 2013

Compressive sensing has shown significant promise in biomedical fields. It reconstructs a signal from sub-Nyquist random linear measurements. Classical methods only exploit the sparsity in one domain. A lot of biomedical signals have additional structures, such as multi-sparsity in different domains, piecewise smoothness, low rank, etc. We propose a framework to exploit all the available structure information. A new convex programming problem is generated with multiple convex structure-inducing constraints and the linear measurement fitting constraint. With additional a priori information for solving the underdetermined system, the signal recovery performance can be improved. In numerical experiments, we compare the proposed method with classical methods. Both simulated data and real-life biomedical data are used. Results show that the newly proposed method achieves better reconstruction accuracy performance in term of both L1 and L2 errors.
Measurements of collective machine intelligence
Venue: arXiv cs.AI 2013
Year: 2013

Independent from the still ongoing research in measuring individual intelligence, we anticipate and provide a framework for measuring collective intelligence. Collective intelligence refers to the idea that several individuals can collaborate in order to achieve high levels of intelligence. We present thus some ideas on how the intelligence of a group can be measured and simulate such tests. We will however focus here on groups of artificial intelligence agents (i.e., machines). We will explore how a group of agents is able to choose the appropriate problem and to specialize for a variety of tasks. This is a feature which is an important contributor to the increase of intelligence in a group (apart from the addition of more agents and the improvement due to common decision making). Our results reveal some interesting results about how (collective) intelligence can be modeled, about how collective intelligence tests can be designed and about the underlying dynamics of collective intelligence. As it will be useful for our simulations, we provide also some improvements of the threshold allocation model originally used in the area of swarm intelligence but further generalized here.
Software for Evaluating Relevance of Steps in Algebraic Transformations
Venue: arXiv cs.SC 2013
Year: 2013

Students of our department solve algebraic exercises in mathematical logic in a computerized environment. They construct transformations step by step and the program checks the syntax, equivalence of expressions and completion of the task. With our current project, we add a program component for checking relevance of the steps.
New Mathematical and Algorithmic Schemes for Pattern Classification with Application to the Identification of Writers of Important Ancient Documents
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, a novel approach is introduced for classifying curves into proper families, according to their similarity. First, a mathematical quantity we call plane curvature is introduced and a number of propositions are stated and proved. Proper similarity measures of two curves are introduced and a subsequent statistical analysis is applied. First, the efficiency of the curve fitting process has been tested on 2 shapes datasets of reference. Next, the methodology has been applied to the very important problem of classifying 23 Byzantine codices and 46 Ancient inscriptions to their writers, thus achieving correct dating of their content. The inscriptions have been attributed to ten individual hands and the Byzantine codices to four writers.
The DeLiVerMATH project - Text analysis in mathematics
Venue: arXiv cs.CL 2013
Year: 2013

A high-quality content analysis is essential for retrieval functionalities but the manual extraction of key phrases and classification is expensive. Natural language processing provides a framework to automatize the process. Here, a machine-based approach for the content analysis of mathematical texts is described. A prototype for key phrase extraction and classification of mathematical texts is presented.
Fractal and Mathematical Morphology in Intricate Comparison between Tertiary Protein Structures
Venue: arXiv cs.CG 2013
Year: 2013

Intricate comparison between two given tertiary structures of proteins is as important as the comparison of their functions. Several algorithms have been devised to compute the similarity and dissimilarity among protein structures. But, these algorithms compare protein structures by structural alignment of the protein backbones which are usually unable to determine precise differences. In this paper, an attempt has been made to compute the similarities and dissimilarities among 3D protein structures using the fundamental mathematical morphology operations and fractal geometry which can resolve the problem of real differences. In doing so, two techniques are being used here in determining the superficial structural (global similarity) and local similarity in atomic level of the protein molecules. This intricate structural difference would provide insight to Biologists to understand the protein structures and their functions more precisely.
Hyperspectral Data Unmixing Using GNMF Method and Sparseness Constraint
Venue: arXiv cs.CV 2013
Year: 2013

Hyperspectral images contain mixed pixels due to low spatial resolution of hyperspectral sensors. Mixed pixels are pixels containing more than one distinct material called endmembers. The presence percentages of endmembers in mixed pixels are called abundance fractions. Spectral unmixing problem refers to decomposing these pixels into a set of endmembers and abundance fractions. Due to nonnegativity constraint on abundance fractions, nonnegative matrix factorization methods (NMF) have been widely used for solving spectral unmixing problem. In this paper we have used graph regularized (GNMF) method with sparseness constraint to unmix hyperspectral data. This method applied on simulated data using AVIRIS Indian Pines dataset and USGS library and results are quantified based on AAD and SAD measures. Results in comparison with other methods show that the proposed method can unmix data more effectively.
Dynamic Traitor Tracing Schemes, Revisited
Venue: arXiv cs.CR 2013
Year: 2013

We revisit recent results from the area of collusion-resistant traitor tracing, and show how they can be combined and improved to obtain more efficient dynamic traitor tracing schemes. In particular, we show how the dynamic Tardos scheme of Laarhoven et al. can be combined with the optimized score functions of Oosterwijk et al. to trace coalitions much faster. If the attack strategy is known, in many cases the order of the code length goes down from quadratic to linear in the number of colluders, while if the attack is not known, we show how the interleaving defense may be used to catch all colluders about twice as fast as in the dynamic Tardos scheme. Some of these results also apply to the static traitor tracing setting where the attack strategy is known in advance, and to group testing.
Ornitología Virtual: Caracterizando a #Chile en Twitter
Venue: arXiv cs.SI 2013
Year: 2013

Este artículo presenta un análisis de los tweets recolectados el 28 de Octubre de 2012, en el contexto de las elecciones municipales de 2012 en Chile. Dicho análisis se realiza mediante una metodología basada en literatura previa, en particular en técnicas de recuperación de la información y de análisis de espacios de información. Como resultado, se determinan: 1) características demográficas básicas de la población virtual chilena, incluyendo su distribución geográfica, 2) el contenido que caracteriza a cada región, y cómo fluye información entre regiones, y 3) el grado de representatividad de la población virtual participante en el evento con respecto a la población física. Se determina que la muestra obtenida es representativa de la población en términos de distribución geográfica, que el centralismo que afecta al país se ve reflejado en Twitter, y que, a pesar de los sesgos poblacionales, es posible identificar el contenido que caracteriza a cada región. Se finaliza con una discusión de las implicaciones y conclusiones prácticas de este trabajo, así como futuras aplicaciones.
Progressive Blue Surfels
Venue: arXiv cs.GR 2013
Year: 2013

In this paper we describe a new technique to generate and use surfels for rendering of highly complex, polygonal 3D scenes in real time. The basic idea is to approximate complex parts of the scene by rendering a set of points (surfels). The points are computed in a preprocessing step and offer two important properties: They are placed only on the visible surface of the scene's geometry and they are distributed and sorted in such a way, that every prefix of points is a good visual representation of the approximated part of the scene. An early evaluation of the method shows that it is capable of rendering scenes consisting of several billions of triangles with high image quality.
Verification-Based Interval-Passing Algorithm for Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

We propose a verification-based Interval-Passing (IP) algorithm for iteratively reconstruction of nonnegative sparse signals using parity check matrices of low-density parity check (LDPC) codes as measurement matrices. The proposed algorithm can be considered as an improved IP algorithm by further incorporation of the mechanism of verification algorithm. It is proved that the proposed algorithm performs always better than either the IP algorithm or the verification algorithm. Simulation results are also given to demonstrate the superior performance of the proposed algorithm.
The coloring problem for classes with two small obstructions
Venue: arXiv cs.DM 2013
Year: 2013

The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except 13 explicitly enumerated cases
The effectiveness of altruistic lobbying: A model study
Venue: arXiv cs.MA 2013
Year: 2013

Altruistic lobbying is lobbying in the public interest or in the interest of the least protected part of the society. In fact, an altruist has a wide range of strategies, from behaving in the interest of the society as a whole to the support of the most disadvantaged ones. How can we compare the effectiveness of such strategies? Another question is: "Given a strategy, is it possible to estimate the optimal number of participants choosing it?" Finally, do the answers to these questions depend on the level of well-being in the society? Can we say that the poorer the society, the more important is to focus on the support of the poorest? We answer these questions within the framework of the model of social dynamics determined by voting in a stochastic environment.
Discrete Signal Processing on Graphs: Frequency Analysis
Venue: arXiv cs.SI 2013
Year: 2013

Signals and datasets that arise in physical and engineering applications, as well as social, genetics, biomolecular, and many other domains, are becoming increasingly larger and more complex. In contrast to traditional time and image signals, data in these domains are supported by arbitrary graphs. Signal processing on graphs extends concepts and techniques from traditional signal processing to data indexed by generic graphs. This paper studies the concepts of low and high frequencies on graphs, and low-, high-, and band-pass graph filters. In traditional signal processing, there concepts are easily defined because of a natural frequency ordering that has a physical interpretation. For signals residing on graphs, in general, there is no obvious frequency ordering. We propose a definition of total variation for graph signals that naturally leads to a frequency ordering on graphs and defines low-, high-, and band-pass graph signals and filters. We study the design of graph filters with specified frequency response, and illustrate our approach with applications to sensor malfunction detection and data classification.
The Orchive : Data mining a massive bioacoustic archive
Venue: arXiv cs.LG 2013
Year: 2013

The Orchive is a large collection of over 20,000 hours of audio recordings from the OrcaLab research facility located off the northern tip of Vancouver Island. It contains recorded orca vocalizations from the 1980 to the present time and is one of the largest resources of bioacoustic data in the world. We have developed a web-based interface that allows researchers to listen to these recordings, view waveform and spectral representations of the audio, label clips with annotations, and view the results of machine learning classifiers based on automatic audio features extraction. In this paper we describe such classifiers that discriminate between background noise, orca calls, and the voice notes that are present in most of the tapes. Furthermore we show classification results for individual calls based on a previously existing orca call catalog. We have also experimentally investigated the scalability of classifiers over the entire Orchive.
Making massive probabilistic databases practical
Venue: arXiv cs.DB 2013
Year: 2013

Existence of incomplete and imprecise data has moved the database paradigm from deterministic to proba- babilistic information. Probabilistic databases contain tuples that may or may not exist with some probability. As a result, the number of possible deterministic database instances that can be observed from a probabilistic database grows exponentially with the number of probabilistic tuples. In this paper, we consider the problem of answering both aggregate and non-aggregate queries on massive probabilistic databases. We adopt the tuple independence model, in which each tuple is assigned a probability value. We develop a method that exploits Probability Generating Functions (PGF) to answer such queries efficiently. Our method maintains a polynomial for each tuple. It incrementally builds a master polynomial that expresses the distribution of the possible result values precisely. We also develop an approximation method that finds the distribution of the result value with negligible errors. Our experiments suggest that our methods are orders of magnitude faster than the most recent systems that answer such queries, including MayBMS and SPROUT. In our experiments, we were able to scale up to several terabytes of data on TPC- H queries, while existing methods could only run for a few gigabytes of data on the same queries.