OpenRaiser/Intern-Atlas huggingface dataset:
Network of two-Chinese-character compound words in Japanese language
Venue: arXiv cs.CL 2009
Year: 2009

Some statistical properties of a network of two-Chinese-character compound words in Japanese language are reported. In this network, a node represents a Chinese character and an edge represents a two-Chinese-character compound word. It is found that this network has properties of "small-world" and "scale-free." A network formed by only Chinese characters for common use ({\it joyo-kanji} in Japanese), which is regarded as a subclass of the original network, also has small-world property. However, a degree distribution of the network exhibits no clear power law. In order to reproduce disappearance of the power-law property, a model for a selecting process of the Chinese characters for common use is proposed.
Prediction with expert evaluators' advice
Venue: arXiv cs.LG 2009
Year: 2009

We introduce a new protocol for prediction with expert advice in which each expert evaluates the learner's and his own performance using a loss function that may change over time and may be different from the loss functions used by the other experts. The learner's goal is to perform better or not much worse than each expert, as evaluated by that expert, for all experts simultaneously. If the loss functions used by the experts are all proper scoring rules and all mixable, we show that the defensive forecasting algorithm enjoys the same performance guarantee as that attainable by the Aggregating Algorithm in the standard setting and known to be optimal. This result is also applied to the case of "specialist" (or "sleeping") experts. In this case, the defensive forecasting algorithm reduces to a simple modification of the Aggregating Algorithm.
Circulant and Toeplitz matrices in compressed sensing
Venue: arXiv cs.IT 2009
Year: 2009

Compressed sensing seeks to recover a sparse vector from a small number of linear and non-adaptive measurements. While most work so far focuses on Gaussian or Bernoulli random measurements we investigate the use of partial random circulant and Toeplitz matrices in connection with recovery by $\ell_1$-minization. In contrast to recent work in this direction we allow the use of an arbitrary subset of rows of a circulant and Toeplitz matrix. Our recovery result predicts that the necessary number of measurements to ensure sparse reconstruction by $\ell_1$-minimization with random partial circulant or Toeplitz matrices scales linearly in the sparsity up to a $\log$-factor in the ambient dimension. This represents a significant improvement over previous recovery results for such matrices. As a main tool for the proofs we use a new version of the non-commutative Khintchine inequality.
Learning DTW Global Constraint for Time Series Classification
Venue: arXiv cs.AI 2009
Year: 2009

1-Nearest Neighbor with the Dynamic Time Warping (DTW) distance is one of the most effective classifiers on time series domain. Since the global constraint has been introduced in speech community, many global constraint models have been proposed including Sakoe-Chiba (S-C) band, Itakura Parallelogram, and Ratanamahatana-Keogh (R-K) band. The R-K band is a general global constraint model that can represent any global constraints with arbitrary shape and size effectively. However, we need a good learning algorithm to discover the most suitable set of R-K bands, and the current R-K band learning algorithm still suffers from an 'overfitting' phenomenon. In this paper, we propose two new learning algorithms, i.e., band boundary extraction algorithm and iterative learning algorithm. The band boundary extraction is calculated from the bound of all possible warping paths in each class, and the iterative learning is adjusted from the original R-K band learning. We also use a Silhouette index, a well-known clustering validation technique, as a heuristic function, and the lower bound function, LB_Keogh, to enhance the prediction speed. Twenty datasets, from the Workshop and Challenge on Time Series Classification, held in conjunction of the SIGKDD 2007, are used to evaluate our approach.
Manipulation Robustness of Collaborative Filtering Systems
Venue: arXiv cs.LG 2009
Year: 2009

A collaborative filtering system recommends to users products that similar users like. Collaborative filtering systems influence purchase decisions, and hence have become targets of manipulation by unscrupulous vendors. We provide theoretical and empirical results demonstrating that while common nearest neighbor algorithms, which are widely used in commercial systems, can be highly susceptible to manipulation, two classes of collaborative filtering algorithms which we refer to as linear and asymptotically linear are relatively robust. These results provide guidance for the design of future collaborative filtering systems.
Document Relevance Evaluation via Term Distribution Analysis Using Fourier Series Expansion
Venue: arXiv cs.IR 2009
Year: 2009

In addition to the frequency of terms in a document collection, the distribution of terms plays an important role in determining the relevance of documents for a given search query. In this paper, term distribution analysis using Fourier series expansion as a novel approach for calculating an abstract representation of term positions in a document corpus is introduced. Based on this approach, two methods for improving the evaluation of document relevance are proposed: (a) a function-based ranking optimization representing a user defined document region, and (b) a query expansion technique based on overlapping the term distributions in the top-ranked documents. Experimental results demonstrate the effectiveness of the proposed approach in providing new possibilities for optimizing the retrieval process.
Granularity-Adaptive Proof Presentation
Venue: arXiv cs.AI 2009
Year: 2009

