OpenRaiser/Intern-Atlas huggingface dataset:
Dimensionality Reduction and Classification feature using Mutual Information applied to Hyperspectral Images : A Filter strategy based algorithm
Venue: arXiv cs.CV 2012
Year: 2012

Hyperspectral images (HIS) classification is a high technical remote sensing tool. The goal is to reproduce a thematic map that will be compared with a reference ground truth map (GT), constructed by expecting the region. The HIS contains more than a hundred bidirectional measures, called bands (or simply images), of the same region. They are taken at juxtaposed frequencies. Unfortunately, some bands contain redundant information, others are affected by the noise, and the high dimensionality of features made the accuracy of classification lower. The problematic is how to find the good bands to classify the pixels of regions. Some methods use Mutual Information (MI) and threshold, to select relevant bands, without treatment of redundancy. Others control and eliminate redundancy by selecting the band top ranking the MI, and if its neighbors have sensibly the same MI with the GT, they will be considered redundant and so discarded. This is the most inconvenient of this method, because this avoids the advantage of hyperspectral images: some precious information can be discarded. In this paper we'll accept the useful redundancy. A band contains useful redundancy if it contributes to produce an estimated reference map that has higher MI with the GT.nTo control redundancy, we introduce a complementary threshold added to last value of MI. This process is a Filter strategy; it gets a better performance of classification accuracy and not expensive, but less preferment than Wrapper strategy.
A Literature Survey of Cooperative Caching in Content Distribution Networks
Venue: arXiv cs.NI 2012
Year: 2012

Content distribution networks (CDNs) which serve to deliver web objects (e.g., documents, applications, music and video, etc.) have seen tremendous growth since its emergence. To minimize the retrieving delay experienced by a user with a request for a web object, caching strategies are often applied - contents are replicated at edges of the network which is closer to the user such that the network distance between the user and the object is reduced. In this literature survey, evolution of caching is studied. A recent research paper [15] in the field of large-scale caching for CDN was chosen to be the anchor paper which serves as a guide to the topic. Research studies after and relevant to the anchor paper are also analyzed to better evaluate the statements and results of the anchor paper and more importantly, to obtain an unbiased view of the large scale collaborate caching systems as a whole.
Self-Delimiting Neural Networks
Venue: arXiv cs.NE 2012
Year: 2012

Self-delimiting (SLIM) programs are a central concept of theoretical computer science, particularly algorithmic information & probability theory, and asymptotically optimal program search (AOPS). To apply AOPS to (possibly recurrent) neural networks (NNs), I introduce SLIM NNs. Neurons of a typical SLIM NN have threshold activation functions. During a computational episode, activations are spreading from input neurons through the SLIM NN until the computation activates a special halt neuron. Weights of the NN's used connections define its program. Halting programs form a prefix code. The reset of the initial NN state does not cost more than the latest program execution. Since prefixes of SLIM programs influence their suffixes (weight changes occurring early in an episode influence which weights are considered later), SLIM NN learning algorithms (LAs) should execute weight changes online during activation spreading. This can be achieved by applying AOPS to growing SLIM NNs. To efficiently teach a SLIM NN to solve many tasks, such as correctly classifying many different patterns, or solving many different robot control tasks, each connection keeps a list of tasks it is used for. The lists may be efficiently updated during training. To evaluate the overall effect of currently tested weight changes, a SLIM NN LA needs to re-test performance only on the efficiently computable union of tasks potentially affected by the current weight changes. Future SLIM NNs will be implemented on 3-dimensional brain-like multi-processor hardware. Their LAs will minimize task-specific total wire length of used connections, to encourage efficient solutions of subtasks by subsets of neurons that are physically close. The novel class of SLIM NN LAs is currently being probed in ongoing experiments to be reported in separate papers.
Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling
Venue: arXiv cs.DS 2012
Year: 2012

Greedy heuristics may be attuned by looking ahead for each possible choice, in an approach called the rollout or Pilot method. These methods may be seen as meta-heuristics that can enhance (any) heuristic solution, by repetitively modifying a master solution: similarly to what is done in game tree search, better choices are identified using lookahead, based on solutions obtained by repeatedly using a greedy heuristic. This paper first illustrates how the Pilot method improves upon some simple well known dispatch heuristics for the job-shop scheduling problem. The Pilot method is then shown to be a special case of the more recent Monte Carlo Tree Search (MCTS) methods: Unlike the Pilot method, MCTS methods use random completion of partial solutions to identify promising branches of the tree. The Pilot method and a simple version of MCTS, using the $\varepsilon$-greedy exploration paradigms, are then compared within the same framework, consisting of 300 scheduling problems of varying sizes with fixed-budget of rollouts. Results demonstrate that MCTS reaches better or same results as the Pilot methods in this context.
Combined Descriptors in Spatial Pyramid Domain for Image Classification
Venue: arXiv cs.CV 2012
Year: 2012

