Search

Qualitative path is a basic concept in qualitative motion reasoning. In this paper, we propose an algorithm for reasoning the qualitative path in Voronoi-Adjacency-Relation Space. Different from the previous approach in which both the dynamic Voronoi edges and the initial position are required, our approach only needs the dynamic Voronoi edges. The basic idea is that the algorithm tracks all possible initial positions, gradually rules out the impossible situation and ultimately gets the correct path. Finally, experiments have been conducted and results show that the proposed algorithm is effective.

Online kernel selection is critical to online kernel learning. However, the time complexity of existing online kernel selection algorithms of each round is linear with respect to the number of examples already arrived. This is not efficient for online learning. To address this issue, we propose a novel stochastic online kernel selection algorithm via the random feature mapping and using the instantaneous loss. This algorithm has only constant time complexity at each round and theoretical guarantee. Formally, the algorithm first maps the arriving example into the random feature space. Then the algorithm updates the kernel parameter and the weights of the classifier simultaneously using SGD (stochastic gradient descent) to minimize the instantaneous loss. We also prove that the algorithm enjoys a sub-linear regret bound. Experimental results on benchmark datasets demonstrate that the proposed algorithm is effective and efficient.

Enhanced Qualitative Probabilistic Network (QPN) is to make qualitative network more applicable by reducing ambiguity in a qualitative way. To reduce ambiguity in the basic QPN inference, we propose an enhanced QPN based on qualitative mutual information (QMI), named QMIQPN. Firstly, we give a strict definition of QMI. Secondly, based on the definition, we present the formalism of QMIQPN. Specifically, we take QMI as the strength of qualitative influence in QMIQPN, the qualitative influence with strength differs from the previous work, which additional expressiveness of the enhancement does not come at the expense of the property of symmetry of influence. Thirdly, we analyze several relative properties of qualitative influences with strengths. Furthermore, we improve the Sign-propagation Algorithm to reduce ambiguity and discuss its complexity. Finally, by experiments on several databases, we analyze the performance of QMIQPN. Theoretic analysis and experimental results illustrate that QMIQPN is qualitative and efficient, yet allows for reducing some ambiguities upon QPN inference.

The integration of uncertain information from different time sources is a crucial issue in various applications. In this paper, we propose an integration method of multiple Temporal Qualitative Probabilistic Networks (TQPNs) in time series environments. First, we present the method for learning TQPN from time series data. The TQPN's structure is constructed using Dynamic Bayesian Networks learning based on Markov Chain Monte Carlo. Furthermore, the corresponding qualitative influences are obtained by the conditional probabilities. Secondly, based on rough set theory, we integrate multiple TQPNs into a single QPN that preserves as much information as possible. Specifically, we take the rough-set-based dependency degree as the strength of qualitative influence, and then make the rules to solve the ambiguities reduction and cycles deletion problems which arise from the integration of different TQPNs. Finally, we verify the feasibility of the integration method by the simulation experiments.

Objective. To investigate differences in tongue images of subjects with and without hyperuricemia.Materials and Methods. This population-based case-control study was performed in 2012-2013. We collected data from 46 case subjects with hyperuricemia and 46 control subjects, including results of biochemical examinations and tongue images. Symmetrical Haar-like features based on integral images were extracted from tongue images.T-tests were performed to determine the ability of extracted features to distinguish between the case and control groups. We first selected features using the common criterionP<0.05, then conducted further examination of feature characteristics and feature selection using means and standard deviations of distributions in the case and control groups.Results. A total of 115,683 features were selected using the criterionP<0.05. The maximum area under the receiver operating characteristic curve (AUC) of these features was 0.877. The sensitivity of the feature with the maximum AUC value was 0.800 and specificity was 0.826 when the Youden index was maximized. Features that performed well were concentrated in the tongue root region.Conclusions. Symmetrical Haar-like features enabled discrimination of subjects with and without hyperuricemia in our sample. The locations of these discriminative features were in agreement with the interpretation of tongue appearance in traditional Chinese and Western medicine.

