OpenRaiser/Intern-Atlas huggingface dataset:
Software Effort Estimation with Ridge Regression and Evolutionary Attribute Selection
Venue: arXiv cs.SE 2010
Year: 2010

Software cost estimation is one of the prerequisite managerial activities carried out at the software development initiation stages and also repeated throughout the whole software life-cycle so that amendments to the total cost are made. In software cost estimation typically, a selection of project attributes is employed to produce effort estimations of the expected human resources to deliver a software product. However, choosing the appropriate project cost drivers in each case requires a lot of experience and knowledge on behalf of the project manager which can only be obtained through years of software engineering practice. A number of studies indicate that popular methods applied in the literature for software cost estimation, such as linear regression, are not robust enough and do not yield accurate predictions. Recently the dual variables Ridge Regression (RR) technique has been used for effort estimation yielding promising results. In this work we show that results may be further improved if an AI method is used to automatically select appropriate project cost drivers (inputs) for the technique. We propose a hybrid approach combining RR with a Genetic Algorithm, the latter evolving the subset of attributes for approximating effort more accurately. The proposed hybrid cost model has been applied on a widely known high-dimensional dataset of software project samples and the results obtained show that accuracy may be increased if redundant attributes are eliminated.
DD-EbA: An algorithm for determining the number of neighbors in cost estimation by analogy using distance distributions
Venue: arXiv cs.SE 2010
Year: 2010

Case Based Reasoning and particularly Estimation by Analogy, has been used in a number of problem-solving areas, such as cost estimation. Conventional methods, despite the lack of a sound criterion for choosing nearest projects, were based on estimation using a fixed and predetermined number of neighbors from the entire set of historical instances. This approach puts boundaries to the estimation ability of such algorithms, for they do not take into consideration that every project under estimation is unique and requires different handling. The notion of distributions of distances together with a distance metric for distributions help us to adapt the proposed method (we call it DD-EbA) each time to a specific case that is to be estimated without loosing in prediction power or computational cost. The results of this paper show that the proposed technique achieves the above idea in a very efficient way.
Homophonic Coding Design for Communication Systems Employing the Encoding-Encryption Paradigm
Venue: arXiv cs.CR 2010
Year: 2010