Recently spatial pyramid matching (SPM) with scale invariant feature transform (SIFT) descriptor has been successfully used in image classification. Unfortunately, the codebook generation and feature quantization procedures using SIFT feature have the high complexity both in time and space. To address this problem, in this paper, we propose an approach which combines local binary patterns (LBP) and three-patch local binary patterns (TPLBP) in spatial pyramid domain. The proposed method does not need to learn the codebook and feature quantization processing, hence it becomes very efficient. Experiments on two popular benchmark datasets demonstrate that the proposed method always significantly outperforms the very popular SPM based SIFT descriptor method both in time and classification accuracy.
Essential Convexity and Complexity of Semi-Algebraic Constraints
Venue: arXiv cs.CC 2012
Year: 2012

Let Γbe a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for Γ: the problem to decide whether a given primitive positive sentence is true in Γ. We focus on those structures Γthat contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If Γcontains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for Γis NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if Γis a first-order expansion of (R;*,+), then the CSP for Γcan be solved in polynomial time if and only if all relations in Γare essentially convex (unless P=NP).
Combinatorics and the Rigidity of CAD Systems
Venue: arXiv cs.DM 2012
Year: 2012

We study the rigidity of body-and-cad frameworks which capture the majority of the geometric constraints used in 3D mechanical engineering CAD software. We present a combinatorial characterization of the generic minimal rigidity of a subset of body-and-cad frameworks in which we treat 20 of the 21 body-and-cad constraints, omitting only point-point coincidences. While the handful of classical combinatorial characterizations of rigidity focus on distance constraints between points, this is the first result simultaneously addressing coincidence, angular, and distance constraints. Our result is stated in terms of the partitioning of a graph into edge-disjoint spanning trees. This combinatorial approach provides the theoretical basis for the development of deterministic algorithms (that will not depend on numerical methods) for analyzing the rigidity of body-and-cad frameworks.
Memory Constraint Online Multitask Classification
Venue: arXiv cs.LG 2012
Year: 2012

We investigate online kernel algorithms which simultaneously process multiple classification tasks while a fixed constraint is imposed on the size of their active sets. We focus in particular on the design of algorithms that can efficiently deal with problems where the number of tasks is extremely high and the task data are large scale. Two new projection-based algorithms are introduced to efficiently tackle those issues while presenting different trade offs on how the available memory is managed with respect to the prior information about the learning tasks. Theoretically sound budget algorithms are devised by coupling the Randomized Budget Perceptron and the Forgetron algorithms with the multitask kernel. We show how the two seemingly contrasting properties of learning from multiple tasks and keeping a constant memory footprint can be balanced, and how the sharing of the available space among different tasks is automatically taken care of. We propose and discuss new insights on the multitask kernel. Experiments show that online kernel multitask algorithms running on a budget can efficiently tackle real world learning problems involving multiple tasks.
Sparse LMS via Online Linearized Bregman Iteration
Venue: arXiv cs.IT 2012
Year: 2012

We propose a version of least-mean-square (LMS) algorithm for sparse system identification. Our algorithm called online linearized Bregman iteration (OLBI) is derived from minimizing the cumulative prediction error squared along with an l1-l2 norm regularizer. By systematically treating the non-differentiable regularizer we arrive at a simple two-step iteration. We demonstrate that OLBI is bias free and compare its operation with existing sparse LMS algorithms by rederiving them in the online convex optimization framework. We perform convergence analysis of OLBI for white input signals and derive theoretical expressions for both the steady state and instantaneous mean square deviations (MSD). We demonstrate numerically that OLBI improves the performance of LMS type algorithms for signals generated from sparse tap weights.
Graph-Based Approaches to Clustering Network-Constrained Trajectory Data
Venue: arXiv cs.LG 2012
Year: 2012