Model selection in kernel methods is the problem of choosing an appropriate hypothesis space for kernel-based learning algorithms to avoid either underfitting or overfitting of the resulting hypothesis. One of main problems faced by model selection is how to control the sample complexity when designing the model selection criterion. In this paper, we take balls of reproducing kernel Hilbert spaces (RKHSs) as candidate hypothesis spaces and propose a novel model selection criterion via minimizing the empirical optimal error in the ball of RKHS and the covering number of the ball. By introducing the covering number to measure the capacity of the ball of RKHS, our criterion could directly control the sample complexity. Specifically, we first prove the relation between expected optimal error and empirical optimal error in the ball of RKHS. Using the relation as the theoretical foundation, we give the definition of our criterion. Then, by estimating the expectation of optimal empirical error and proving an upper bound of the covering number, we represent our criterion as a functional of the kernel matrix. An efficient algorithm is further developed for approximately calculating the functional so that the fast Fourier transform (FFT) can be applied to achieve a quasi-linear computational complexity. We also prove the consistency between the approximate criterion and the accurate one for large enough samples. Finally, we empirically evaluate the performance of our criterion and verify the consistency between the approximate and accurate criterion.

In this paper, we cluster a unlabeled human wrist pulse signal data set via a multiple criteria decision making (MCDM) framework to mine useful information for further study. First, a preprocessing scheme is performed and spatial features are extracted to represent a pulse signal. Then, a list of clustering algorithms are initialized to generate a number of clustering alternatives. The goodness of these clustering alternatives are sequentially comprehensively evaluated by 11 criteria, including ten internal cluster validation indices and an ad-hoc index, the robustness to noise, which is proposed for assessing the clustering alternatives of the pulse data set with spatial features. Taking the evaluation results as inputs, the technique for order preference by similarity to ideal solution (TOPSIS) method is employed to solve the resulting MCDM model. According to the TOPSIS rank, clustering the data set into thirteen clusters via k-means is optimal. Samples drawn from each cluster have similar patterns, corresponding to specific pulse type in traditional Chinese pulse diagnosis. The thirteen clusters are segregated into two groups, namely the healthy and the unhealthy, which can be further applied for unhealthy pulse detection.

Background. Minimization is a case allocation method for randomized controlled trials (RCT). Evidence suggests that the minimization method achieves balanced groups with respect to numbers and participant characteristics, and can incorporate more prognostic factors compared to other randomization methods. Although several automatic allocation systems exist (e.g., randoWeb, and MagMin), the minimization method is still difficult to implement, and RCTs seldom employ minimization. Therefore, we developed the minimization allocation controlled trials (MACT) system, a generic manageable minimization allocation system.System Outline. The MACT system implements minimization allocation by Web and email. It has a unified interface that manages trials, participants, and allocation. It simultaneously supports multitrials, multicenters, multigrouping, multiple prognostic factors, and multilevels.Methods. Unlike previous systems, MACT utilizes an optimized database that greatly improves manageability.Simulations and Results. MACT was assessed in a series of experiments and evaluations. Relative to simple randomization, minimization produces better balance among groups and similar unpredictability.Applications. MACT has been employed in two RCTs that lasted three years. During this period, MACT steadily and simultaneously satisfied the requirements of the trial.Conclusions. MACT is a manageable, easy-to-use case allocation system. Its outstanding features are attracting more RCTs to use the minimization allocation method.

Kernel methods play an important role in machine learning, pattern recognition and data mining. Although the kernel functions are the central part of the kernel methods, little is known about the structure of its reproducing kernel Hilbert spaces (RKHS) and the eigenvalues of the integral operator. In this paper, we first give the definition of the extended Gaussian kernel which includes the Gaussian kernel as its special case. Then, through a generalization form of the Weyl inner product, we present an explicit description of the RKHS of the extended Gaussian kernel. Furthermore, using the Funk-Hecke formula, we get the eigenvalues and eigenfunctions of the integral operator on the unit sphere.

Parameter tuning is essential to generalization of support vector machine (SVM). Previous methods usually adopt a nested two-layer framework, where the inner layer solves a convex optimization problem, and the outer layer selects the hyper-parameters by minimizing either cross validation or other error bounds. In this paper, we propose a novel parameter tuning approach for SVM via kernel matrix approximation, based on the observation that approximate computation is sufficient for parameter tuning. We first develop a preliminary approximate computation theory of parameter tuning for SVM. We present a kernel matrix approximation algorithm MoCIC. We design an approximate parameter tuning algorithm APT, which applies MoCIC to compute a low-dimension and low-rank approximation of the kernel matrix, and uses this approximate matrix to efficiently solve the quadratic programming of SVM, then selects the optimal candidate parameter through the approximate cross validation error (ACVE). Finally, we verify and compare the feasibility and efficiency of APT on 10 artificial and benchmark datasets. Experimental results show that this new algorithm can dramatically reduce time consumption of parameter tuning and at the same time guarantee the effectiveness of the selected parameters. It comes to the conclusion that the approximate parameter tuning approach is sound, efficient, and promising.