When mathematicians present proofs they usually adapt their explanations to their didactic goals and to the (assumed) knowledge of their addressees. Modern automated theorem provers, in contrast, present proofs usually at a fixed level of detail (also called granularity). Often these presentations are neither intended nor suitable for human use. A challenge therefore is to develop user- and goal-adaptive proof presentation techniques that obey common mathematical practice. We present a flexible and adaptive approach to proof presentation that exploits machine learning techniques to extract a model of the specific granularity of proof examples and employs this model for the automated generation of further proofs at an adapted level of granularity.
Deductive Inference for the Interiors and Exteriors of Horn Theories
Venue: arXiv cs.AI 2009
Year: 2009

In this paper, we investigate the deductive inference for the interiors and exteriors of Horn knowledge bases, where the interiors and exteriors were introduced by Makino and Ibaraki to study stability properties of knowledge bases. We present a linear time algorithm for the deduction for the interiors and show that it is co-NP-complete for the deduction for the exteriors. Under model-based representation, we show that the deduction problem for interiors is NP-complete while the one for exteriors is co-NP-complete. As for Horn envelopes of the exteriors, we show that it is linearly solvable under model-based representation, while it is co-NP-complete under formula-based representation. We also discuss the polynomially solvable cases for all the intractable problems.
Raptor Codes Based Distributed Storage Algorithms for Wireless Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider a distributed storage problem in a large-scale wireless sensor network with $n$ nodes among which $k$ acquire (sense) independent data. The goal is to disseminate the acquired information throughout the network so that each of the $n$ sensors stores one possibly coded packet and the original $k$ data packets can be recovered later in a computationally simple way from any $(1+ε)k$ of nodes for some small $ε>0$. We propose two Raptor codes based distributed storage algorithms for solving this problem. In the first algorithm, all the sensors have the knowledge of $n$ and $k$. In the second one, we assume that no sensor has such global information.
Real-time Texture Error Detection
Venue: arXiv cs.CV 2009
Year: 2009

This paper advocates an improved solution for real-time error detection of texture errors that occurs in the production process in textile industry. The research is focused on the mono-color products with 3D texture model (Jaquard fabrics). This is a more difficult task than, for example, 2D multicolor textures.
On Requirements for Programming Exercises from an E-learning Perspective
Venue: arXiv cs.AI 2009
Year: 2009

In this work, we deal with the question of modeling programming exercises for novices pointing to an e-learning scenario. Our purpose is to identify basic requirements, raise some key questions and propose potential answers from a conceptual perspective. Presented as a general picture, we hypothetically situate our work in a general context where e-learning instructional material needs to be adapted to form part of an introductory Computer Science (CS) e-learning course at the CS1-level. Meant is a potential course which aims at improving novices skills and knowledge on the essentials of programming by using e-learning based approaches in connection (at least conceptually) with a general host framework like Activemath (www.activemath.org). Our elaboration covers contextual and, particularly, cognitive elements preparing the terrain for eventual research stages in a derived project, as indicated. We concentrate our main efforts on reasoning mechanisms about exercise complexity that can eventually offer tool support for the task of exercise authoring. We base our requirements analysis on our own perception of the exercise subsystem provided by Activemath especially within the domain reasoner area. We enrich the analysis by bringing to the discussion several relevant contextual elements from the CS1 courses, its definition and implementation. Concerning cognitive models and exercises, we build upon the principles of Bloom's Taxonomy as a relatively standardized basis and use them as a framework for study and analysis of complexity in basic programming exercises. Our analysis includes requirements for the domain reasoner which are necessary for the exercise analysis. We propose for such a purpose a three-layered conceptual model considering exercise evaluation, programming and metaprogramming.
A Domain-Specific Language for Programming in the Tile Assembly Model
Venue: arXiv cs.SE 2009
Year: 2009

We introduce a domain-specific language (DSL) for creating sets of tile types for simulations of the abstract Tile Assembly Model. The language defines objects known as tile templates, which represent related groups of tiles, and a small number of basic operations on tile templates that help to eliminate the error-prone drudgery of enumerating such tile types manually or with low-level constructs of general-purpose programming languages. The language is implemented as a class library in Python (a so-called internal DSL), but is presented independently of Python or object-oriented programming, with emphasis on supporting the creation of visual editing tools for programmatically creating large sets of complex tile types without needing to write a program.
On the Category of Partial Bijections
Venue: arXiv cs.DM 2009
Year: 2009