This paper addresses the design of a dedicated homophonic coding for a class of communication systems which, in order to provide both reliability and security, first encode the data before encrypting it, which is referred to as the encoding-encryption paradigm. The considered systems employ error-correction coding for reliability, a stream cipher for encryption, and homophonic coding to enhance the protection of the key used in the stream cipher, on which relies the security of all the system transmissions. This paper presents a security evaluation of such systems from a computational complexity point of view, which serves as a source for establishing dedicated homophonic code design criteria. The security evaluation shows that the computational complexity of recovering the secret key, given all the information an attacker could gather during passive attacks he can mount, is lower bounded by the complexity of the related LPN (Learning Parity in Noise) problem in both the average and worst case. This gives guidelines to construct a dedicated homophonic encoder which maximizes the complexity of the underlying LPN problem for a given encoding overhead. Finally, this paper proposes a generic homophonic coding strategy that fulfills the proposed design criteria and thus both enhances security while minimizing the induced overhead.
Extending Binary Qualitative Direction Calculi with a Granular Distance Concept: Hidden Feature Attachment
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we introduce a method for extending binary qualitative direction calculi with adjustable granularity like OPRAm or the star calculus with a granular distance concept. This method is similar to the concept of extending points with an internal reference direction to get oriented points which are the basic entities in the OPRAm calculus. Even if the spatial objects are from a geometrical point of view infinitesimal small points locally available reference measures are attached. In the case of OPRAm, a reference direction is attached. The same principle works also with local reference distances which are called elevations. The principle of attaching references features to a point is called hidden feature attachment.
Toward Emerging Topic Detection for Business Intelligence: Predictive Analysis of `Meme' Dynamics
Venue: arXiv cs.SI 2010
Year: 2010

Detecting and characterizing emerging topics of discussion and consumer trends through analysis of Internet data is of great interest to businesses. This paper considers the problem of monitoring the Web to spot emerging memes - distinctive phrases which act as "tracers" for topics - as a means of early detection of new topics and trends. We present a novel methodology for predicting which memes will propagate widely, appearing in hundreds or thousands of blog posts, and which will not, thereby enabling discovery of significant topics. We begin by identifying measurables which should be predictive of meme success. Interestingly, these metrics are not those traditionally used for such prediction but instead are subtle measures of meme dynamics. These metrics form the basis for learning a classifier which predicts, for a given meme, whether or not it will propagate widely. The utility of the prediction methodology is demonstrated through analysis of memes that emerged online during the second half of 2008.
Learning a Representation of a Believable Virtual Character's Environment with an Imitation Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

In video games, virtual characters' decision systems often use a simplified representation of the world. To increase both their autonomy and believability we want those characters to be able to learn this representation from human players. We propose to use a model called growing neural gas to learn by imitation the topology of the environment. The implementation of the model, the modifications and the parameters we used are detailed. Then, the quality of the learned representations and their evolution during the learning are studied using different measures. Improvements for the growing neural gas to give more information to the character's model are given in the conclusion.
Packet Scheduling in Switches with Target Outflow Profiles
Venue: arXiv cs.NI 2010
Year: 2010

The problem of packet scheduling for traffic streams with target outflow profiles traversing input queued switches is formulated in this paper. Target outflow profiles specify the desirable inter-departure times of packets leaving the switch from each traffic stream. The goal of the switch scheduler is to dynamically select service configurations of the switch, so that actual outflow streams ("pulled" through the switch) adhere to their desired target profiles as accurately as possible. Dynamic service controls (schedules) are developed to minimize deviation of actual outflow streams from their targets and suppress stream "distortion". Using appropriately selected subsets of service configurations of the switch, efficient schedules are designed, which deliver high performance at relatively low complexity. Some of these schedules are provably shown to achieve 100% pull-throughput. Moreover, simulations demonstrate that for even substantial contention of streams through the switch, due to stringent/intense target outflow profiles, the proposed schedules achieve closely their target profiles and suppress stream distortion. The switch model investigated here deviates from the classical switching paradigm. In the latter, the goal of packet scheduling is primarily to "push" as much traffic load through the switch as possible, while controlling delay to traverse the switch and keeping congestion/backlogs from exploding. In the model presented here, however, the goal of packet scheduling is to "pull" traffic streams through the switch, maintaining desirable (target) outflow profiles.
The growth function of S-recognizable sets
Venue: arXiv cs.FL 2010
Year: 2010

A set $X\subseteq\mathbb N$ is S-recognizable for an abstract numeration system S if the set $\rep_S(X)$ of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either $Θ((\log(n))^{c-df}n^f)$ where $c,d\in\mathbb N$ and $f\ge 1$, or $Θ(n^r θ^{Θ(n^q)})$, where $r,q\in\mathbb Q$ with $q\le 1$. If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is $Θ(n^r)$, where $r\in \mathbb Q$ with $r\ge 1$. Furthermore, for every $r\in \mathbb Q$ with $r\ge 1$, we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is $Θ(n^r)$. For all positive integers k and l, we can also provide an abstract numeration system S built on a exponential language and an S-recognizable set such that the growth function of X is $Θ((\log(n))^k n^l)$.
The Complexity of Euclidian 2 Dimension Travelling Salesman Problem versus General Assign Problem, NP is not P
Venue: arXiv cs.DS 2010
Year: 2010

This paper presents the differences between two NP problems. It focuses in the Euclidian 2 Dimension Travelling Salesman Problems and General Assign Problems. The main results are the triangle reduction to verify the solution in polynomial time for the former and for the later the solution to the Noted Conjecture of the NP-Class, NP is not P.
Maximizing Strength of Digital Watermarks using Fuzzy Logic
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we propose a novel digital watermarking scheme in DCT domain based fuzzy inference system and the human visual system to adapt the embedding strength of different blocks. Firstly, the original image is divided into some 8 \times 8 blocks, and then fuzzy inference system according to different textural features and luminance of each block decide adaptively different embedding strengths. The watermark detection adopts correlation technology. Experimental results show that the proposed scheme has good imperceptibility and high robustness to common image processing operators.
An Intrusion Detection Architecture for Clustered Wireless Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

Intrusion detection in wireless ad hoc networks is a challenging task because these networks change their topologies dynamically, lack concentration points where aggregated traffic can be analyzed, utilize infrastructure protocols that are susceptible to manipulation, and rely on noisy, intermittent wireless communications. Security remains a major challenge for these networks due their features of open medium, dynamically changing topologies, reliance on co-operative algorithms, absence of centralized monitoring points, and lack of clear lines of defense. In this paper, we present a cooperative, distributed intrusion detection architecture based on clustering of the nodes that addresses the security vulnerabilities of the network and facilitates accurate detection of attacks. The architecture is organized as a dynamic hierarchy in which the intrusion data is acquired by the nodes and is incrementally aggregated, reduced in volume and analyzed as it flows upwards to the cluster-head. The cluster-heads of adjacent clusters communicate with each other in case of cooperative intrusion detection. For intrusion related message communication, mobile agents are used for their efficiency in lightweight computation and suitability in cooperative intrusion detection. Simulation results show effectiveness and efficiency of the proposed architecture.
Illustrating Color Evolution and Color Blindness by the Decoding Model of Color Vision
Venue: arXiv cs.CV 2010
Year: 2010

A symmetrical model of color vision, the decoding model as a new version of zone model, was introduced. The model adopts new continuous-valued logic and works in a way very similar to the way a 3-8 decoder in a numerical circuit works. By the decoding model, Young and Helmholtz's tri-pigment theory and Hering's opponent theory are unified more naturally; opponent process, color evolution, and color blindness are illustrated more concisely. According to the decoding model, we can obtain a transform from RGB system to HSV system, which is formally identical to the popular transform for computer graphics provided by Smith (1978). Advantages, problems, and physiological tests of the decoding model are also discussed.
Locked and Unlocked Chains of Planar Shapes
Venue: arXiv cs.CG 2010
Year: 2010

We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid planar shapes (Jordan regions) that are hinged together sequentially at rotatable joints. Our goal is to characterize the families of planar shapes that admit locked chains, where some configurations cannot be reached by continuous reconfiguration without self-intersection, and which families of planar shapes guarantee universal foldability, where every chain is guaranteed to have a connected configuration space. Previously, only obtuse triangles were known to admit locked shapes, and only line segments were known to guarantee universal foldability. We show that a surprisingly general family of planar shapes, called slender adornments, guarantees universal foldability: roughly, the distance from each edge along the path along the boundary of the slender adornment to each hinge should be monotone. In contrast, we show that isosceles triangles with any desired apex angle less than 90 degrees admit locked chains, which is precisely the threshold beyond which the inward-normal property no longer holds.
Concurrent Processing Memory
Venue: arXiv cs.DC 2010
Year: 2010

A theoretical memory with limited processing power and internal connectivity at each element is proposed. This memory carries out parallel processing within itself to solve generic array problems. The applicability of this in-memory finest-grain massive SIMD approach is studied in some details. For an array of N items, it reduces the total instruction cycle count of universal operations such as insertion/deletion and match finding to ~ 1, local operations such as filtering and template matching to ~ local operation size, and global operations such as sum, finding global limit and sorting to ~\sqroot{N} instruction cycles. It eliminates most streaming activities for data processing purpose on the system bus. Yet it remains general-purposed, easy to use, pin compatible with conventional memory, and practical for implementation.
Happy endings for flip graphs
Venue: arXiv cs.CG 2010
Year: 2010

We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.
Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris
Venue: arXiv cs.AI 2011
Year: 2011

We consider the discrete-time infinite-horizon optimal control problem formalized by Markov Decision Processes. We revisit the work of Bertsekas and Ioffe, that introduced $λ$ Policy Iteration, a family of algorithms parameterized by $λ$ that generalizes the standard algorithms Value Iteration and Policy Iteration, and has some deep connections with the Temporal Differences algorithm TD($λ$) described by Sutton and Barto. We deepen the original theory developped by the authors by providing convergence rate bounds which generalize standard bounds for Value Iteration described for instance by Puterman. Then, the main contribution of this paper is to develop the theory of this algorithm when it is used in an approximate form and show that this is sound. Doing so, we extend and unify the separate analyses developped by Munos for Approximate Value Iteration and Approximate Policy Iteration. Eventually, we revisit the use of this algorithm in the training of a Tetris playing controller as originally done by Bertsekas and Ioffe. We provide an original performance bound that can be applied to such an undiscounted control problem. Our empirical results are different from those of Bertsekas and Ioffe (which were originally qualified as "paradoxical" and "intriguing"), and much more conform to what one would expect from a learning experiment. We discuss the possible reason for such a difference.
A System for Distributed Mechanisms: Design, Implementation and Applications
Venue: arXiv cs.DC 2011
Year: 2011

We describe here a structured system for distributed mechanism design appropriate for both Intranet and Internet applications. In our approach the players dynamically form a network in which they know neither their neighbours nor the size of the network and interact to jointly take decisions. The only assumption concerning the underlying communication layer is that for each pair of processes there is a path of neighbours connecting them. This allows us to deal with arbitrary network topologies. We also discuss the implementation of this system which consists of a sequence of layers. The lower layers deal with the operations that implement the basic primitives of distributed computing, namely low level communication and distributed termination, while the upper layers use these primitives to implement high level communication among players, including broadcasting and multicasting, and distributed decision making. This yields a highly flexible distributed system whose specific applications are realized as instances of its top layer. This design is implemented in Java. The system supports at various levels fault-tolerance and includes a provision for distributed policing the purpose of which is to exclude `dishonest' players. Also, it can be used for repeated creation of dynamically formed networks of players interested in a joint decision making implemented by means of a tax-based mechanism. We illustrate its flexibility by discussing a number of implemented examples.
On the Expressive Power of Multiple Heads in CHR
Venue: arXiv cs.LO 2011
Year: 2011