Sketch recognition is one of the essential step of sketch understanding. Challenge in sketch recognition is the variation and imprecision present in sketch. Free drawing styles of sketching make it difficult to build a robust sketch recognition system. This paper proposes a novel recognition approach that can recognize primitive shapes, as well as combinations of these primitives. The approach is independent of stroke order, number, as well as invariant to size and aspect ratio of sketch. Feature string is used to represent primitives. We defined a similarity measure on these feature strings that counts common substrings in two input strings, which is referred to as the string kernel in the field of kernel methods. Support vector machine(SVM) is then trained with labeled examples to handle the task of classification. The experiment on hand drawn digital circuit diagrams shows that our system can recognize sketching efficiently and robustly.

In order to improve the generalization performance of support vector regression (SVR), we propose a novel model combination method for SVR on regularization path. First, we construct the initial candidate model set using the regularization path, whose inherent piecewise linearity makes the construction easy and effective. Then, we elaborately select the models for combination from the initial model set through the improved Occam's Window method and the input-dependent strategy. Finally, we carry out the combination on the selected models using the Bayesian model averaging. Experimental results on benchmark data sets show that our combination method has significant advantage over the model selection methods based on generalized cross validation (GCV) and Bayesian information criterion (BIC). The results also verify that the improved Occam's Window method and the input-dependent strategy can enhance the predictive performance of the combination model.

Model selection is critical to least squares support vector machine (LSSVM). A major problem of existing model selection approaches is that a standard LSSVM needs to be solved with O (n 3) complexity for each iteration, where n is the number of training examples. In this paper, we propose an approximate approach to model selection of LSSVM. We use Nystrom method to approximate a given kernel matrix by a low rank representation of it. With such approximation, we first design an efficient LSSVM algorithm and theoretically analyze the effect of kernel matrix approximation on the decision function of LSSVM. Based on the matrix approximation error bound of Nystrom method, we derive a model approximation error bound, which is a theoretical guarantee of approximate model selection. We finally present an approximate model selection scheme, whose complexity is lower than the previous approaches. Experimental results on benchmark datasets demonstrate the effectiveness of approximate model selection.

Many learning algorithms, such as spectral clustering and manifold learning, need to estimate eigenvalues of graph Laplacian operators defined by a similarity function or a kernel on empirical data. It is important to assess the quality of the eigenvalue estimation. In this paper, we present an accurate approximation error bound for each eigenvalue of empirical graph Laplacian (graph Laplacian matrix) and that of graph Laplacian operator with bounded kernel function. We first propose a basic bound involving with the norms of certain error matrices based on the spectral perturbation theory. Then, we estimate the norms of error matrices with bounded kernel function. This bound, which depends on the eigenvalue under consideration, asymptotically reflects the actual behavior of approximation error for each eigenvalue, and significantly improves existing approximation error bounds.

We propose a new leaning method for Multiple Kernel Learning (MKL) based on the upper bounds of the leave-one-out error that is an almost unbiased estimate of the expected generalization error. Specifically, we first present two new formulations for MKL by minimizing the upper bounds of the leave-one-out error. Then, we compute the derivatives of these bounds and design an efficient iterative algorithm for solving these formulations. Experimental results show that the proposed method gives better accuracy results than that of both SVM with the uniform combination of basis kernels and other state-of-art kernel learning approaches.

Parameter Tuning is an indispensable step to guarantee generalization of support vector machines (SVM). Previous methods can be reduced to a nested two-layer framework, where the inner layer solves a convex optimization problem, and the outer layer selects the hyper-parameters by minimizing either cross validation error or other error bounds. In this paper, we propose a novel efficient parameter tuning approach via kernel matrix approximation, focusing on the efficiency improvement of SVM training in the inner layer. We first develop a kernel matrix approximation algorithm MoCIC. Then, we apply MoCIC to compute a low-rank approximation of the kernel matrix, and then use the approximate matrix to approximately solve the quadratic programming of SVM, and finally select the optimal candidate parameters through the approximate cross validation error (ACVE). We verify the feasibility and the efficiency of parameter tuning approach based on MoCIC on 5 benchmark datasets. Experimental results show that our approach can dramatically reduce time consumption of parameter tuning and meanwhile guarantee the effectiveness of the selected parameters.

