927509
Edge-adaptive prediction for lossless image coding
We design an edge-adaptive predictor for lossless image coding. The predictor adaptively weights a four-directional predictor together with an adaptive linear predictor based on information from neighbouring pixels. Although conceptually simple, the performance of the resulting coder is comparable to state-of-the-art image coders when a simple context-based coder is used to encode the prediction errors.
2748729
Partially Supervised Classification of Text Documents
We investigate the following problem: Given a set of documents of a particular topic or class P , and a large set M of mixed documents that contains documents from class P and other types of documents, identify the documents from class P in M . The key feature of this problem is that there is no labeled nonP document, which makes traditional machine learning techniques inapplicable, as they all need labeled documents of both classes. We call this problem partially supervised classification. In this paper, we show that this problem can be posed as a constrained optimization problem and that under appropriate conditions, solutions to the constrained optimization problem will give good solutions to the partially supervised classification problem. We present a novel technique to solve the problem and demonstrate the effectiveness of the technique through extensive experimentation.
12294439
Learning to Separate Text Content and Style for Classification
Many text documents naturally have two kinds of labels. For example, we may label web pages from universities according to their categories, such as “student” or “faculty”, or according the source universities, such as “Cornell” or “Texas”. We call one kind of labels the content and the other kind the style. Given a set of documents, each with both content and style labels, we seek to effectively learn to classify a set of documents in a new style with no content labels into its content classes. Assuming that every document is generated using words drawn from a mixture of two multinomial component models, one content model and one style model, we propose a method named Cartesian EM that constructs content models and style models through Expectation Maximization and performs classification of the unknown content classes transductively. Our experiments on real-world datasets show the proposed method to be effective for style independent text content classification.
9023584
Text classification with kernels on the multinomial manifold
Support Vector Machines (SVMs) have been very successful in text classification. However, the intrinsic geometric structure of text data has been ignored by standard kernels commonly used in SVMs. It is natural to assume that the documents are on the multinomial manifold, which is the simplex of multinomial models furnished with the Riemannian structure induced by the Fisher information metric. We prove that the Negative Geodesic Distance (NGD) on the multinomial manifold is conditionally positive definite (cpd), thus can be used as a kernel in SVMs. Experiments show the NGD kernel on the multinomial manifold to be effective for text classification, significantly outperforming standard kernels on the ambient Euclidean space.
1176859
RankCut - A Domain Independent Forward Pruning Method for Games
Forward pruning, also known as selective search, is now employed in many strong game-playing programs. In this paper, we introduce RankCut – a domain independent forward pruning technique which makes use of move ordering, and prunes once no better move is likely to be available. Since gameplaying programs already perform move ordering to improve the performance of αβ search, this information is available at no extra cost. As RankCut uses additional information untapped by current forward pruning techniques, RankCut is a complementary forward pruning method that can be used with existing methods, and is able to achieve improvements even when conventional pruning techniques are simultaneously employed. We implemented RankCut in a modern open-source chess program, CRAFTY. RankCut reduces the game-tree size by approximately 10%-40% for search depths 8-12 while retaining tactical reliability, when implemented alongside CRAFTY’s existing forward pruning techniques.
37770250
A Theoretical Analysis of Query Selection for Collaborative Filtering
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple and fast algorithm for a theoretical model of this problem with a provable approximation guarantee, and prove that solving the problem exactly is NP-Hard.
9483777
Evading network anomaly detection systems: formal reasoning and practical techniques
Attackers often try to evade an intrusion detection system (IDS) when launching their attacks. There have been several published studies in evasion attacks, some with available tools, in the research community as well as the "hackers'' community. Our recent empirical case study showed that some payload-based network anomaly detection systems can be evaded by a polymorphic blending attack (PBA). The main idea of a PBA is to create each polymorphic instance in such a way that the statistics of attack packet(s) match the normal traffic profile. In this paper, we present a formal framework for the open problem: given an anomaly detection system and an attack, can one automatically generate its PBA instances? We show that in general, generating a PBA that optimally matches the normal traffic profile is a hard problem (NP-complete). However, the problem of finding a PBA can be reduced to the SAT or ILP problems so that solvers available in those domains can be used to find a near-optimal solution. We also present a heuristic (hill-climbing) to find an approximate solution. Our framework can not only expose how the IDS can be exploited by a PBA but also suggest how the IDS can be improved to prevent the PBA. We have experimented with our framework using the PAYL 1-gram and 2-gram anomaly detection system, and the results have validated our framework.
15482443
Applying data mining to intrusion detection: the quest for automation, efficiency, and credibility
Intrusion detection is an essential component of the layered computer security mechanisms. It requires accurate and efficient models for analyzing a large amount of system and network audit data. This paper is an overview of our research in applying data mining techniques to build intrusion detection models. We describe a framework for mining patterns from system and network audit data, and constructing features according to analysis of intrusion patterns. We discuss approaches for improving the run-time efficiency as well as the credibility of detection models. We report the ideas, algorithms, and prototype systems we have developed, and discuss open research problems.
16787004
Performance evaluation of a wireless hierarchical data dissemination system
Various techniques have been developed to improve the performance of wireless information services. Techniques such as information broadcasting, caching of frequently accessed data, and point-to-point channels for pull-based data requests are often used to reduce data access time. To efficiently utilize information broadcast, indexing and scheduling schemes are employed for the organization of data broadcast. Most of the studies in the literature focused either on individual technique or a combination of them with some restrictive assumptions. There is no study considering these techniques working together in an integrated manner. In this paper, we propose a dynamic data delivery model for wireless communication environments. An important feature of our model is that data are disseminated through various storage mediums according to the dynamically collected data access patterns. Various results are presented in a set of simulation studies, which give some of the intuitions behind the design of a wireless data delivery system.
9087977
Facial shape and 3D skin
**************** **************** **************** **************** **************** ************* We present novel ideas for facial shape and skin simulation on extremely detailed threedimensional facial meshes. Our input database is composed of a small number of scanned human faces with resolutions up to several million triangles, where even the pores are clearly distinguished. We show how to decompose the facial meshes into the global shape of the face plus skin detail (3D skin), and then to reconstitute them. Our modeling methodology allows us to simulate the exaggeration of the facial global shape, retaining the original skin detail, as well as to transfer 3D skin from one face to another. First, we represent all the input faces in terms of a homogeneous structure on the base model in low resolution by using mesh adaptation techniques. Second, the differences between the original mesh and a base mesh, which appear as skin detail, are captured and stored, so that each face is decomposed into the global shape (a base mesh) plus skin detail. Face reconstitution after global shape exaggeration and/or skin transfer enables delicate simulation of facial models. In addition, we can increase the resolution of any model scanned at a low resolution by transferring skin from a higher resolution model. Our method shows successful manipulation of the minute structure of 3D skin differently from other methods such as Normal Mapping, Displacement Mapping, Displaced Subdivision Surfaces, and Normal Meshes where none of these techniques show manipulation of minute structure like ours and only approximation is used while our method recovers the original structure. Copyright # 2006 John Wiley & Sons, Ltd.
5421860
DSI: A Fully Distributed Spatial Index for Location-Based Wireless Broadcast Services
Recent announcement of the MSN Direct Service has demonstrated the feasibility and industrial interest in utilizing wireless broadcast for pervasive information services. To support location-based services in wireless data broadcast systems, a distributed spatial index (called DSI) is proposed in this paper. DSI is highly efficient because it has a linear yet fully distributed structure that facilitates multiple search paths to be naturally mixed together by sharing links. Moreover, DSI is very resilient in error-prone wireless communication environments. Search algorithms for two classical location-based queries, window queries and kNN queries, based on DSI are presented. Performance evaluation of DSI shows that DSI significantly outperforms R-tree and Hilbert Curve Index, two state-of-the-art spatial indexing techniques for wireless data broadcast