Constraint Handling Rules (CHR) is a committed-choice declarative language which has been originally designed for writing constraint solvers and which is nowadays a general purpose language. CHR programs consist of multi-headed guarded rules which allow to rewrite constraints into simpler ones until a solved form is reached. Many empirical evidences suggest that multiple heads augment the expressive power of the language, however no formal result in this direction has been proved, so far. In the first part of this paper we analyze the Turing completeness of CHR with respect to the underneath constraint theory. We prove that if the constraint theory is powerful enough then restricting to single head rules does not affect the Turing completeness of the language. On the other hand, differently from the case of the multi-headed language, the single head CHR language is not Turing powerful when the underlying signature (for the constraint theory) does not contain function symbols. In the second part we prove that, no matter which constraint theory is considered, under some reasonable assumptions it is not possible to encode the CHR language (with multi-headed rules) into a single headed language while preserving the semantics of the programs. We also show that, under some stronger assumptions, considering an increasing number of atoms in the head of a rule augments the expressive power of the language. These results provide a formal proof for the claim that multiple heads augment the expressive power of the CHR language.
Coding Theory and Projective Spaces
Venue: arXiv cs.IT 2011
Year: 2011

The projective space of order $n$ over a finite field $\F_q$ is a set of all subspaces of the vector space $\F_q^{n}$. In this work, we consider error-correcting codes in the projective space, focusing mainly on constant dimension codes. We start with the different representations of subspaces in the projective space. These representations involve matrices in reduced row echelon form, associated binary vectors, and Ferrers diagrams. Based on these representations, we provide a new formula for the computation of the distance between any two subspaces in the projective space. We examine lifted maximum rank distance (MRD) codes, which are nearly optimal constant dimension codes. We prove that a lifted MRD code can be represented in such a way that it forms a block design known as a transversal design. The incidence matrix of the transversal design derived from a lifted MRD code can be viewed as a parity-check matrix of a linear code in the Hamming space. We find the properties of these codes which can be viewed also as LDPC codes. We present new bounds and constructions for constant dimension codes. First, we present a multilevel construction for constant dimension codes, which can be viewed as a generalization of a lifted MRD codes construction. This construction is based on a new type of rank-metric codes, called Ferrers diagram rank-metric codes. Then we derive upper bounds on the size of constant dimension codes which contain the lifted MRD code, and provide a construction for two families of codes, that attain these upper bounds. We generalize the well-known concept of a punctured code for a code in the projective space to obtain large codes which are not constant dimension. We present efficient enumerative encoding and decoding techniques for the Grassmannian. Finally we describe a search method for constant dimension lexicodes.
DimReduction - Interactive Graphic Environment for Dimensionality Reduction
Venue: arXiv cs.CV 2011
Year: 2011

Feature selection is a pattern recognition approach to choose important variables according to some criteria to distinguish or explain certain phenomena. There are many genomic and proteomic applications which rely on feature selection to answer questions such as: selecting signature genes which are informative about some biological state, e.g. normal tissues and several types of cancer; or defining a network of prediction or inference among elements such as genes, proteins, external stimuli and other elements of interest. In these applications, a recurrent problem is the lack of samples to perform an adequate estimate of the joint probabilities between element states. A myriad of feature selection algorithms and criterion functions are proposed, although it is difficult to point the best solution in general. The intent of this work is to provide an open-source multiplataform graphical environment to apply, test and compare many feature selection approaches suitable to be used in bioinformatics problems.
Menger's Paths with Minimum Mergings
Venue: arXiv cs.IT 2011
Year: 2011

For an acyclic directed graph with multiple sources and multiple sinks, we prove that one can choose the Merger's paths between the sources and the sinks such that the number of mergings between these paths is upper bounded by a constant depending only on the min-cuts between the sources and the sinks, regardless of the size and topology of the graph. We also give bounds on the minimum number of mergings between these paths, and discuss how it depends on the min-cuts.