Even though clustering trajectory data attracted considerable attention in the last few years, most of prior work assumed that moving objects can move freely in an euclidean space and did not consider the eventual presence of an underlying road network and its influence on evaluating the similarity between trajectories. In this paper, we present two approaches to clustering network-constrained trajectory data. The first approach discovers clusters of trajectories that traveled along the same parts of the road network. The second approach is segment-oriented and aims to group together road segments based on trajectories that they have in common. Both approaches use a graph model to depict the interactions between observations w.r.t. their similarity and cluster this similarity graph using a community detection algorithm. We also present experimental results obtained on synthetic data to showcase our propositions.
Multibiometric: Feature Level Fusion Using FKP Multi-Instance biometric
Venue: arXiv cs.CV 2012
Year: 2012

This paper proposed the use of multi-instance feature level fusion as a means to improve the performance of Finger Knuckle Print (FKP) verification. A log-Gabor filter has been used to extract the image local orientation information, and represent the FKP features. Experiments are performed using the FKP database, which consists of 7,920 images. Results indicate that the multi-instance verification approach outperforms higher performance than using any single instance. The influence on biometric performance using feature level fusion under different fusion rules have been demonstrated in this paper.
Detecting multiword phrases in mathematical text corpora
Venue: arXiv cs.CL 2012
Year: 2012

We present an approach for detecting multiword phrases in mathematical text corpora. The method used is based on characteristic features of mathematical terminology. It makes use of a software tool named Lingo which allows to identify words by means of previously defined dictionaries for specific word classes as adjectives, personal names or nouns. The detection of multiword groups is done algorithmically. Possible advantages of the method for indexing and information retrieval and conclusions for applying dictionary-based methods of automatic indexing instead of stemming procedures are discussed.
Performance Constraint and Power-Aware Allocation For User Requests In Virtual Computing Lab
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing is driven by economies of scale. A cloud system uses virtualization technology to provide cloud resources (e.g. CPU, memory) to users in form of virtual machines. Virtual machine (VM), which is a sandbox for user application, fits well in the education environment to provide computational resources for teaching and research needs. In resource management, they want to reduce costs in operations by reducing expensive cost of electronic bill of large-scale data center system. A lease-based model is suitable for our Virtual Computing Lab, in which users ask resources on a lease of virtual machines. This paper proposes two host selection policies, named MAP (minimum of active physical hosts) and MAP-H2L, and four algorithms solving the lease scheduling problem. FF-MAP, FF-MAP-H2L algorithms meet a trade-off between the energy consumption and Quality of Service (e.g. performance). The simulation on 7-day workload, which converted from LLNL Atlas log, showed the FF-MAP and FF-MAP-H2L algorithms reducing 7.24% and 7.42% energy consumption than existing greedy mapping algorithm in the leasing scheduler Haizea. In addition, we introduce a ratio θof consolidation in HalfPI-FF-MAP and PI-FF-MAP algorithms, in which θis π/2 and π, and results on their simulations show that energy consumption decreased by 34.87% and 63.12% respectively.
JooFlux: Hijacking Java 7 InvokeDynamic To Support Live Code Modifications
Venue: arXiv cs.OS 2012
Year: 2012

Changing functional and non-functional software implementation at runtime is useful and even sometimes critical both in development and production environments. JooFlux is a JVM agent that allows both the dynamic replacement of method implementations and the application of aspect advices. It works by doing bytecode transformation to take advantage of the new invokedynamic instruction added in Java SE 7 to help implementing dynamic languages for the JVM. JooFlux can be managed using a JMX agent so as to operate dynamic modifications at runtime, without resorting to a dedicated domain-specific language. We compared JooFlux with existing AOP platforms and dynamic languages. Results demonstrate that JooFlux performances are close to the Java ones --- with most of the time a marginal overhead, and sometimes a gain --- where AOP platforms and dynamic languages present significant overheads. This paves the way for interesting future evolutions and applications of JooFlux.
Turing machines based on unsharp quantum logic
Venue: arXiv cs.LO 2012
Year: 2012