Categories of partial functions have become increasingly important principally because of their applications in theoretical computer science. In this note we prove that the category of partial bijections between sets as an inverse-Baer*-category with closed projections and in which the idempotent split is an exact category. Finally the Noether isomorphism theorems are given for this exact category.
On-Off Random Access Channels: A Compressed Sensing Framework
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers a simple on-off random multiple access channel, where n users communicate simultaneously to a single receiver over m degrees of freedom. Each user transmits with probability lambda, where typically lambda n < m << n, and the receiver must detect which users transmitted. We show that when the codebook has i.i.d. Gaussian entries, detecting which users transmitted is mathematically equivalent to a certain sparsity detection problem considered in compressed sensing. Using recent sparsity results, we derive upper and lower bounds on the capacities of these channels. We show that common sparsity detection algorithms, such as lasso and orthogonal matching pursuit (OMP), can be used as tractable multiuser detection schemes and have significantly better performance than single-user detection. These methods do achieve some near-far resistance but--at high signal-to-noise ratios (SNRs)--may achieve capacities far below optimal maximum likelihood detection. We then present a new algorithm, called sequential OMP, that illustrates that iterative detection combined with power ordering or power shaping can significantly improve the high SNR performance. Sequential OMP is analogous to successive interference cancellation in the classic multiple access channel. Our results thereby provide insight into the roles of power control and multiuser detection on random-access signalling.
Application for Evaluation of the Professional Competencies of the Teaching Staff
Venue: arXiv cs.CY 2009
Year: 2009

The goal of the presented application is to offer a full support for universities in retrieving the feedback from their students with regard to their teachers. This is the main reason we described it in this paper. To build this application the following tools have been used: Microsoft Notepad 5.1 (to make the source files), Adobe Photoshop CS3 (to make the background image) and Adobe Flash Media Encoder 8 (to render the video clips).
The Complexity of Reasoning with Global Constraints
Venue: arXiv cs.AI 2009
Year: 2009

Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.
Enumerative Encoding in the Grassmannian Space
Venue: arXiv cs.IT 2009
Year: 2009

Codes in the Grassmannian space have found recently application in network coding. Representation of $k$-dimensional subspaces of $\F_q^n$ has generally an essential role in solving coding problems in the Grassmannian, and in particular in encoding subspaces of the Grassmannian. Different representations of subspaces in the Grassmannian are presented. We use two of these representations for enumerative encoding of the Grassmannian. One enumerative encoding is based on Ferrers diagrams representation of subspaces; and another is based on identifying vector and reduced row echelon form representation of subspaces. A third method which combine the previous two is more efficient than the other two enumerative encodings.
Laconic schema mappings: computing core universal solutions by means of SQL queries
Venue: arXiv cs.DB 2009
Year: 2009

We present a new method for computing core universal solutions in data exchange settings specified by source-to-target dependencies, by means of SQL queries. Unlike previously known algorithms, which are recursive in nature, our method can be implemented directly on top of any DBMS. Our method is based on the new notion of a laconic schema mapping. A laconic schema mapping is a schema mapping for which the canonical universal solution is the core universal solution. We give a procedure by which every schema mapping specified by FO s-t tgds can be turned into a laconic schema mapping specified by FO s-t tgds that may refer to a linear order on the domain of the source instance. We show that our results are optimal, in the sense that the linear order is necessary and the method cannot be extended to schema mapping involving target constraints.
Deposition and Extension Approach to Find Longest Common Subsequence for Multiple Sequences
Venue: arXiv cs.DS 2009
Year: 2009

The problem of finding the longest common subsequence (LCS) for a set of sequences is a very interesting and challenging problem in computer science. This problem is NP-complete, but because of its importance, many heuristic algorithms have been proposed, such as Long Run algorithm and Expansion algorithm. However, the performance of many current heuristic algorithms deteriorates fast when the number of sequences and sequence length increase. In this paper, we have proposed a post process heuristic algorithm for the LCS problem, the Deposition and Extension algorithm (DEA). This algorithm first generates common subsequence by the process of sequences deposition, and then extends this common subsequence. The algorithm is proven to generate Common Subsequences (CSs) with guaranteed lengths. The experiments show that the results of DEA algorithm are better than those of Long Run and Expansion algorithm, especially on many long sequences. The algorithm also has superior efficiency both in time and space.
Adaptive Mesh Approach for Predicting Algorithm Behavior with Application to Visibility Culling in Computer Graphics
Venue: arXiv cs.PF 2009
Year: 2009

