MLBio+Laboratory Machine Learning in Biomedical Informatics



Bioinformatics & Data Mining

PrePrint: Automatic Generation of the Domain Module from Electronic Textbooks. Method &#x0026 Validation

TKDE - Mon, 04/01/2013 - 17:25
Technology Supported Learning Systems have proved to be helpful in many learning situations. These systems require an appropriate representation of the knowledge to be learnt, the Domain Module. The authoring of the Domain Module is cost and labour intensive, but its development cost might be lightened by profiting from semi-automatic Domain Module authoring techniques and promoting knowledge reuse. DOM-Sortze is a system that uses Natural Language Processing techniques, heuristic reasoning, and ontologies for the semi-automatic construction of the Domain Module from electronic textbooks. In order to determine how it might help in the Domain Module authoring process, it has been tested with an electronic textbook, and the gathered knowledge has been compared against the Domain Module that instructional designers developed manually. This paper presents DOM-Sortze and describes the experiment carried out.

PrePrint: Multidimensional Sequence Classification based on Fuzzy Distances and Discriminant Analysis

TKDE - Mon, 04/01/2013 - 17:25
In this paper, we present a novel method aiming at multidimensional sequence classification. We propose a novel sequence representation, based on its fuzzy distances from optimal representative signal instances, called statemes. We also propose a novel modified Clustering Discriminant Analysis algorithm minimizing the adopted criterion with respect to both the data projection matrix and the class representation, leading to the optimal discriminant sequence class representation in a low-dimensional space, respectively. Based on this representation, simple classification algorithms, such as the nearest subclass centroid, provide high classification accuracy. A three step iterative optimization procedure for choosing statemes, optimal discriminant sub-space and optimal sequence class representation in the final decision space is proposed. The classification procedure is fast and accurate. The proposed method has been tested on a wide variety of multidimensional sequence classification problems, including handwritten character recognition, time series classification and human activity recognition, providing very satisfactory classification results.

PrePrint: Facilitating Document Annotation using Content and Querying Value

TKDE - Mon, 04/01/2013 - 17:25
A large number of organizations today generate and share textual descriptions of their products, services, and actions. Such collections of textual data contain significant amount of structured information, which remains buried in the unstructured text. While information extraction algorithms facilitate the extraction of structured relations, they are often expensive and inaccurate. We present a novel alternative approach that facilitates the generation of the structured metadata by identifying documents that are likely to contain information of interest and this information is going to be subsequently useful for querying the database. Our approach relies on the idea that humans are more likely to add the necessary metadata during creation time, if prompted by the interface; or that it is much easier for humans to identify the metadata when such information actually exists in the document, instead of naively prompting users to fill in forms with information that is not available in the document. We present algorithms that identify structured attributes that are likely to appear within the document, by jointly utilizing the content of the text and the query workload. Our experimental evaluation shows that our approach generates superior results compared to approaches that rely only on content or only on the query workload.

PrePrint: Practical Ensemble Classification Error Bounds for Different Operating Points

TKDE - Mon, 04/01/2013 - 17:25
Classification algorithms used to support the decisions of human analysts are often used in settings in which zero-one loss is not the appropriate indication of performance. The zero-one loss corresponds to the operating point with equal costs for false alarms and missed detections, and no option for the classifier to leave uncertain test samples unlabeled. A generalization bound for ensemble classification at the standard operating point has been developed based on two interpretable properties of the ensemble: strength and correlation, using the Chebyshev inequality. Such generalization bounds for other operating points have not been developed previously, and are developed in this paper. Significantly, the bounds are empirically shown to have much practical utility in determining optimal parameters for classification with a reject option, classification for ultra-low probability of false alarm, and classification for ultra-low probability of missed detection. Counter to the usual guideline of large strength and small correlation in the ensemble, different guidelines are recommended by the derived bounds in the ultra-low false alarm and missed detection probability regimes.

PrePrint: Crowdsourced Trace Similarity with Smartphones

