OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Bound Optimization for Online Convex Optimization
Venue: arXiv cs.LG 2010
Year: 2010

We introduce a new online convex optimization algorithm that adaptively chooses its regularization function based on the loss functions observed so far. This is in contrast to previous algorithms that use a fixed regularization function such as L2-squared, and modify it only via a single time-dependent parameter. Our algorithm's regret bounds are worst-case optimal, and for certain realistic classes of loss functions they are much better than existing bounds. These bounds are problem-dependent, which means they can exploit the structure of the actual problem instance. Critically, however, our algorithm does not need to know this structure in advance. Rather, we prove competitive guarantees that show the algorithm provides a bound within a constant factor of the best possible bound (of a certain functional form) in hindsight.
Energy Optimal Transmission Scheduling in Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

One of the main issues in the design of sensor networks is energy efficient communication of time-critical data. Energy wastage can be caused by failed packet transmission attempts at each node due to channel dynamics and interference. Therefore transmission control techniques that are unaware of the channel dynamics can lead to suboptimal channel use patterns. In this paper we propose a transmission controller that utilizes different "grades" of channel side information to schedule packet transmissions in an optimal way, while meeting a deadline constraint for all packets waiting in the transmission queue. The wireless channel is modeled as a finite-state Markov channel. We are specifically interested in the case where the transmitter has low-grade channel side information that can be obtained based solely on the ACK/NAK sequence for the previous transmissions. Our scheduler is readily implementable and it is based on the dynamic programming solution to the finite-horizon transmission control problem. We also calculate the information theoretic capacity of the finite state Markov channel with feedback containing different grades of channel side information including that, obtained through the ACK/NAK sequence. We illustrate that our scheduler achieves a given throughput at a power level that is fairly close to the fundamental limit achievable over the channel.
Generating Function For Network Delay
Venue: arXiv cs.NI 2010
Year: 2010

In this paper correspondence between experimental data for packet delay and two theoretical types of distribution is investigated. Statistical tests have shown that only exponential distribution can be used for the description of packet delays in global network. Precision experimental data to within microseconds are gathered by means of the RIPE Test Box. Statistical verification of hypothesis has shown that distribution parameters remain constants during 500 second intervals at least. In paper cumulative distribution function and generating function for packet delay in network are in an explicit form written down, the algorithm of search of parameters of distribution is resulted.
Central Force Optimization Applied to the PBM Suite of Antenna Benchmarks
Venue: arXiv cs.OH 2010
Year: 2010

Central Force Optimization (CFO) is a new nature-inspired deterministic multi-dimensional search and optimization metaheuristic based on the metaphor of gravitational kinematics. CFO is applied to the PBM antenna benchmark suite and the results compared to published performance data for other optimization algorithms. CFO acquits itself quite well. CFO's gradient-like nature is discussed, and it is speculated that a "generalized hyperspace derivative" might be defined for optimization problems as a new mathematical construct based on the Unit Step function. What appears to be a sufficient but not necessary condition for local trapping, oscillation in the probe average distance curve, is discussed in the context of the theory of gravitational "resonant returns" that gives rise to strikingly similar oscillatory curves. It is suggested that the theory may be applicable to CFO as an aid to understanding trapping and to developing effective mitigation techniques, possibly based on a concept of "energy" in CFO space. It also is suggested that CFO may be re-formulated as a "total energy" model by analogizing conservation of energy for orbiting masses in physical space.
Further Exploration of the Dendritic Cell Algorithm: Antigen Multiplier and Time Windows
Venue: arXiv cs.AI 2010
Year: 2010

As an immune-inspired algorithm, the Dendritic Cell Algorithm (DCA), produces promising performances in the field of anomaly detection. This paper presents the application of the DCA to a standard data set, the KDD 99 data set. The results of different implementation versions of the DXA, including the antigen multiplier and moving time windows are reported. The real-valued Negative Selection Algorithm (NSA) using constant-sized detectors and the C4.5 decision tree algorithm are used, to conduct a baseline comparison. The results suggest that the DCA is applicable to KDD 99 data set, and the antigen multiplier and moving time windows have the same effect on the DCA for this particular data set. The real-valued NSA with constant-sized detectors is not applicable to the data set, and the C4.5 decision tree algorithm provides a benchmark of the classification performance for this data set.
Stopping Set Distributions of Some Linear Codes
Venue: arXiv cs.IT 2010
Year: 2010