We propose a concise approximate description, and a method for efficiently obtaining this description, via adaptive random sampling of the performance (running time, memory consumption, or any other profileable numerical quantity) of a given algorithm on some low-dimensional rectangular grid of inputs. The formal correctness is proven under reasonable assumptions on the algorithm under consideration; and the approach's practical benefit is demonstrated by predicting for which observer positions and viewing directions an occlusion culling algorithm yields a net performance benefit or loss compared to a simple brute force renderer.
Supernodal Analysis Revisited
Venue: arXiv cs.SC 2009
Year: 2009

In this paper we show how to extend the known algorithm of nodal analysis in such a way that, in the case of circuits without nullors and controlled sources (but allowing for both, independent current and voltage sources), the system of nodal equations describing the circuit is partitioned into one part, where the nodal variables are explicitly given as linear combinations of the voltage sources and the voltages of certain reference nodes, and another, which contains the node variables of these reference nodes only and which moreover can be read off directly from the given circuit. Neither do we need preparational graph transformations, nor do we need to introduce additional current variables (as in MNA). Thus this algorithm is more accessible to students, and consequently more suitable for classroom presentations.
On the Generation of Test Data for Prolog by Partial Evaluation
Venue: arXiv cs.PL 2009
Year: 2009

In recent work, we have proposed an approach to Test Data Generation (TDG) of imperative bytecode by partial evaluation (PE) of CLP which consists in two phases: (1) the bytecode program is first transformed into an equivalent CLP program by means of interpretive compilation by PE, (2) a second PE is performed in order to supervise the generation of test-cases by execution of the CLP decompiled program. The main advantages of TDG by PE include flexibility to handle new coverage criteria, the possibility to obtain test-case generators and its simplicity to be implemented. The approach in principle can be directly applied for TDG of any imperative language. However, when one tries to apply it to a declarative language like Prolog, we have found as a main difficulty the generation of test-cases which cover the more complex control flow of Prolog. Essentially, the problem is that an intrinsic feature of PE is that it only computes non-failing derivations while in TDG for Prolog it is essential to generate test-cases associated to failing computations. Basically, we propose to transform the original Prolog program into an equivalent Prolog program with explicit failure by partially evaluating a Prolog interpreter which captures failing derivations w.r.t. the input program. Another issue that we discuss in the paper is that, while in the case of bytecode the underlying constraint domain only manipulates integers, in Prolog it should properly handle the symbolic data manipulated by the program. The resulting scheme is of interest for bringing the advantages which are inherent in TDG by PE to the field of logic programming.
Achievable Error Exponents for Channel with Side Information - Erasure and List Decoding
Venue: arXiv cs.IT 2009
Year: 2009

We consider a decoder with an erasure option and a variable size list decoder for channels with non-casual side information at the transmitter. First, universally achievable error exponents are offered for decoding with an erasure option using a parameterized decoder in the spirit of Csiszár and Körner's decoder. Then, the proposed decoding rule is generalized by extending the range of its parameters to allow variable size list decoding. This extension gives a unified treatment for erasure/list decoding. Exponential bounds on the probability of list error and the average number of incorrect messages on the list are given. Relations to Forney's and Csiszár and Körner's decoders for discrete memoryless channel are discussed. These results are obtained by exploring a random binning code with conditionally constant composition codewords proposed by Moulin and Wang, but with a different decoding rule.
Analysis of the Relationships among Longest Common Subsequences, Shortest Common Supersequences and Patterns and its application on Pattern Discovery in Biological Sequences
Venue: arXiv cs.DS 2009
Year: 2009

For a set of mulitple sequences, their patterns,Longest Common Subsequences (LCS) and Shortest Common Supersequences (SCS) represent different aspects of these sequences profile, and they can all be used for biological sequence comparisons and analysis. Revealing the relationship between the patterns and LCS,SCS might provide us with a deeper view of the patterns of biological sequences, in turn leading to better understanding of them. However, There is no careful examinaton about the relationship between patterns, LCS and SCS. In this paper, we have analyzed their relation, and given some lemmas. Based on their relations, a set of algorithms called the PALS (PAtterns by Lcs and Scs) algorithms are propsoed to discover patterns in a set of biological sequences. These algorithms first generate the results for LCS and SCS of sequences by heuristic, and consequently derive patterns from these results. Experiments show that the PALS algorithms perform well (both in efficiency and in accuracy) on a variety of sequences. The PALS approach also provides us with a solution for transforming between the heuristic results of SCS and LCS.