TKDE - Mon, 04/01/2013 - 17:25
Smartphones are nowadays equipped with a number of sensors, such as WiFi, GPS, accelerometers, etc. This capability allows smartphone users to easily engage in crowdsourced computing services, which contribute to the solution of complex problems in a distributed manner. In this work, we leverage such a computing paradigm to solve efficiently the following problem: comparing a query trace Q against a crowd of traces generated and stored on distributed smartphones. Our proposed framework, coined SmartTrace+, provides an effective solution without disclosing any part of the crowd traces to the query processor. SmartTrace+, relies on an in-situ data storage model and intelligent top-K query processing algorithms that exploit distributed trajectory similarity measures, resilient to spatial and temporal noise, in order to derive the most relevant answers to Q. We evaluate our algorithms on both synthetic and real workloads. We describe our prototype system developed on the Android OS. The solution is deployed over our own SmartLab testbed of 25 smartphones. Our study reveals that computations over SmartTrace+ result in substantial energy conservation; in addition, results can be computed faster than competitive approaches.

PrePrint: Improving Word Similarity by Augmenting PMI with Estimates of Word Polysemy

TKDE - Mon, 04/01/2013 - 17:25
Pointwise mutual information (PMI) is a widely used word similarity measure, but it lacks a clear explanation of how it works. We explore how PMI differs from distributional similarity, and we introduce a novel metric, PMI_max, that augments PMI with information about a word's number of senses. The coefficients of PMI_max are determined empirically by maximizing a utility function based on the performance of automatic thesaurus generation. We show that it outperforms traditional PMI in the application of automatic thesaurus generation and in two word similarity benchmark tasks: human similarity ratings and TOEFL synonym questions. PMI_max achieves a correlation coefficient comparable to the best knowledge-based approaches on the Miller-Charles similarity rating dataset.

PrePrint: Symmetric Fast Marching Schemes for Better Numerical Isotropy

TPAMI - Sun, 03/31/2013 - 18:59
Existing Fast Marching methods solve the Eikonal equation using a continuous (first order) model to estimate the accumulated cost, but a discontinuous (zero order) model for the traveling cost at each grid point. As a result the estimate of the accumulated cost (calculated numerically) at a given point will vary based on the direction of the arriving front, introducing an anisotropy into the discrete algorithm even though the continuous PDE is itself isotropic. To remove this anisotropy, we propose two very different schemes. In the first model we utilize a continuous interpolation of the traveling cost, which is not biased by the direction of the propagating front. In the second model we upsample the traveling cost on a higher resolution grid to overcome the directional bias. We show the significance of removing the directional bias in the computation of the cost in some applications of fast marching method, demonstrating that both methods make the discrete implementation more isotropic in accordance with the underlying continuous PDE. We also compare the accuracy and computation time of our proposed methods with the existing state of the art fast marching techniques to demonstrate the superiority of our method.

PrePrint: Multi-View Face Detection and Registration Requiring Minimal Manual Intervention

TPAMI - Sun, 03/31/2013 - 18:59
Most face recognition systems require faces to be detected and localized a priori. In this paper, an approach to simultaneously detect and localize multiple faces having arbitrary views and different scales is proposed. The main contribution of this paper is the introduction of a face constellation, which enables multi-view face detection and localization. In contrast to other multi-view approaches that require many manually labeled images for training, the proposed face constellation requires only a single reference image of a face containing two manually indicated reference points for initialization. Subsequent training face images from arbitrary views are automatically added to the constellation (registered to the reference image) based on finding the correspondences between distinctive local features. Thus, the key advantage of the proposed scheme is the minimal manual intervention required to train the face constellation. We also propose an approach to identify distinctive correspondence points between pairs of face images in the presence of a large amount of false matches. To detect and localize multiple faces with arbitrary views, we then propose a probabilistic classifier based formulation to evaluate whether a local feature cluster corresponds to a face.

PrePrint: Stereo Seam Carving A Geometrically Consistent Approach

