3813357
Video data mining: semantic indexing and event detection from the association perspective
Advances in the media and entertainment industries, including streaming audio and digital TV, present new challenges for managing and accessing large audio-visual collections. Current content management systems support retrieval using low-level features, such as motion, color, and texture. However, low-level features often have little meaning for naive users, who much prefer to identify content using high-level semantics or concepts. This creates a gap between systems and their users that must be bridged for these systems to be used effectively. To this end, in this paper, we first present a knowledge-based video indexing and content management framework for domain specific videos (using basketball video as an example). We will provide a solution to explore video knowledge by mining associations from video data. The explicit definitions and evaluation measures (e.g., temporal support and confidence) for video associations are proposed by integrating the distinct feature of video data. Our approach uses video processing techniques to find visual and audio cues (e.g., court field, camera motion activities, and applause), introduces multilevel sequential association mining to explore associations among the audio and visual cues, classifies the associations by assigning each of them with a class label, and uses their appearances in the video to construct video indices. Our experimental results demonstrate the performance of the proposed approach.
5944615
Eliminating Class Noise in Large Datasets
This paper presents a new approach for identifying and eliminating mislabeled instances in large or distributed datasets. We first partition a dataset into subsets, each of which is small enough to be processed by an induction algorithm at one time. We construct good rules from each subset, and use the good rules to evaluate the whole dataset. For a given instance Ik, two error count variables are used to count the number of times it has been identified as noise by all subsets. The instance with higher error values will have a higher probability of being a mislabeled example. Two threshold schemes, majority and non-objection, are used to identify the noise. Experimental results and comparative studies from real-world datasets are reported to evaluate the effectiveness and efficiency of the proposed approach.
5621999
Accelerated Kernel Feature Analysis
A fast algorithm, Accelerated Kernel Feature Analysis (AKFA), that discovers salient features evidenced in a sample of n unclassified patterns, is presented. Like earlier kernel-based feature selection algorithms, AKFA implicitly embeds each pattern into a Hilbert space, H, induced by a Mercer kernel. An \ell-dimensional linear subspace of H is iteratively constructed by maximizing a variance condition for the nonlinearly transformed sample. This linear subspace can then be used to define more efficient data representations and pattern classifiers. AKFA requires O(\elln2) operations, as compared to 0(n^3) for Sch¨olkof, Smola, and M¨uller’s Kernel Principal Component Analysis (KPCA), and O(\ell^2 n^2) for Smola, Mangasarian, and Sch¨olkopf’s Sparse Kernel Feature Analysis (SKFA). Numerical experiments show that AKFA can generate more concise feature representations than both KPCA and SKFA, and demonstrate that AKFA obtains similar classification performance as KPCA for a face recognition problem.
1654569
Qualitative Camera Motion Classification for Content-Based Video Indexing
Due to the fact that the camera motion usually imply some hints which are helpful in bridging the gap between computationally available features and semantic interpretations, extensive researches have been executed to extract them for various purposes. However, these strategies fail to classify the camera rotation; furthermore, their performance might be significantly reduced by considerable noise or error in extracted features. In this paper, a robust camera motion classification strategy is proposed. We use the mutual relationship between motion vectors for motion classification. Given any two motion vectors in each P-frame, four types of mutual relationships between them are classified, then, a 14-bins feature vector is constructed to characterize the statistical motion information for the P-frame. Finally, the qualitative classification is executed by considering all achieved statistical information.
1977839
Effective classification of noisy data streams with attribute-oriented dynamic classifier selection
Recently, mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a new dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single “best” classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence.
17434758
An Empirical Study of the Noise Impact on Cost-Sensitive Learning
In this paper, we perform an empirical study of the impact of noise on cost-sensitive (CS) learning, through observations on how a CS learner reacts to the mislabeled training examples in terms of misclassification cost and classification accuracy. Our empirical results and theoretical analysis indicate that mislabeled training examples can raise serious concerns for cost-sensitive classification, especially when misclassifying some classes becomes extremely expensive. Compared to general inductive learning, the problem of noise handling and data cleansing is more crucial, and should be carefully investigated to ensure the success of CS learning.
3096549
Kernel conditional random fields: representation and clique selection
Kernel conditional random fields (KCRFs) are introduced as a framework for discriminative modeling of graph-structured data. A representer theorem for conditional graphical models is given which shows how kernel conditional random fields arise from risk minimization procedures defined using Mercer kernels on labeled graphs. A procedure for greedily selecting cliques in the dual representation is then proposed, which allows sparse representations. By incorporating kernels and implicit feature spaces into conditional graphical models, the framework enables semi-supervised learning algorithms for structured data through the use of graph kernels. The framework and clique selection methods are demonstrated in synthetic data experiments, and are also applied to the problem of protein secondary structure prediction.
52810083
A hierarchical modeling framework for on-chip communication architectures
The communication sub-system of complex IC systems is increasingly critical for achieving system performance. Given this, it is important that the on-chip communication architecture should be included in any quantitative evaluation of system design during design space exploration. While there are several mature methodologies for the modeling and evaluation of architectures of processing elements, there is relatively little work done in modeling of an extensive range of on-chip communication architectures, and integrating this into a single modeling and simulation environment combining processing element and on-chip communication architectures. This paper describes a modeling framework with accompanying simulation tools that attempts to fill this gap. Based on an analysis of a wide range of on-chip communication architectures, we describe how a specific hierarchical class library can be used to develop new on-chip communication architectures, or variants of existing ones with relatively little incremental effort. We demonstrate this through three case studies including two commercial on-chip bus systems and an on-chip packet switching network. Here we show that through careful analysis and construction it is possible for the modeling environment to support the common features of these architectures as part of the library and permit instantiation of the individual architectures as variants of the library design. As part of this methodology we also show how different levels of abstraction of the model can be supported and viewed as different variants that can be used in an accuracy versus simulation time trade-off.
25871713
A Polynomial Algorithm for Homomorphisms to Oriented Cycles
W. Gutjahr, E. Welzl, and G. Woeginger have given a polynomial time algorithm to decide whether a given digraph is homomorphic to an oriented path. The corresponding problem for oriented cycles (i.e., given a digraph G, is it homomorphic to a fixed oriented cycle C?) remained open. We prove that if C is an unbalanced cycle then this problem is polynomial time decidable.
1166908
Distributed rate allocation for multi-stream video transmission over ad hoc networks
When multiple video streams are present in an ad hoc network, they share and compete for the common network resources. A rate allocation algorithm must balance the available resources among the video streams in a fair and efficient manner. In addition, it is desirable to have a distributed solution so that nodes do not need to collect global information of the network and that the computational burden can be shared. We propose a distributed rate allocation algorithm which minimizes the total distortion of all video streams. Based on the subgradient method, the proposed scheme only requires link price updates at each relay node based on local observations and rate adaptations at each source node derived from rate-distortion (RD) models of the video. Simulation results show that the proposed scheme can achieve the same optimal rate allocation as that obtained from exhaustive search.
152494
Tight relation between the circular chromatic number and the girth of series-parallel graphs
This paper proves the sharpness of an upper bound for the circular chromatic number of series-parallel graphs of large girth.