In this paper, we consider Turing machines based on unsharp quantum logic. For a lattice-ordered quantum multiple-valued (MV) algebra E, we introduce E-valued non-deterministic Turing machines (ENTMs) and E-valued deterministic Turing machines (EDTMs). We discuss different E-valued recursively enumerable languages from width-first and depth-first recognition. We find that width-first recognition is equal to or less than depth-first recognition in general. The equivalence requires an underlying E value lattice to degenerate into an MV algebra. We also study variants of ENTMs. ENTMs with a classical initial state and ENTMs with a classical final state have the same power as ENTMs with quantum initial and final states. In particular, the latter can be simulated by ENTMs with classical transitions under a certain condition. Using these findings, we prove that ENTMs are not equivalent to EDTMs and that ENTMs are more powerful than EDTMs. This is a notable difference from the classical Turing machines.
Properties of Stochastic Kronecker Graph
Venue: arXiv cs.SI 2012
Year: 2012

The stochastic Kronecker Graph model can generate large random graph that closely resembles many real world networks. For example, the output graph has a heavy-tailed degree distribution, has a (low) diameter that effectively remains constant over time and obeys the so-called densification power law [1]. Aside from this list of very important graph properties, one may ask for some additional information about the output graph: What will be the expected number of isolated vertices? How many edges, self loops are there in the graph? What will be the expected number of triangles in a random realization? Here we try to answer the above questions. In the first phase, we bound the expected values of the aforementioned features from above. Next we establish the sufficient conditions to generate stochastic Kronecker graph with a wide range of interesting properties. Finally we show two phase transitions for the appearance of edges and self loops in stochastic Kronecker graph.
Revisiting Content Availability in Distributed Online Social Networks
Venue: arXiv cs.NI 2012
Year: 2012

Online Social Networks (OSN) are among the most popular applications in today's Internet. Decentralized online social networks (DOSNs), a special class of OSNs, promise better privacy and autonomy than traditional centralized OSNs. However, ensuring availability of content when the content owner is not online remains a major challenge. In this paper, we rely on the structure of the social graphs underlying DOSN for replication. In particular, we propose that friends, who are anyhow interested in the content, are used to replicate the users content. We study the availability of such natural replication schemes via both theoretical analysis as well as simulations based on data from OSN users. We find that the availability of the content increases drastically when compared to the online time of the user, e. g., by a factor of more than 2 for 90% of the users. Thus, with these simple schemes we provide a baseline for any more complicated content replication scheme.
A Framework for Joint Design of Pilot Sequence and Linear Precoder
Venue: arXiv cs.IT 2012
Year: 2012

Most performance measures of pilot-assisted multiple-input multiple-output (MIMO) systems are functions that depend on both the linear precoding filter and the pilot sequence. A framework for the optimization of these two parameters is proposed, based on a matrix-valued generalization of the concept of effective signal-to-noise ratio (SNR) introduced in a famous work by Hassibi and Hochwald. The framework applies to a wide class of utility functions of said effective SNR matrix, most notably a well-known mutual information expression for Gaussian inputs, an upper bound on the minimum mean-square error (MMSE), as well as approximations thereof. The approach consists in decomposing the joint optimization problem into three subproblems: first, we describe how to reformulate the optimization of the linear precoder subject to a fixed pilot sequence as a convex problem. Second, we do likewise for the optimization of the pilot sequence subject to a fixed precoder. Third, we describe how to generate pairs of precoders and pilot sequences that are Pareto optimal in the sense that they attain the Pareto boundary of the set of feasible effective SNR matrices. By combining these three optimization problems into an iteration, we obtain an algorithm which allows to compute jointly optimal pairs of precoders and pilot sequences with respect to some generic utility function of the effective SNR.
Turing Patterns with Turing Machines: Emergence and Low-level Structure Formation
Venue: arXiv cs.CC 2012
Year: 2012

Despite having advanced a reaction-diffusion model of ODE's in his 1952 paper on morphogenesis, reflecting his interest in mathematical biology, Alan Turing has never been considered to have approached a definition of Cellular Automata. However, his treatment of morphogenesis, and in particular a difficulty he identified relating to the uneven distribution of certain forms as a result of symmetry breaking, are key to connecting his theory of universal computation with his theory of biological pattern formation. Making such a connection would not overcome the particular difficulty that Turing was concerned about, which has in any case been resolved in biology. But instead the approach developed here captures Turing's initial concern and provides a low-level solution to a more general question by way of the concept of algorithmic probability, thus bridging two of his most important contributions to science: Turing pattern formation and universal computation. I will provide experimental results of one-dimensional patterns using this approach, with no loss of generality to a n-dimensional pattern generalisation.
Efficient Tabling of Structured Data with Enhanced Hash-Consing
Venue: arXiv cs.PL 2012
Year: 2012

Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called input sharing and hash code memoization, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.