7881691
Dynamic Refinement of Feature Weights Using Quantitative Introspective Learning
Recently more and more researchers have been supporting the view that learning is a goaldriven process. One of the key properties of a goal-driven learner is introspectiveness-the ability to notice the gaps in its knowledge and to reason about the information required to fill in those gaps. In this paper, we introduce a quantitative introspective learning paradigm into case-based reasoning (CBR). The result is an integrated problem-solving model which will learn introspectively feature weights in a case base in order to be responsive dynamically to its users. In contrast to the existing qualitative methods for introspective learning, our model has the advantage of being able to capture accurate learning information in the interactions with its users. A CBR system equipped with quantitative introspective learning ability can allow the feature weights to be captured automatically and to track its users' changing preferences continuously. In such a system, while the reasoning part is still case-based, the learning part is shouldered by a quantitative introspective learning model. Weight learning and evolution are accomplished in the background. The effectiveness of this integration will be demonstrated through a series of empirical experiments.
13595177
Multiple-Goal Recognition from Low-Level Signals
Researchers and practitioners from both the artificial intelligence and pervasive computing communities have been paying increasing attention to the task of inferring users' high-level goals from low-level sensor readings. A common assumption made by most approaches is that a user either has a single goal in mind, or achieves several goals sequentially. However, in real-world environments, a user often has multiple goals that are concurrently carried out, and a single action can serve as a common step towards multiple goals. In this paper, we formulate the multiple-goal recognition problem and exemplify it in an indoor environment where an RF-based wireless network is available. We propose a goal-recognition algorithm based on a dynamic model set and show how goal models evolve over time based on pre-defined states. Experiments with real data demonstrate that our method can accurately and efficiently recognize multiple interleaving goals in a user's trace.
9645876
Handling feature interactions in process-planning
Abstract The development of a successful approach to the integration of computer-aided design and computer-aided process-planning will require solutions to several fundamental problems in planning and geometric reasoning. In this article, we consider two such problems, both of which arise from interactions among machinable features. The first problem is that interactions can lead to several alternative interpretations of what the machinable features are. We address this problem by developing an algebra of features. The second problem is that interactions among features can cause problems in optimizing the process plans. For this problem, we have developed a branch-and-bound optimization algorithm with good heuristics to guide the search. This article presents the theory and mathematical framework for both problems and also the details of the implementation and experimental results.
15099164
A scalable supervised algorithm for dimensionality reduction on streaming data
Algorithms on streaming data have attracted increasing attention in the past decade. Among them, dimensionality reduction algorithms are greatly interesting due to the desirability of real tasks. Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are two of the most widely used dimensionality reduction approaches. However, PCA is not optimal for general classification problems because it is unsupervised and ignores valuable label information for classification. On the other hand, the performance of LDA is degraded when encountering limited available low-dimensional spaces and singularity problem. Recently, Maximum Margin Criterion (MMC) was proposed to overcome the shortcomings of PCA and LDA. Nevertheless, the original MMC algorithm could not satisfy the streaming data model to handle large-scale high-dimensional data set. Thus an effective, efficient and scalable approach is needed. In this paper, we propose a supervised incremental dimensionality reduction algorithm and its extension to infer adaptive low-dimensional spaces by optimizing the maximum margin criterion. Experimental results on a synthetic dataset and real datasets demonstrate the superior performance of our proposed algorithm on streaming data.
5296157
A Novel Scalable Algorithm for Supervised Subspace Learning
Subspace learning approaches aim to discover important statistical distribution on lower dimensions for high dimensional data. Methods such as principal component analysis (PCA) do not make use of the class information, and linear discriminant analysis (LDA) could not be performed efficiently in a scalable way. In this paper, we propose a novel highly scalable supervised subspace learning algorithm called as supervised Kampong measure (SKM). It assigns data points as close as possible to their corresponding class mean, simultaneously assigns data points to be as far as possible from the other class means in the transformed lower dimensional subspace. Theoretical derivation shows that our algorithm is not limited by the number of classes or the singularity problem faced by LDA. Furthermore, our algorithm can be executed in an incremental manner in which learning is done in an online fashion as data streams are received. Experimental results on several datasets, including a very large text data set RCV1, show the outstanding performance of our proposed algorithm on classification problems as compared to PCA, LDA and a popular feature selection approach, information gain (IG).
17216165
Cut-and-Pick Transactions for Proxy Log Mining
Web logs collected by proxy servers, referred to as proxy logs or proxy traces, contain information about Web document accesses by many users against many Web sites. This "many-to-many" characteristic poses a challenge to Web log mining techniques due to the difficulty in identifying individual access transactions. This is because in a proxy log, user transactions are not clearly bounded and are sometimes interleaved with each other as well as with noise. Most previous work has used simplistic measures such as a fixed time interval as a determination method for the transaction boundaries, and has not addressed the problem of interleaving and noisy transactions. In this paper, we show that this simplistic view can lead to poor performance in building models to predict future access patterns. We present a more advanced cut-and-pick method for determining the access transactions from proxy logs, by deciding on more reasonable transaction boundaries and by removing noisy accesses. Our method takes advantage of the user behavior that in most transactions, the same user typically visits multiple, related Web sites that form clusters. These clusters can be discovered by our algorithm based on the connectivity among Web sites. By using real-world proxy logs, we experimentally show that this cut-and-pick method can produce more accurate transactions that result in Web-access prediction models with higher accuracy.
7030953
Energy-aware partitioning for multiprocessor real-time systems
In this paper, we address the problem of partitioning periodic real-time tasks in a multiprocessor platform by considering both feasibility and energy-awareness perspectives: our objective is to compute the feasible partitioning that results in minimum energy consumption on multiple identical processors by using variable voltage earliest-deadline-first scheduling. We show that the problem is NP-hard in the strong sense on m /spl ges/ 2 processors even when feasibility is guaranteed a priori. Then, we develop our framework where load balancing plays a major role in producing energy-efficient partitionings. We evaluate the feasibility and energy-efficiency performances of partitioning heuristics experimentally.
20437986
Design and analysis of multiple-bus arbiters with different priority schemes
The authors present four multiple-user and multiple-server arbiter designs of multiple-bus multiprocessors. All designs are based on decentralized control, which has the advantage of good reliability and potentially high throughput. The priority protocols considered are fixed priority, rotating priority, round-robin priority, and equal priority. For the first two priority protocols, lookahead techniques are used to speed up the arbitration process. The round-robin protocol is based on the decentralized daisy-chain idea and is operated in an asynchronous fashion. Analytical models are developed for the four different priority protocols to evaluate the performance of the different designs. The analyses are based on a probabilistic model for the synchronous case and simple queuing analysis for the asynchronous system. Numerical results obtained from the proposed model show that the equal priority protocol performs better than the others in the system with a few buses. The performance difference is not significant when the number of buses is relatively large.<<ETX>>
229042
Introducing a New Cache Design into Vector Computers
Introduces an innovative cache design for vector computers, called prime-mapped cache. By utilizing the special properties of a Mersenne prime, the new design does not increase the critical path length of a processor, nor does it increase the cache access time as compared to existing cache organizations. The prime-mapped cache minimizes cache miss ratio caused by line interferences that have been shown to be critical for numerical applications by previous investigators. With negligibly additional hardware cost, significant performance gains are obtained by adding the proposed cache memory to an existing vector computer. The performance of the design is studied analytically, using a generic vector computation model. The analytical model is validated through extensive simulation experiments. A performance analysis for various vector access patterns shows that the prime-mapped cache performs significantly better than conventional cache organizations in the vector processing environment. The performance gain will increase with the increase of the speed gap between processors and memories. >
36641724
A new and efficient FFT algorithm for distributed memory systems
This paper presents a new and optimal parallel implementation of multidimensional fast Fourier transform algorithm on distributed memory multiprocessors. Its optimality is obtained by minimizing the number of message passings necessary, at the cost of increase in message length. This distinctive feature of the new algorithm effectively utilizes the important architectural property of most of today's distributed memory multiprocessors-wormhole routing for interprocessor communications. By using the algebra of stride permutations and tenser products as a mathematical tool, we are able to derive and formulate an efficient data partition and communication scheme that reduces communication cost from O(N/sup 2/) required for the best known FFT to O(N) on an N/sup 2/-processor machine. Our data partition scheme is natural and efficient for solving discretized boundary value problems such as partial differential equations and finite element analysis. To evaluate the actual performance of our new algorithm in comparison with other existing parallel FFT algorithms, we have carried out implementation experiments on the Intel's Touchstone Delta machine.
13076928
Coverage Algorithm and Protocol in Heterogeneous Sensor Networks
One fundamental issue in wireless sensor networks is the coverage problem. In heterogeneous sensor networks composed of different types of sensors, the difference of the sensing radius of nodes augments the computation difficulty of coverage degree. In this paper, we analyze the features of heterogeneous sensor networks and discuss the approaches to guarantee and calculate the coverage degree of the region deployed by heterogeneous sensor networks. Based on our analysis, a Distributed Coverage Optimization Algorithm by which each node in the network can determine whether it should be turn active/inactive is proposed. Simulation shows that our algorithm can make the extraneous nodes inactive and minimize the number of nodes need to remain active.