Stopping sets and stopping set distribution of an low-density parity-check code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). Let $C$ be a binary $[n,k]$ linear code with parity-check matrix $H$, where the rows of $H$ may be dependent. A stopping set $S$ of $C$ with parity-check matrix $H$ is a subset of column indices of $H$ such that the restriction of $H$ to $S$ does not contain a row of weight one. The stopping set distribution $\{T_i(H)\}_{i=0}^n$ enumerates the number of stopping sets with size $i$ of $C$ with parity-check matrix $H$. Note that stopping sets and stopping set distribution are related to the parity-check matrix $H$ of $C$. Let $H^{*}$ be the parity-check matrix of $C$ which is formed by all the non-zero codewords of its dual code $C^{\perp}$. A parity-check matrix $H$ is called BEC-optimal if $T_i(H)=T_i(H^*), i=0,1,..., n$ and $H$ has the smallest number of rows. On the BEC, iterative decoder of $C$ with BEC-optimal parity-check matrix is an optimal decoder with much lower decoding complexity than the exhaustive decoder. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes and the extended Hamming codes.
Collaborative Hierarchical Sparse Modeling
Venue: arXiv cs.IT 2010
Year: 2010

Sparse modeling is a powerful framework for data analysis and processing. Traditionally, encoding in this framework is done by solving an l_1-regularized linear regression problem, usually called Lasso. In this work we first combine the sparsity-inducing property of the Lasso model, at the individual feature level, with the block-sparsity property of the group Lasso model, where sparse groups of features are jointly encoded, obtaining a sparsity pattern hierarchically structured. This results in the hierarchical Lasso, which shows important practical modeling advantages. We then extend this approach to the collaborative case, where a set of simultaneously coded signals share the same sparsity pattern at the higher (group) level but not necessarily at the lower one. Signals then share the same active groups, or classes, but not necessarily the same active set. This is very well suited for applications such as source separation. An efficient optimization procedure, which guarantees convergence to the global optimum, is developed for these new models. The underlying presentation of the new framework and optimization approach is complemented with experimental examples and preliminary theoretical results.
The Sparsity Gap: Uncertainty Principles Proportional to Dimension
Venue: arXiv cs.IT 2010
Year: 2010

In an incoherent dictionary, most signals that admit a sparse representation admit a unique sparse representation. In other words, there is no way to express the signal without using strictly more atoms. This work demonstrates that sparse signals typically enjoy a higher privilege: each nonoptimal representation of the signal requires far more atoms than the sparsest representation-unless it contains many of the same atoms as the sparsest representation. One impact of this finding is to confer a certain degree of legitimacy on the particular atoms that appear in a sparse representation. This result can also be viewed as an uncertainty principle for random sparse signals over an incoherent dictionary.
A new model for solution of complex distributed constrained problems
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we describe an original computational model for solving different types of Distributed Constraint Satisfaction Problems (DCSP). The proposed model is called Controller-Agents for Constraints Solving (CACS). This model is intended to be used which is an emerged field from the integration between two paradigms of different nature: Multi-Agent Systems (MAS) and the Constraint Satisfaction Problem paradigm (CSP) where all constraints are treated in central manner as a black-box. This model allows grouping constraints to form a subset that will be treated together as a local problem inside the controller. Using this model allows also handling non-binary constraints easily and directly so that no translating of constraints into binary ones is needed. This paper presents the implementation outlines of a prototype of DCSP solver, its usage methodology and overview of the CACS application for timetabling problems.
Exponential Family Hybrid Semi-Supervised Learning
Venue: arXiv cs.LG 2010
Year: 2010

We present an approach to semi-supervised learning based on an exponential family characterization. Our approach generalizes previous work on coupled priors for hybrid generative/discriminative models. Our model is more flexible and natural than previous approaches. Experimental results on several data sets show that our approach also performs better in practice.
Automatically Discovering Hidden Transformation Chaining Constraints
Venue: arXiv cs.AI 2010
Year: 2010