Qualitative probabilistic networks (QPNs) are a qualitative abstraction of Bayesian networks, which focus on the monotonic relationship between variables. However, sometimes we don't care about this monotonic relationship, but more concerned about the change of probability of the variable comparing with its prior probability. In this paper, we propose a new qualitative abstraction of Bayesian networks-PQPNs (prior qualitative probabilistic networks) that focuses on the prior probability distribution. We analyze the properties of PQPN, namely symmetry, transitivity and composition. Further, we design a sign propagation algorithm of PQPN, and describe the relationship between QPN and PQPN. Finally, through an experiment, we show that PQPNs have an advantage over QPNs.

Kernel construction is one of the key issues both in current research and application of kernel methods. In this paper, we present an effective kernel construction method, in which we reduce the construction of kernel function to the solutions of generalized eigenvalue problems. Specifically, we first obtain a primal kernel function based on the similarity of instances, and refine it with the conformal transformation. Then we determine the parameters of kernel function by simply solving the generalized eigenvalue problems according to the kernel alignment and Fisher criteria. Our method can avoid local maxima and insure positive semidefinite of the constructed kernel. Experimental results show that our kernel construction method is effective and robust.

Model combination is an important approach to improving the generalization performance of support vector machine (SVM), but usually has low computational efficiency. In this paper, we propose a novel probabilistic model combination method for support vector machine on regularization path (PMCRP). We first design an efficient regularization path algorithm, namely the regularization path of support vector machine based on positive-definite kernel (PDSVMP), which constructs the initial candidate model set. Then, we combine the initial models using Bayesian model averaging. Experimental results on benchmark datasets show that PMCRP has significant advantage over cross-validation and the Generalized Approximate Cross-Validation (GACV), meanwhile guaranteeing high computation efficiency of model combination.

The problem of integrating multiple-source uncertain information is crucial in many applications. In this paper, we propose an integration method of multiple Qualitative Probabilistic Networks (QPNs). Assuming that each QPN has the same nodes, we integrate the qualitative signs and structure of multiple QPNs based on probabilistic rough sets. Specifically, we first take the probabilistic-rough-set-based dependency degree as the strength of qualitative influences to reduce ambiguities that arise from the qualitative signs integration. Secondly, we give the definition of the whole influence strength, and then discuss two cases to delete the cycles in the process of structure integration. Finally, we verify the correctness of the integration method by the simulation experiments.

Parameters tuning is fundamental for support vector regression (SVR). Previous tuning methods mainly adopted a nested two-layer optimization framework, where the inner one solved a standard SVR for fixed hyper-parameters and the outer one adjusted the hyper-parameters, which directly led to high computational complexity. To solve this problem, we propose a kernel matrix approximation algorithm KMA-α based on Monte Carlo and incomplete Cholesky factorization. The KMA-α approximates a given kernel matrix by a low-rank matrix, which will be used to feed SVR to improve its performance and further accelerate the whole parameters tuning process. Finally, on the basis of the computational complexity analysis of the KMA-α, we verify the performance improvement of parameters tuning attributed to the KMA-α on benchmark databases. Theoretical and experimental results show that the KMA-α is a valid and efficient kernel matrix approximation algorithm for parameters tuning of SVR.

The notion of conceptual neighborhood has been used in the areas of qualitative temporal reasoning and qualitative spatial reasoning. In this paper, first, we discuss the adjacent relations between generators in Voronoi diagrams and their changes, and then present a method of representing relative positions with adjacent relations qualitatively. Next, we define the conceptual neighborhood for reasoning about motion based on relative positions, and construct it with a line sweep algorithm. The algorithm gradually moves a horizontal sweep-line, finds to record the adjacent relative positions, and then constructs the conceptual neighborhood. Finally, we give the examples for illustrating the use and the potential of the conceptual neighborhood for representing and reasoning about motion.

Qualitative probabilistic networks(QPNs) have been designed for probabilistic reasoning in a qualitative way. As a consequence of their coarse level of representation detail, qualitative probabilistic networks do not provide for resolving trade-offs and typically yield ambiguous results upon inference, especially in large complicated networks, we propose an algorithm for computing more informative results for unresolved trade-offs. The algorithm derives significant efficiency building upon the idea of decomposing QPNs into subnetworks and reasoning hierarchically in virtue of enhanced representation.

Temporal Qualitative Probabilistic Networks (TQPN) have become a standard tool for modeling various qualitative and temporal causal phenomena. In this paper, we address the issue of TQPN learning from time series data. The structure of TQPN can be constructed by learning Dynamic Bayesian Networks (DBN) based on Markov Chain Monte Carlo (MCMC) method. Specifically, since the causal relationships between variables always follow the time flow, we only consider the causal relationships existing between adjacent time slices. Furthermore, we learn the corresponding relationships of both qualitative influences and qualitative synergies with the conditional probability orderings, and represent the conditional probabilities with the frequency formats. Experiment results illuminate that the method is promising.