TPAMI - Sun, 03/31/2013 - 18:59
Image retargeting algorithms attempt to adapt the image content to the screen without distorting the important objects in the scene. Existing methods address retargeting of a single image. In this paper we propose a novel method for retargeting a pair of stereo images. Naively retargeting each image independently will distort the geometric structure and hence will impair the perception of the 3D structure of the scene. We show how to extend a single image seam carving to work on a pair of images. Our method minimizes the visual distortion in each of the images as well as the depth distortion. A key property of the proposed method is that it takes into account the visibility relations between pixels in the image pair (occluded and occluding pixels). As a result, our method guarantees, as we formally prove, that the retargeted pair is geometrically consistent with a feasible 3D scene, similar to the original one. Hence, the retargeted stereo pair can be viewed on a stereoscopic display or further processed by any computer vision algorithm. We demonstrate our method on a number of challenging indoor and outdoor stereo images.

PrePrint: Multi-Exemplar Affinity Propagation

TPAMI - Sun, 03/31/2013 - 18:59
Affinity Propagation (AP) clustering algorithm has received much attention in the past few years. AP is appealing because it is efficient, insensitive to initialization, and it produces clusters at a lower error rate than other exemplar-based methods. However, its single-exemplar model becomes inadequate when applied to model multi-subclasses in some situations such as scene analysis and character recognition. To remedy this deficiency, we have extended the single-exemplar model to a multi-exemplar one to create a new Multi-Exemplar Affinity Propagation (MEAP) algorithm. This new model determines automatically the number of exemplars in each cluster associated with a super exemplar to approximate the subclasses in the category. Solving the model is NP-hard and we tackle it with the max-sum belief propagation to produce neighborhood maximum clusters, with no need to specify beforehand the number of clusters, multi-exemplars, and super-exemplars. Also, utilizing the sparsity in the data, we are able to reduce substantially the computational time and storage. Experimental studies have shown MEAP's significant improvements over other algorithms on unsupervised image categorization and the clustering of handwritten digits.

PrePrint: Learning AND-OR Templates for Object Recognition and Detection

TPAMI - Sun, 03/31/2013 - 18:59
This paper presents a framework for unsupervised learning of a hierarchical reconfigurable image template - the AND-OR Template (AOT) for visual objects. The AOT includes: (1) hierarchical composition as ''AND'' nodes, (2) deformation and articulation of parts as geometric "OR" nodes, and (3) multiple ways of composition as structural "OR" nodes. The terminal nodes are hybrid image templates (HIT) \cite{hit} that are fully generative to the pixels. We show that both the structures and parameters of the AOT model can be learned in an unsupervised way from images using an information projection principle. The learning algorithm consists of two steps: i) a recursive block pursuit procedure to learn the hierarchical dictionary of primitives, parts and objects, and ii) a graph compression procedure to minimize model structure for better generalizability. We investigate the factors that influence how well the learning algorithm can identify the underlying AOT. And we propose a number of ways to evaluate the performance of the learned AOTs through both synthesized examples and real world images. Our model advances the state-of-the-art for object detection by improving the accuracy of template matching.

PrePrint: Modeling Natural Images Using Gated MRFs

TPAMI - Sun, 03/31/2013 - 18:59
This paper describes a Markov Random Field for real-valued image modeling that has two sets of latent variables. One set is used to gate the interactions between all pairs of pixels while the second set determines the mean intensities of each pixel. This is a powerful model with a conditional distribution over the input that is Gaussian with both mean and covariance determined by the configuration of latent variables, which is unlike previous models that were restricted to use Gaussians with either a fixed mean or a diagonal covariance matrix. Thanks to the increased flexibility, this gated MRF can generate more realistic samples after training on an unconstrained distribution of high-resolution natural images. Furthermore, the latent variables of the model can be inferred efficiently and can be used as very effective descriptors in recognition tasks. Both generation and discrimination drastically improve as layers of binary latent variables are added to the model, yielding a hierarchical model called a Deep Belief Network.