Model transformations operate on models conforming to precisely defined metamodels. Consequently, it often seems relatively easy to chain them: the output of a transformation may be given as input to a second one if metamodels match. However, this simple rule has some obvious limitations. For instance, a transformation may only use a subset of a metamodel. Therefore, chaining transformations appropriately requires more information. We present here an approach that automatically discovers more detailed information about actual chaining constraints by statically analyzing transformations. The objective is to provide developers who decide to chain transformations with more data on which to base their choices. This approach has been successfully applied to the case of a library of endogenous transformations. They all have the same source and target metamodel but have some hidden chaining constraints. In such a case, the simple metamodel matching rule given above does not provide any useful information.
S-Program Calculus
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents a special subset of the first-order predicate logic named S-program calculus (briefly S-calculus). The S-calculus is a calculus consisting of so-called S-formulas that are defined over the abstract state space of a virtual machine. We show that S-formulas are a highly general tool for analyzing program semantics inasmuch as Hoare triplets of total and partial correctness are not more than two S-formulas. Moreover, all the rules of Hoare logic can be derived using S-formulas and axioms/theorems of first-order predicate calculus. The S-calculus is a powerful mechanism for proving program correctness as well as for building additional proving tools using theorems of the predicate logic. Every proof is based on deriving the validity of some S-formula, so the procedure may be automated using automatic theorem provers (we will use Coq in this paper). As an example of the use of S-calculus, we will prove the four basic properties of Dijsktra's operator wp. The proofs given by Dijkstra are not completely formalized and we will show that a full formalization can be achieved using S-calculus. Finally, we add one more theorem to the above-mentioned four, namely the law of negation.
Parallel structurally-symmetric sparse matrix-vector products on multi-core processors
Venue: arXiv cs.DC 2010
Year: 2010

We consider the problem of developing an efficient multi-threaded implementation of the matrix-vector multiplication algorithm for sparse matrices with structural symmetry. Matrices are stored using the compressed sparse row-column format (CSRC), designed for profiting from the symmetric non-zero pattern observed in global finite element matrices. Unlike classical compressed storage formats, performing the sparse matrix-vector product using the CSRC requires thread-safe access to the destination vector. To avoid race conditions, we have implemented two partitioning strategies. In the first one, each thread allocates an array for storing its contributions, which are later combined in an accumulation step. We analyze how to perform this accumulation in four different ways. The second strategy employs a coloring algorithm for grouping rows that can be concurrently processed by threads. Our results indicate that, although incurring an increase in the working set size, the former approach leads to the best performance improvements for most matrices.
Parameter-Free Deterministic Global Search with Central Force Optimization
Venue: arXiv cs.OH 2010
Year: 2010

This note describes a parameter-free implementation of Central Force Optimization for deterministic multidimensional search and optimization. The user supplies only one input: the objective function to be maximized, nothing more. The CFO equations of motion are simplified by assigning specific values to CFO's basic parameters, and this particular algorithmic implementation also includes hardwired internal parameters so that none is user-specified. The algorithm's performance is tested against a widely used suite of twenty three benchmark functions and compared to other state-of-the-art algorithms. CFO performs very well indeed. Includes important update 20 March 2010 addressing the issue of different probes coalescing into one.
Integrating Innate and Adaptive Immunity for Intrusion Detection
Venue: arXiv cs.AI 2010
Year: 2010