Qualitative path is a basic concept in qualitative motion reasoning. In this paper, we propose a qualitative path representation method based on Voronoi diagram. This method uses the adjacent relationship to represent the qualitative position, and then uses a sequence of qualitative positions to represent the qualitative path. Furthermore, we also design and implement an algorithm for qualitative path. With the initial Voronoi diagram and the change in the number of edges of all Voronoi regions during the course of motion, the algorithm can determine the changes in neighbors of Voronoi regions, identify the moving points, and work out their qualitative path. Experiment results show that the method is promising.

Group Lasso is an efficient regularized leastsquare regression algorithm, and is now being used as a computationally feasible method to select grouped variables. In this paper, we address the issue of estimation consistency of the group Lasso with special diagonal matrix. We derive sufficient condition for the consistency of group Lasso under practical assumptions, such as model misspecification. This sufficient condition, which depends mainly on the covariance of the predictor variables, states that group Lasso selects the true model consistently if the predictors that are in and not in the true model have low correlation. Specifically, the consistency condition adopts the regularization with special kernel matrix. Experiments are carried out to provide insights and understanding of this result.

The adapted sign-propagation algorithm presented recently by Kouwen for inference with a qualitative probabilistic network has been designed to handle a single observation at a time. Renooij has proposed an adapted algorithm for propagating multiple observations by entering them sequentially and combining the results of the successive propagations, but it still generates unnecessary weakness in multiply connected network. We demonstrate that both approaches are complementary, and propose a new integrated qualitative probabilistic inference algorithm that will provide for stronger results upon inference with multiple observations.

Qualitative motion reasoning is an important approach to spatial commonsense reasoning. In this paper, we propose a qualitative motion reasoning method based on Voronoi diagrams. The method adopts the vicinity relationship to represent qualitative position and qualitative path. Specifically, the qualitative position is represented by the edges of the Voronoi diagram region the moving point falls in, and the qualitative path is represented by the series of qualitative positions the moving point passes through. Furthermore, a qualitative motion reasoning algorithm is designed and implemented. With the initial Voronoi diagram and the numbers of edges of all Voronoi regions at different moments, the algorithm can update the dynamic Voronoi diagram, work up the qualitative path, and identify the moving point. Experiment results illuminate that the method is promising.

Group Lasso is a recently proposed regression method that can be used to select group variables. When studying the consistency condition of the regularization path of group Lasso, we assume that the groupings of the univariate variables are known and fixed, that is, the group structure is given. In this paper, we address the issue of the influence of group structure on the group Lasso consistency. Based on the analysis of the consistency condition, we argue that the sparsity patterns is the determinant, the different group structures can lead to different consistencies, and the degree of the correlation between the relevant groups and the irrelevant groups is the key factor. Experimental results also demonstrate that the group Lasso is consistent under low correlation conditions.

Semantics representation of 3D-sketch is fundamental to 3D-sketch understanding. Line labeling was a convenient approach to spatial semantics representation for 3D-sketches. However, all the existing label sets could not be used to label freehand 3D-sketches directly as these label sets were derived from perfect projections of 3D objects. These label sets had not been proved to be complete yet. In this paper, we propose a label set, named the 3DS label set, for 3D-sketches of the blocks world objects, which can be used to label the 3D-sketches directly without tidying. We firmly prove that the 3DS label set is complete for the 3D-sketches spatial semantics.

Constructing an optimal combinatorial kernel matrix is crucial in kernel methods. We propose a criterion for this model selection problem in the feature space. Differing from the previously popular kernel target alignments criterion, which is subject to limiting the combinatorial matrix that projects the inputs into two additive inverse features, the proposed criterion overcomes the limitation and measures the goodness of a combinatorial kernel matrix based on the feature distances. We first introduce the kernel target alignment and discuss its limitation for combinatorial kernel matrix. Then we present the feature-distances based combinatorial kernel matrix evaluating criterion formally. Finally, we analyze the properties of the proposed criterion and examine its performance on simulated data base. Both theoretical analysis and experimental results demonstrate that the proposed combinatorial kernel matrix evaluating criterion is sound and effective, and lays the foundation for further research of combinatorial kernel methods.