PrePrint: Efficient Methods for Overlapping Group Lasso

TPAMI - Sun, 03/31/2013 - 18:59
The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. Our methods and theoretical results are then generalized to tackle the general overlapping group Lasso formulation based on the Lq norm. We further extend our algorithm to solve a non-convex overlapping group Lasso formulation based on the capped norm regularization, which reduces the estimation bias introduced by the convex penalty. Our empirical evaluations using both synthetic and real data demonstrate the efficiency of the proposed algorithm. Results also demonstrate the effectiveness of the non-convex formulation for overlapping group Lasso.

PrePrint: Range Image Registration using a Photometric Metric Under unknown Lighting

TPAMI - Sun, 03/31/2013 - 18:59
Based on the spherical harmonics representation of image formation, we derive a new photometric metric for evaluating the correctness of a given rigid transformation aligning two overlapping range images captured under unknown, distant and general illumination. We estimate the surrounding illumination and albedo values of points of the two range images from the point correspondences induced by the input transformation. We then synthesize the color of both range images using albedo values transferred using the point correspondences to compute the photometric re-projection error. This way allows us to accurately register two range images by finding the transformation that minimizes the photometric re-projection error. We also propose a practical method using the proposed photometric metric to register pairs of range images devoid of salient geometric features, captured under unknown lighting. Our method uses a hypothesize-and-test strategy to search for the transformation that minimizes our photometric metric. Transformation candidates are efficiently generated by employing the spherical representation of each range image. Experimental results using both synthetic and real data demonstrate the usefulness of the proposed metric.

PrePrint: Joint Histogram Based Cost Aggregation for Stereo Matching

TPAMI - Sun, 03/31/2013 - 18:59
This paper presents a novel method for performing efficient cost aggregation in stereo matching. The cost aggregation problem is re-formulated from a perspective of a histogram, giving us a potential to reduce the complexity of the cost aggregation in stereo matching significantly. Different from previous methods which have tried to reduce the complexity in terms of the size of an image and a matching window, our approach focuses on reducing the computational redundancy which exists among the search range, caused by a repeated filtering for all the hypotheses. Moreover, we also reduce the complexity of the window-based filtering through an efficient sampling scheme inside the matching window. The trade-off between accuracy and complexity is extensively investigated by varying the parameters used in the proposed method. Experimental results show that the proposed method provides high-quality disparity maps with a low complexity and outperforms existing local methods. This work also provides new insights into complexity-constrained stereo matching algorithm design.

PrePrint: Higher-Order Partial Least Squares (HOPLS): A Generalized Multi-Linear Regression Method

TPAMI - Sun, 03/31/2013 - 18:59
A new generalized multilinear regression model, termed the Higher-Order Partial Least Squares (HOPLS), is introduced with the aim to predict a tensor (multiway array) <b><u>Y</u></b> from a tensor <b><u>X</u></b> through projecting the data onto the latent space and performing regression on the corresponding latent variables. HOPLS differs substantially from other regression models in that it explains the data by a sum of orthogonal Tucker tensors, while the number of orthogonal loadings serves as a parameter to control model complexity and prevent overfitting. The low dimensional latent space is optimized sequentially via a deflation operation, yielding the best joint subspace approximation for both <b><u>X</u></b> and <b><u>Y</u></b>. Instead of decomposing <b><u>X</u></b> and <b><u>Y</u></b> individually, higher order singular value decomposition on a newly defined generalized cross-covariance tensor is employed to optimize the orthogonal loadings. A systematic comparison on both synthetic data and real-world decoding of 3D movement trajectories from electrocorticogram (ECoG) signals demonstrate the advantages of HOPLS over the existing methods in terms of better predictive ability, suitability to handle small sample sizes, and robustness to noise.

PrePrint: A Branch and Bound Approach to Correspondence and Grouping Problems