Network Intrusion Detection Systems (NDIS) monitor a network with the aim of discerning malicious from benign activity on that network. While a wide range of approaches have met varying levels of success, most IDS's rely on having access to a database of known attack signatures which are written by security experts. Nowadays, in order to solve problems with false positive alters, correlation algorithms are used to add additional structure to sequences of IDS alerts. However, such techniques are of no help in discovering novel attacks or variations of known attacks, something the human immune system (HIS) is capable of doing in its own specialised domain. This paper presents a novel immune algorithm for application to an intrusion detection problem. The goal is to discover packets containing novel variations of attacks covered by an existing signature base.
Cleaning Interval Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference |V(G)|-|V(H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as "cleaning" the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is |V(H)|.
Author Identifiers in Scholarly Repositories
Venue: arXiv cs.DL 2010
Year: 2010

Bibliometric and usage-based analyses and tools highlight the value of information about scholarship contained within the network of authors, articles and usage data. Less progress has been made on populating and using the author side of this network than the article side, in part because of the difficulty of unambiguously identifying authors. I briefly review a sample of author identifier schemes, and consider use in scholarly repositories. I then describe preliminary work at arXiv to implement public author identifiers, services based on them, and plans to make this information useful beyond the boundaries of arXiv.
Macro and micro view on steady states in state space
Venue: arXiv cs.GR 2010
Year: 2010

This paper describes visualization of chaotic attractor and elements of the singularities in 3D space. 3D view of these effects enables to create a demonstrative projection about relations of chaos generated by physical circuit, the Chua's circuit. Via macro views on chaotic attractor is obtained not only visual space illustration of representative point motion in state space, but also its relation to planes of singularity elements. Our created program enables view on chaotic attractor both in 2D and 3D space together with plane objects visualization -- elements of singularities.
The Comparison of Methods Artificial Neural Network with Linear Regression Using Specific Variables for Prediction Stock Price in Tehran Stock Exchange
Venue: arXiv cs.NE 2010
Year: 2010

In this paper, researchers estimated the stock price of activated companies in Tehran (Iran) stock exchange. It is used Linear Regression and Artificial Neural Network methods and compared these two methods. In Artificial Neural Network, of General Regression Neural Network method (GRNN) for architecture is used. In this paper, first, researchers considered 10 macro economic variables and 30 financial variables and then they obtained seven final variables including 3 macro economic variables and 4 financial variables to estimate the stock price using Independent components Analysis (ICA). So, we presented an equation for two methods and compared their results which shown that artificial neural network method is more efficient than linear regression method.
Use of Service Curve for Resource Reservation in Wired-cum-Wireless Scenario
Venue: arXiv cs.NI 2010
Year: 2010

In a network, arrival process is converted into departure process through network elements. The departure process suffer propagation delay in the link, processing delay at the network elements like router and data loss due to buffer overflow or congestion. For providing guaranteed service resources need to be reserved before conversation takes place. To reserve such resources estimation of them are indispensable. The idea of service curve gives beforehand deterministic value of these parameters. In this paper, we aim to minimum and maximum buffer space required in the router, minimum link capacity required to guarantee a pre-specified end-to-end delay for an ongoing session in a wired-cum-wireless scenario by analyzing minimum and maximum service curve. We assume that the network we are analyzing is an IP based mobile network. The findings of the work are presented in the form of tables which can be used for resource reservation to offer quality service to end-users.
Creating A Model HTTP Server Program Using java
Venue: arXiv cs.OH 2010
Year: 2010

HTTP Server is a computer programs that serves webpage content to clients. A webpage is a document or resource of information that is suitable for the World Wide Web and can be accessed through a web browser and displayed on a computer screen. This information is usually in HTML format, and may provide navigation to other webpage's via hypertext links. WebPages may be retrieved from a local computer or from a remote HTTP Server. WebPages are requested and served from HTTP Servers using Hypertext Transfer Protocol (HTTP). WebPages may consist of files of static or dynamic text stored within the HTTP Server's file system. Client-side scripting can make WebPages more responsive to user input once in the client browser. This paper encompasses the creation of HTTP server program using java language, which is basically supporting for HTML and JavaScript.
A New Variable Threshold and Dynamic Step Size Based Active Noise Control System for Improving Performance
Venue: arXiv cs.OH 2010
Year: 2010

Several approaches have been introduced in literature for active noise control (ANC) systems. Since FxLMS algorithm appears to be the best choice as a controller filter, researchers tend to improve performance of ANC systems by enhancing and modifying this algorithm. In this paper, modification is done in the existing FxLMS algorithm that provides a new structure for improving the tracking performance and convergence rate. The secondary signal y(n) is dynamic thresholded by Wavelet transform to improve tracking. The convergence rate is improved by dynamically varying the step size of the error signal.
On the Failure of the Finite Model Property in some Fuzzy Description Logics
Venue: arXiv cs.AI 2010
Year: 2010

Fuzzy Description Logics (DLs) are a family of logics which allow the representation of (and the reasoning with) structured knowledge affected by vagueness. Although most of the not very expressive crisp DLs, such as ALC, enjoy the Finite Model Property (FMP), this is not the case once we move into the fuzzy case. In this paper we show that if we allow arbitrary knowledge bases, then the fuzzy DLs ALC under Lukasiewicz and Product fuzzy logics do not verify the FMP even if we restrict to witnessed models; in other words, finite satisfiability and witnessed satisfiability are different for arbitrary knowledge bases. The aim of this paper is to point out the failure of FMP because it affects several algorithms published in the literature for reasoning under fuzzy ALC.
An Analytical Approach to Document Clustering Based on Internal Criterion Function
Venue: arXiv cs.IR 2010
Year: 2010

Fast and high quality document clustering is an important task in organizing information, search engine results obtaining from user query, enhancing web crawling and information retrieval. With the large amount of data available and with a goal of creating good quality clusters, a variety of algorithms have been developed having quality-complexity trade-offs. Among these, some algorithms seek to minimize the computational complexity using certain criterion functions which are defined for the whole set of clustering solution. In this paper, we are proposing a novel document clustering algorithm based on an internal criterion function. Most commonly used partitioning clustering algorithms (e.g. k-means) have some drawbacks as they suffer from local optimum solutions and creation of empty clusters as a clustering solution. The proposed algorithm usually does not suffer from these problems and converge to a global optimum, its performance enhances with the increase in number of clusters. We have checked our algorithm against three different datasets for four different values of k (required number of clusters).