In this paper, we present a generic diffusion kernel for graph-based semi-supervised learning, whose kernel matrix is generated with a Taylor expansion on the generating function of diffusion similarity matrix. The generic diffusion kernel subsumes common known diffusion kernels, and provides a kernel framework for semi-supervised learning. Specifically, we first present the definition of diffusion similarity matrix, and lay the theoretical foundation for our approach. Then we derive the 2- and d-diffusion kernels, and naturally extend them to the generic diffusion kernel. Further we prove that small eigenvalues of the generic diffusion kernel correspond to smooth eigenvectors over the graph. This property is critical for the construction of generic diffusion kernels. Experiments on simulated and benchmark databases demonstrate that the generic diffusion kernel is sound and effective.

Gaussian mean field is an important paradigm of cluster-based variational inference, and its cluster selection is critical to the tradeoff between the variational accuracy and the computational complexity of cluster-based variational inference. In this paper, we explore a coupling based cluster selection method for Gaussian mean fields. First, we propose the model coupling and the quasi-coupling concepts on Gaussian Markov random field, and prove the coupling-accuracy theorem for Gaussian mean fields, which regards the quasi-coupling as a cluster selection criterion. Then we design a normalized cluster selection algorithm based on the criterion for Gaussian mean fields. Finally, we design numerical experiments to demonstrate the validity and efficiency of the cluster selection method and algorithm.

Construction of kernel functions is crucial for research and application of support vector machines (SVM). In this paper, we propose a combinatorial construction of hyperkernel functions for SVM. We first analyze the under and over-learning phenomena of common kernel functions. Then, we construct hyperkernel function with a polynomial combination of common kernels, and prove the Mercer condition of the hyperkernel. Finally, we experiment both on simulation and benchmark data to demonstrate the performance of hyperkernel for SVM. The theoretical proofs and experimental results illuminate the validity and feasibility of hyperkernel.

Automatic tuning of hyperparameter and parameter is an essential ingredient and important process for learning and applying Support Vector Machines (SVM). Previous tuning methods choose hyperparameter and parameter separately in different iteration processes, and usually search exhaustively in parameter spaces. In this paper we propose and implement a new tuning algorithm that chooses hyperparameter and parameter for SVM simultaneously and search the parameter space efficiently with a deliberate initialization of a pair of starting points. First we derive an approximate but effective radius margin bound for soft margin SVM. Then we combine multiparameters of SVM into one vector, converting the two separate tuning processes into one optimization problem. Further we discuss the implementation issue about the new tuning algorithm, and that of choosing initial points for iteration. Finally we compare the new tuning algorithm with old gradient based method and cross validation on five benchmark data sets. The experimental results demonstrate that the new tuning algorithm is effective, and usually outperforms those classical tuning algorithms.

Sketch recognition provides the basis for semantic processing in Sketching Understanding, and it consists of two sequential and cyclic phases: primitive shape recognition and composite shape recognition. In this paper, a composite shape recognition algorithm based on Support Vector Machines (SVM) and Decision Tree is proposed. Directed Acyclic Graphs SVM (DAGSVM) is used for primitive shape recognition and composite shape recognition. The decision tree is introduced to pre-classify the composite shape and to reduce the computational cost of recognition. The algorithm integrates the advantages of feature-based and similarity-based recognition approaches, and can deal with sketching sequence properly. Experiment demonstrates that the model is feasible.

Sketch recognition is an essential process for sketch understanding. The free drawing style of sketching makes it difficult to build a robust sketch recognition system that can support the imprecision and high variability present in sketch. This paper addresses these problems inherent in sketch recognition in the framework of Bayesian network which can readily represent uncertainty in the recognition process and make inference based on partial evidence. To further improve recognition accuracy, context information is incorporated in the recognition process rather than identifying sketches in isolation. The new framework proposed in this paper offers user more sketching freedom by automatically grouping strokes and recognizing editing gestures as well as over-traced strokes.

In this paper, a qualitative shape model for 2D semi-fractals is presented. First, based on iterated functions system (IFS) theory and formal language theory, a shape representation formalism called regular generation system (RGS) is proposed to qualitatively represent 2D semi-fractal shape. Then, based on an inductive automata learning algorithm, a modeling procedure for natural semi-fractals is described. Finally, examples are presented to demonstrate the representation mechanism and the modeling method of RGS. Since RGS combines and extends Prusinkiewicz's (1992) and Gujar's (1993) works on representing fractals and provides a modeling procedure, RGS is a complete and effective shape model for 2D semi-fractals.