TPAMI - Sun, 03/31/2013 - 18:59
Data correspondence/grouping is a fundamental topic in computer vision. Finding feature correspondences is probably the most popular application of this topic and constitutes our main motivation. It is a key ingredient for various tasks including 3D reconstruction and object recognition. Existing feature correspondence methods are based on either local appearance similarity, or global geometric consistency, or a combination of both in some heuristic manner. None of these methods is fully satisfactory, especially with repetitive image textures or mis-matches. In this paper, we present a new algorithm that combines the benefits of both appearance-based and geometry-based methods, and mathematically guarantees a global optimization. Our algorithm accepts the two sets of features as input, and outputs the largest set of feature correspondences verifying both the appearance and geometric constraints. We formulate the problem as a mixed integer program, and solve it efficiently by a series of linear programs via branch-and-bound. We subsequently generalize our framework in the context of data correspondence/grouping under an unknown parametric model and show it can be applied to certain classes of computer vision problems. Our algorithm has been validated successfully on synthesized data and challenging real images.

PrePrint: Hierarchical Object Parsing from Structured Noisy Point Clouds

TPAMI - Sun, 03/31/2013 - 18:59
Object parsing and segmentation from point clouds are challenging tasks because the relevant data is available only as thin structures along object boundaries or other features, and is corrupted by large amounts of noise. To handle this kind of data, flexible shape models are desired that can accurately follow the object boundaries. Popular models such as Active Shape and Active Appearance models lack the necessary flexibility for this task, while recent approaches such as the Recursive Compositional Models make model simplifications in order to obtain computational guarantees. This paper investigates a hierarchical Bayesian model of shape and appearance in a generative setting. The input data is explained by an object parsing layer, which is a deformation of a hidden PCA shape model with Gaussian prior. The paper also introduces a novel efficient inference algorithm that uses informed data-driven proposals to initialize local searches for the hidden variables. Applied to the problem of object parsing from structured point clouds such as edge detection images, the proposed approach obtains state of the art parsing errors on two standard datasets without using any intensity information.

PrePrint: Calibration of Smooth Camera Models

TPAMI - Sun, 03/31/2013 - 18:59
Generic imaging models can be used to represent any camera. Current generic models are discrete and define a mapping between each pixel in the image and a straight line in 3D space. This paper presents a modification of the generic camera model that allows the simplification of the calibration procedure. The only requirement is that the coordinates of the 3D projecting lines are related by functions that vary smoothly across space. Such model is obtained by modifying the general imaging model using radial basis functions to interpolate image coordinates and 3D lines, thereby allowing both an increase in resolution (due to their continuous nature) and a more compact representation. Using this variation of the general imaging model we also develop a calibration procedure. This procedure only requires that a 3D point be matched to each pixel. In addition not all the pixels need to be calibrated. As a result the complexity of the procedure is significantly decreased. Normalization is applied to the coordinates of both image and 3D points which increases the accuracy of the calibration. Results with both synthetic and real data sets show that the model and calibration procedure are easily applicable and provide accurate calibration results.

PrePrint: Clustering Dynamic Textures with the Hierarchical EM Algorithm for Modeling Video

TPAMI - Sun, 03/31/2013 - 18:59
The dynamic texture (DT) is a probabilistic generative model, defined over space and time, that represents a video as the output of a linear dynamical system (LDS). The DT model has been applied to a wide variety of computer vision problems, such as motion segmentation, motion classification, and video registration. In this paper, we derive a new algorithm for clustering DT models that is based on the hierarchical EM algorithm. The proposed clustering algorithm is capable of both clustering DTs and learning novel DT cluster centers that are representative of the cluster members, in a manner that is consistent with the underlying generative probabilistic model of the DT. We also derive an efficient recursive algorithm for sensitivity analysis of the discrete-time Kalman smoothing filter, which is used as the basis for computing expectations in the E-step of the HEM algorithm. Finally, we demonstrate the efficacy of the clustering algorithm on several applications in motion analysis, including hierarchical motion clustering, semantic motion annotation, and learning bag-of-systems codebooks for dynamic texture recognition.


Powered by Drupal, an open source content management system