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.
13530245
A robust codec for transmission of very low bit-rate video over channels with bursty errors
We describe a robust codec for the transmission of very low bit-rate video over channels with a variety of errors, including random and bursty bit errors and packet loss. The codec exploits adaptivity to give good performance with a low overhead. By only protecting macroblocks which would otherwise be poorly concealed by the decoder the codec allows adaptive selection of the parts of video to protect. For protection, it uses multiple description codes which indirectly provide frequency-based adaptivity by protecting the more significant DCT coefficients. Simulations show significant improvements in the performance of the codec when compared to codecs which use intra macroblock updating (raster scan and random) at the same overhead. The codec is efficient in its use of bits and has good error resilience properties both objectively and subjectively over a wide range of conditions. Further, transcoding of the received bit stream to the standard H.263 syntax is relatively easy.
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.
361066
Efficient agnostic learning of neural networks with bounded fan-in
We show that the class of two-layer neural networks with bounded fan-in is efficiently learnable in a realistic extension to the probably approximately correct (PAC) learning model. In this model, a joint probability distribution is assumed to exist on the observations and the learner is required to approximate the neural network which minimizes the expected quadratic error. As special cases, the model allows learning real-valued functions with bounded noise, learning probabilistic concepts, and learning the best approximation to a target function that cannot be well approximated by the neural network. The networks we consider have real-valued inputs and outputs, an unlimited number of threshold hidden units with bounded fan-in, and a bound on the sum of the absolute values of the output weights. The number of computation steps of the learning algorithm is bounded by a polynomial in 1//spl epsiv/, 1//spl delta/, n and B where /spl epsiv/ is the desired accuracy, /spl delta/ is the probability that the algorithm fails, n is the input dimension, and B is the bound on both the absolute value of the target (which may be a random variable) and the sum of the absolute values of the output weights. In obtaining the result, we also extended some results on iterative approximation of functions in the closure of the convex hull of a function class and on the sample complexity of agnostic learning with the quadratic loss function.
18738450
Robustness of multiplexing protocols for audio-visual services over wireless networks
The protocols used to multiplex the various streams in an audio-visual service (such as MPEG 2 systems and ITU-T H.223) have an important impact on the quality of the service. The fact that wireless channels are often associated with high bit-error rates which are often bursty means that the multiplexing protocols should be designed to be robust against such errors. We suggest two departures from traditional practice which can improve significantly the performance of a packet-oriented multiplex for use with audio-visual services: (1) where the packet header is protected against errors using forward error correcting codes, the use of a synchronization codeword (or flag) is often unnecessary, and (2) for channels where errors tend to occur in bursts, the occurrence of errors in the header can be reduced by transmitting the header information twice (at both ends of the packet) with a low level of FEC protection instead of using the same number of bits to obtain an increased level of protection using a single code word. The value of these approaches is confirmed by simulations.
37611527
The Importance of Convexity in Learning with Squared Loss
We show that if the closure of a function class F under the metric induced by some probability distribution is not convex, then the sample complexity for agnostically learning F with squared loss (using only hypotheses in F) is /spl Omega/(ln(1//spl delta/)//spl epsiv//sup 2/) where 1-/spl delta/ is the probability of success and /spl epsiv/ is the required accuracy. In comparison, if the class F is convex and has finite pseudodimension, then the sample complexity is O(1//spl epsiv/(ln(1//spl epsiv/)+ln(1/b)). If a nonconvex class F has finite pseudodimension, then the sample complexity for agnostically learning the closure of the convex hull of F, is O(1//spl epsiv/(1//spl epsiv/(ln(1//spl epsiv/)+ln(1//spl delta/)). Hence, for agnostic learning, learning the convex hull provides better approximation capabilities with little sample complexity penalty.
18052652
Cross-feature analysis for detecting ad-hoc routing anomalies
With the proliferation of wireless devices, mobile ad-hoc networking (MANET) has become a very exciting and important technology. However, MANET is more vulnerable than wired networking. Existing security mechanisms designed for wired networks have to be redesigned in this new environment. In this paper, we discuss the problem of intrusion detection in MANET. The focus of our research is on techniques for automatically constructing anomaly detection models that are capable of detecting new (or unseen) attacks. We introduce a new data mining method that performs "cross-feature analysis" to capture the inter-feature correlation patterns in normal traffic. These patterns can be used as normal profiles to detect deviation (or anomalies) caused by attacks. We have implemented our method on a few well known ad-hoc routing protocols, namely, Dynamic Source Routing (DSR) and Ad-hoc On-Demand Distance Vector (AODV), and have conducted extensive experiments on the ns-2 simulator. The results show that the anomaly detection models automatically computed using our data mining method can effectively, detect anomalies caused by typical routing intrusions.
30352251
An Efficient Algorithm for Rendering Large Bodies of Water
Water rendering is one of the most computationally demanding task in computer graphics. Because of its computational complexity, real-time water rendering requires high-end hardwares. In this paper, we present a new algorithm for real-time rendering of large bodies of water such as open seas and oceans which results in an improved efficiency. Using interactive frustum, water surface can be fluidly calculated as a function of height given and interaction with another player in games. This results in an efficient yet realistic method for rendering large bodies of water without requiring as much computational power.
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
454679
Heterogeneous networking: a new survivability paradigm
We believe that a network, to be survivable, must be heterogeneous. Just like a species that draws on a small gene pool can succumb to a single environmental threat, so a homogeneous network is vulnerable to a malicious attack that exploits a single weakness common to all of its components. In contrast, in a network in which each critical functionality is provided by a diverse set of protocols and implementations, attacks that focus on a weakness of one such protocol or implementation will not be able to bring down the entire network, even though all elements are not be bulletproof and even if some of components are compromised.Following this survivability through heterogeneity philosophy, we propose a new survivability paradigm, called heterogeneous networking, for improving a network's defense capabilities. Rather than following the current trend of converging towards single solutions to provide the desired functionality at every element of the network architecture, this methodology calls for systematically increasing the network's heterogeneity without sacrificing its interoperability.
15867299
Supporting XML Security Models Using Relational Databases: A Vision
As the secure distribution and sharing of information over the World Wide Web becomes increasingly important, the needs for flexible and efficient support of access control systems naturally arise. Since the eXtensible Markup Language (XML) is emerging as the format of the Internet era for storing and exchanging information, there have been, recently, many proposals to extend the XML model to incorporate security aspects. To the lesser or greater extent, however, such proposals neglect the fact that the data for XML documents will most likely reside in relational databases, and consequently do not utilize various security models proposed for and implemented in relational databases.