results for au:Shen_L in:cs

- Nov 17 2017 cs.CV arXiv:1711.05775v1We develop an end-to-end training algorithm for whole-image breast cancer diagnosis based on mammograms. It requires lesion annotations only at the first stage of training. After that, a whole image classifier can be trained using only image level labels. This greatly reduced the reliance on lesion annotations. Our approach is implemented using an all convolutional design that is simple yet provides superior performance in comparison with the previous methods. On DDSM, our best single-model achieves a per-image AUC score of 0.88 and three-model averaging increases the score to 0.91. On INbreast, our best single-model achieves a per-image AUC score of 0.96. Using DDSM as benchmark, our models compare favorably with the current state-of-the-art. We also demonstrate that a whole image model trained on DDSM can be easily transferred to INbreast without using its lesion annotations and using only a small amount of training data. Code availability: https://github.com/lishen/end2end-all-conv
- As an efficient recurrent neural network (RNN) model, reservoir computing (RC) models, such as Echo State Networks, have attracted widespread attention in the last decade. However, while they have had great success with time series data [1], [2], many time series have a multiscale structure, which a single-hidden-layer RC model may have difficulty capturing. In this paper, we propose a novel hierarchical reservoir computing framework we call Deep Echo State Networks (Deep-ESNs). The most distinctive feature of a Deep-ESN is its ability to deal with time series through hierarchical projections. Specifically, when an input time series is projected into the high-dimensional echo-state space of a reservoir, a subsequent encoding layer (e.g., a PCA, autoencoder, or a random projection) can project the echo-state representations into a lower-dimensional space. These low-dimensional representations can then be processed by another ESN. By using projection layers and encoding layers alternately in the hierarchical framework, a Deep-ESN can not only attenuate the effects of the collinearity problem in ESNs, but also fully take advantage of the temporal kernel property of ESNs to explore multiscale dynamics of time series. To fuse the multiscale representations obtained by each reservoir, we add connections from each encoding layer to the last output layer. Theoretical analyses prove that stability of a Deep-ESN is guaranteed by the echo state property (ESP), and the time complexity is equivalent to a conventional ESN. Experimental results on some artificial and real world time series demonstrate that Deep-ESNs can capture multiscale dynamics, and outperform both standard ESNs and previous hierarchical ESN-based models.
- Nov 08 2017 cs.CV arXiv:1711.02488v1Images captured in low-light conditions usually suffer from very low contrast, which increases the difficulty of subsequent computer vision tasks in a great extent. In this paper, a low-light image enhancement model based on convolutional neural network and Retinex theory is proposed. Firstly, we show that multi-scale Retinex is equivalent to a feedforward convolutional neural network with different Gaussian convolution kernels. Motivated by this fact, we consider a Convolutional Neural Network(MSR-net) that directly learns an end-to-end mapping between dark and bright images. Different fundamentally from existing approaches, low-light image enhancement in this paper is regarded as a machine learning problem. In this model, most of the parameters are optimized by back-propagation, while the parameters of traditional models depend on the artificial setting. Experiments on a number of challenging images reveal the advantages of our method in comparison with other state-of-the-art methods from the qualitative and quantitative perspective.
- Oct 24 2017 cs.CV arXiv:1710.08092v1In this paper, we introduce a new large-scale face dataset named VGGFace2. The dataset contains 3.31 million images of 9131 subjects, with an average of 362.6 images for each subject. Images are downloaded from Google Image Search and have large variations in pose, age, illumination, ethnicity and profession (e.g. actors, athletes, politicians). The dataset was collected with three goals in mind: (i) to have both a large number of identities and also a large number of images for each identity; (ii) to cover a large range of pose, age and ethnicity; and (iii) to minimize the label noise. We describe how the dataset was collected, in particular the automated and manual filtering stages to ensure a high accuracy for the images of each identity. To assess face recognition performance using the new dataset, we train ResNet-50 (with and without Squeeze-and-Excitation blocks) Convolutional Neural Networks on VGGFace2, on MS- Celeb-1M, and on their union, and show that training on VGGFace2 leads to improved recognition performance over pose and age. Finally, using the models trained on these datasets, we demonstrate state-of-the-art performance on the IJB-A and IJB-B face recognition benchmarks, exceeding the previous state-of-the-art by a large margin. Datasets and models are publicly available.
- Sep 06 2017 cs.CV arXiv:1709.01507v1Convolutional neural networks are built upon the convolution operation, which extracts informative features by fusing spatial and channel-wise information together within local receptive fields. In order to boost the representational power of a network, much existing work has shown the benefits of enhancing spatial encoding. In this work, we focus on channels and propose a novel architectural unit, which we term the "Squeeze-and-Excitation" (SE) block, that adaptively recalibrates channel-wise feature responses by explicitly modelling interdependencies between channels. We demonstrate that by stacking these blocks together, we can construct SENet architectures that generalise extremely well across challenging datasets. Crucially, we find that SE blocks produce significant performance improvements for existing state-of-the-art deep architectures at slight computational cost. SENets formed the foundation of our ILSVRC 2017 classification submission which won first place and significantly reduced the top-5 error to 2.251%, achieving a 25% relative improvement over the winning entry of 2016.
- We develop an end-to-end training algorithm for whole-image breast cancer diagnosis based on mammograms. It requires lesion annotations only at the first stage of training. After that, a whole image classifier can be trained using only image level labels. This greatly reduced the reliance on lesion annotations. Our approach is implemented using an all convolutional design that is simple yet provides superior performance in comparison with the previous methods. On DDSM, our best single-model achieves a per-image AUC score of 0.88 and three-model averaging increases the score to 0.91. On INbreast, our best single-model achieves a per-image AUC score of 0.96. Using DDSM as benchmark, our models compare favorably with the current state-of-the-art. We also demonstrate that a whole image model trained on DDSM can be easily transferred to INbreast without using its lesion annotations and using only a small amount of training data. Code and model availability: https://github.com/lishen/end2end-all-conv
- Aug 07 2017 cs.DC arXiv:1708.01365v1The goal of load balancing (grid partitioning) is to minimize overall computations and communications, and to make sure that all processors have a similar workload. Geometric methods divide a grid by using a location of a cell while topological methods work with connectivity of cells, which is generally described as a graph. This paper introduces a Hilbert space-filling curve method. A space-filling curve is a continuous curve and defines a map between a one-dimensional space and a multi-dimensional space. A Hilbert space-filling curve is one special space-filling curve discovered by Hilbert and has many useful characteristics, such as good locality, which means that two objects that are close to each other in a multi-dimensional space are also close to each other in a one dimensional space. This property can model communications in grid-based parallel applications. The idea of the Hilbert space-filling curve method is to map a computational domain into a one-dimensional space, partition the one-dimensional space to certain intervals, and assign all cells in a same interval to a MPI. To implement a load balancing method, a mapping kernel is required to convert high-dimensional coordinates to a scalar value and an efficient one-dimensional partitioning module that divides a one-dimensional space and makes sure that all intervals have a similar workload. The Hilbert space-filling curve method is compared with ParMETIS, a famous graph partitioning package. The results show that our Hilbert space-filling curve method has good partition quality. It has been applied to grids with billions of cells, and linear scalability has been obtained on IBM Blue Gene/Q.
- Jul 28 2017 cs.LO arXiv:1707.08849v1In fairly elementary terms this paper presents how the theory of preordered fuzzy sets, more precisely quantale-valued preorders on quantale-valued fuzzy sets, is established under the guidance of enriched category theory. Motivated by several key results from the theory of quantaloid-enriched categories, this paper develops all needed ingredients purely in order-theoretic languages for the readership of fuzzy set theorists, with particular attention paid to fuzzy Galois connections between preordered fuzzy sets.
- Jun 12 2017 cs.CV arXiv:1706.02884v1Understanding the simultaneously very diverse and intricately fine-grained set of possible human actions is a critical open problem in computer vision. Manually labeling training videos is feasible for some action classes but doesn't scale to the full long-tailed distribution of actions. A promising way to address this is to leverage noisy data from web queries to learn new actions, using semi-supervised or "webly-supervised" approaches. However, these methods typically do not learn domain-specific knowledge, or rely on iterative hand-tuned data labeling policies. In this work, we instead propose a reinforcement learning-based formulation for selecting the right examples for training a classifier from noisy web search results. Our method uses Q-learning to learn a data labeling policy on a small labeled training dataset, and then uses this to automatically label noisy web data for new visual concepts. Experiments on the challenging Sports-1M action recognition benchmark as well as on additional fine-grained and newly emerging action classes demonstrate that our method is able to learn good labeling policies for noisy data and use this to learn accurate visual concept classifiers.
- May 10 2017 cs.CV arXiv:1705.03159v1In this paper, we present a novel approach for contour detection with Convolutional Neural Networks. A multi-scale CNN learning framework is designed to automatically learn the most relevant features for contour patch detection. Our method uses patch-level measurements to create contour maps with overlapping patches. We show the proposed CNN is able to to detect large-scale contours in an image efficienly. We further propose a guided filtering method to refine the contour maps produced from large-scale contours. Experimental results on the major contour benchmark databases demonstrate the effectiveness of the proposed technique. We show our method can achieve good detection of both fine-scale and large-scale contours.
- Mar 06 2017 cs.CV arXiv:1703.01053v1We proposed a two stage framework with only one network to analyze skin lesion images, we firstly trained a convolutional network to classify these images, and cropped the import regions which the network has the maximum activation value. In the second stage, we retrained this CNN with the image regions extracted from stage one and output the final probabilities. The two stage framework achieved a mean AUC of 0.857 in ISIC-2017 skin lesion validation set and is 0.04 higher than that of the original inputs, 0.821.
- Mar 03 2017 cs.CV arXiv:1703.00577v1Skin lesion is a severe disease in world-wide extent. Reliable automatic detection of skin tumors is very useful to help increase the accuracy and efficiency of pathologists. International Skin Imaging Collaboration (ISIC) is a challenge focusing on the automatic analysis of skin lesion. In this brief paper, we introduce two deep learning methods to address all the three tasks announced in ISIC 2017, i.e. lesion segmentation (task 1), lesion dermoscopic feature extraction (task 2) and lesion classification (task 3). A fully-convolutional network is proposed to simultaneously address the tasks of lesion segmentation and classification and a straight-forward CNN is proposed for the dermoscopic feature extraction task. Experimental results on the validation set show promising accuracies, i.e. 75.1% for task 1, 84.4% for task 2 and 90.8% for task 3 were achieved.
- Jan 24 2017 cs.CE arXiv:1701.06254v1This paper presents our work on developing parallel computational methods for two-phase flow on modern parallel computers, where techniques for linear solvers and nonlinear methods are studied and the standard and inexact Newton methods are investigated. A multi-stage preconditioner for two-phase flow is applied and advanced matrix processing strategies are studied. A local reordering method is developed to speed the solution of linear systems. Numerical experiments show that these computational methods are effective and scalable, and are capable of computing large-scale reservoir simulation problems using thousands of CPU cores on parallel computers. The nonlinear techniques, preconditioner and matrix processing strategies can also be applied to three-phase black oil, compositional and thermal models.
- Dec 19 2016 cs.CV arXiv:1612.05365v1Kernelized Correlation Filter (KCF) is one of the state-of-the-art object trackers. However, it does not reasonably model the distribution of correlation response during tracking process, which might cause the drifting problem, especially when targets undergo significant appearance changes due to occlusion, camera shaking, and/or deformation. In this paper, we propose an Output Constraint Transfer (OCT) method that by modeling the distribution of correlation response in a Bayesian optimization framework is able to mitigate the drifting problem. OCT builds upon the reasonable assumption that the correlation response to the target image follows a Gaussian distribution, which we exploit to select training samples and reduce model uncertainty. OCT is rooted in a new theory which transfers data distribution to a constraint of the optimized variable, leading to an efficient framework to calculate correlation filters. Extensive experiments on a commonly used tracking benchmark show that the proposed method significantly improves KCF, and achieves better performance than other state-of-the-art trackers. To encourage further developments, the source code is made available https://github.com/bczhangbczhang/OCT-KCF.
- Oct 04 2016 cs.CV arXiv:1610.00291v1We present a novel method for constructing Variational Autoencoder (VAE). Instead of using pixel-by-pixel loss, we enforce deep feature consistency between the input and the output of a VAE, which ensures the VAE's output to preserve the spatial correlation characteristics of the input, thus leading the output to have a more natural visual appearance and better perceptual quality. Based on recent deep learning works such as style transfer, we employ a pre-trained deep convolutional neural network (CNN) and use its hidden features to define a feature perceptual loss for VAE training. Evaluated on the CelebA face dataset, we show that our model produces better results than other methods in the literature. We also show that our method can produce latent vectors that can capture the semantic information of face expressions and can be used to achieve state-of-the-art performance in facial attribute prediction.
- Sep 30 2016 cs.CL arXiv:1609.09171v2Recurrent Neural Networks have achieved state-of-the-art results for many problems in NLP and two most popular RNN architectures are Tail Model and Pooling Model. In this paper, a hybrid architecture is proposed and we present the first empirical study using LSTMs to compare performance of the three RNN structures on sentence classification task. Experimental results show that the Max Pooling Model or Hybrid Max Pooling Model achieves the best performance on most datasets, while Tail Model does not outperform other models.
- Sep 07 2016 cs.CV arXiv:1609.01366v1We present a method for discovering and exploiting object specific deep learning features and use face detection as a case study. Motivated by the observation that certain convolutional channels of a Convolutional Neural Network (CNN) exhibit object specific responses, we seek to discover and exploit the convolutional channels of a CNN in which neurons are activated by the presence of specific objects in the input image. A method for explicitly fine-tuning a pre-trained CNN to induce an object specific channel (OSC) and systematically identifying it for the human face object has been developed. Based on the basic OSC features, we introduce a multi-resolution approach to constructing robust face heatmaps for fast face detection in unconstrained settings. We show that multi-resolution OSC can be used to develop state of the art face detectors which have the advantage of being simple and compact.
- Jun 08 2016 cs.CV arXiv:1606.02170v2There is a neglected fact in the traditional machine learning methods that the data sampling can actually lead to the solution sampling. We consider this observation to be important because having the solution sampling available makes the variable distribution estimation, which is a problem in many learning-related applications, more tractable. In this paper, we implement this idea on correlation filter, which has attracted much attention in the past few years due to its high performance with a low computational cost. More specifically, we propose a new method, named latent constrained correlation filters (LCCF) by mapping the correlation filters to a given latent subspace, in which we establish a new learning framework that embeds distribution-related constraints into the original problem. We further introduce a subspace based alternating direction method of multipliers (SADMM) to efficiently solve the optimization problem, which is proved to converge at the saddle point. Our approach is successfully applied to two different tasks inclduing eye localization and car detection. Extensive experiments demonstrate that LCCF outperforms the state-of-the-art methods when samples are suffered from noise and occlusion.
- A parallel reservoir simulator has been developed, which is designed for large-scale black oil simulations. It handles three phases, including water, oil and gas, and three components, including water, oil and gas. This simulator can calculate traditional reservoir models and naturally fractured models. Various well operations are supported, such as water flooding, gas flooding and polymer flooding. The operation constraints can be fixed bottom-hole pressure, a fixed fluid rate, and combinations of them. The simulator is based on our in-house platform, which provides grids, cell-centred data, linear solvers, preconditioners and well modeling. The simulator and the platform use MPI for communications among computation nodes. Our simulator is capable of simulating giant reservoir models with hundreds of millions of grid cells. Numerical simulations show that our simulator matches with commercial simulators and it has excellent scalability.
- Skeleton based action recognition distinguishes human actions using the trajectories of skeleton joints, which provide a very good representation for describing actions. Considering that recurrent neural networks (RNNs) with Long Short-Term Memory (LSTM) can learn feature representations and model long-term temporal dependencies automatically, we propose an end-to-end fully connected deep LSTM network for skeleton based action recognition. Inspired by the observation that the co-occurrences of the joints intrinsically characterize human actions, we take the skeleton as the input at each time slot and introduce a novel regularization scheme to learn the co-occurrence features of skeleton joints. To train the deep LSTM network effectively, we propose a new dropout algorithm which simultaneously operates on the gates, cells, and output responses of the LSTM neurons. Experimental results on three human action recognition datasets consistently demonstrate the effectiveness of the proposed model.
- Tensors provide natural representations for massive multi-mode datasets and tensor methods also form the backbone of many machine learning, signal processing, and statistical algorithms. The utility of tensors is mainly due to the ability to identify overcomplete, non-orthogonal factors from tensor data, which is known as tensor decomposition. This work develops theories and computational methods for guaranteed overcomplete, non-orthogonal tensor decomposition using convex optimization. We consider tensor decomposition as a problem of measure estimation from moments. We develop the theory for guaranteed decomposition under three assumptions: (i) Incoherence; (ii) Bounded spectral norm; and (iii) Gram isometry. We show that under these three assumptions, one can retrieve tensor decomposition by solving a convex, infinite-dimensional analog of $\ell_1$ minimization on the space of measures. The optimal value of this optimization defines the tensor nuclear norm that can be used to regularize tensor inverse problems, including tensor completion, denoising, and robust tensor principal component analysis. Remarkably, all the three assumptions are satisfied with high probability if the rank-one tensor factors are uniformly distributed on the unit spheres, implying exact decomposition for tensors with random factors. We also present and numerically test two computational methods based respectively on Burer-Monteiro low-rank factorization reformulation and the Sum-of-Squares relaxations.
- Representation theorems are established for fixed points of adjoint functors between categories enriched in a small quantaloid. In a very general setting these results set up a common framework for representation theorems of concept lattices in formal concept analysis (FCA) and rough set theory (RST), which not only extend the realm of formal contexts to multi-typed and multi-valued ones, but also provide a general approach to construct various kinds of representation theorems. Besides incorporating several well-known representation theorems in FCA and RST as well as formulating new ones, it is shown that concept lattices in RST can always be represented as those in FCA through relative pseudo-complements of the given contexts, especially if the contexts are valued in a non-Girard quantaloid.
- Learning deeper convolutional neural networks becomes a tendency in recent years. However, many empirical evidences suggest that performance improvement cannot be gained by simply stacking more layers. In this paper, we consider the issue from an information theoretical perspective, and propose a novel method Relay Backpropagation, that encourages the propagation of effective information through the network in training stage. By virtue of the method, we achieved the first place in ILSVRC 2015 Scene Classification Challenge. Extensive experiments on two challenging large scale datasets demonstrate the effectiveness of our method is not restricted to a specific dataset or network architecture. Our models will be available to the research community later.
- May 08 2015 cs.CV arXiv:1505.01589v2Local structures of shadow boundaries as well as complex interactions of image regions remain largely unexploited by previous shadow detection approaches. In this paper, we present a novel learning-based framework for shadow region recovery from a single image. We exploit the local structures of shadow edges by using a structured CNN learning framework. We show that using the structured label information in the classification can improve the local consistency of the results and avoid spurious labelling. We further propose and formulate a shadow/bright measure to model the complex interactions among image regions. The shadow and bright measures of each patch are computed from the shadow edges detected in the image. Using the global interaction constraints on patches, we formulate a least-square optimization problem for shadow recovery that can be solved efficiently. Our shadow recovery method achieves state-of-the-art results on the major shadow benchmark databases collected under various conditions.
- Apr 23 2015 cs.CV arXiv:1504.05809v1In this paper, we propose a novel local feature, called Local Orientation Adaptive Descriptor (LOAD), to capture regional texture in an image. In LOAD, we proposed to define point description on an Adaptive Coordinate System (ACS), adopt a binary sequence descriptor to capture relationships between one point and its neighbors and use multi-scale strategy to enhance the discriminative power of the descriptor. The proposed LOAD enjoys not only discriminative power to capture the texture information, but also has strong robustness to illumination variation and image rotation. Extensive experiments on benchmark data sets of texture classification and real-world material recognition show that the proposed LOAD yields the state-of-the-art performance. It is worth to mention that we achieve a 65.4\% classification accuracy-- which is, to the best of our knowledge, the highest record by far --on Flickr Material Database by using a single feature. Moreover, by combining LOAD with the feature extracted by Convolutional Neural Networks (CNN), we obtain significantly better performance than both the LOAD and CNN. This result confirms that the LOAD is complementary to the learning-based features.
- Chu connections and back diagonals are introduced as morphisms for distributors between categories enriched in a small quantaloid $\mathcal{Q}$. These notions, meaningful for closed bicategories, dualize the constructions of arrow categories and the Freyd completion of categories. It is shown that, for a small quantaloid $\mathcal{Q}$, the category of complete $\mathcal{Q}$-categories and left adjoints is a retract of the dual of the category of $\mathcal{Q}$-distributors and Chu connections, and it is dually equivalent to the category of $\mathcal{Q}$-distributors and back diagonals. As an application of Chu connections, a postulation of the intuitive idea of reduction of formal contexts in the theory of formal concept analysis is presented, and a characterization of reducts of formal contexts is obtained.
- In this article, we investigate self-organizing optimization for cognitive small cells (CSCs), which have the ability to sense the environment, learn from historical information, make intelligent decisions, and adjust their operational parameters. By exploring the inherent features, some fundamental challenges for self-organizing optimization in CSCs are presented and discussed. Specifically, the dense and random deployment of CSCs brings about some new challenges in terms of scalability and adaptation; furthermore, the uncertain, dynamic and incomplete information constraints also impose some new challenges in terms of convergence and robustness. For providing better service to the users and improving the resource utilization, four requirements for self-organizing optimization in CSCs are presented and discussed. Following the attractive fact that the decisions in game-theoretic models are exactly coincident with those in self-organizing optimization, i.e., distributed and autonomous, we establish a framework of game-theoretic solutions for self-organizing optimization in CSCs, and propose some featured game models. Specifically, their basic models are presented, some examples are discussed and future research directions are given.
- This letter investigates the problem of distributed spectrum access for cognitive small cell networks. Compared with existing work, two inherent features are considered: i) the transmission of a cognitive small cell base station only interferes with its neighbors due to the low power, i.e., the interference is local, and ii) the channel state is time-varying due to fading. We formulate the problem as a robust graphical game, and prove that it is an ordinal potential game which has at least one pure strategy Nash equilibrium (NE). Also, the lower throughput bound of NE solutions is analytically obtained. To cope with the dynamic and incomplete information constraints, we propose a distribute spectrum access algorithm to converge to some stable results. Simulation results validate the effectiveness of the proposed game-theoretic distributed learning solution in time-varying spectrum environment.
- This article investigates the problem of dynamic spectrum access for canonical wireless networks, in which the channel states are time-varying. In the most existing work, the commonly used optimization objective is to maximize the expectation of a certain metric (e.g., throughput or achievable rate). However, it is realized that expectation alone is not enough since some applications are sensitive to fluctuations. Effective capacity is a promising metric for time-varying service process since it characterizes the packet delay violating probability (regarded as an important statistical QoS index), by taking into account not only the expectation but also other high-order statistic. Therefore, we formulate the interactions among the users in the time-varying environment as a non-cooperative game, in which the utility function is defined as the achieved effective capacity. We prove that it is an ordinal potential game which has at least one pure strategy Nash equilibrium. Based on an approximated utility function, we propose a multi-agent learning algorithm which is proved to achieve stable solutions with dynamic and incomplete information constraints. The convergence of the proposed learning algorithm is verified by simulation results. Also, it is shown that the proposed multi-agent learning algorithm achieves satisfactory performance.
- Feb 10 2015 cs.CV arXiv:1502.02171v1For long time, person re-identification and image search are two separately studied tasks. However, for person re-identification, the effectiveness of local features and the "query-search" mode make it well posed for image search techniques. In the light of recent advances in image search, this paper proposes to treat person re-identification as an image search problem. Specifically, this paper claims two major contributions. 1) By designing an unsupervised Bag-of-Words representation, we are devoted to bridging the gap between the two tasks by integrating techniques from image search in person re-identification. We show that our system sets up an effective yet efficient baseline that is amenable to further supervised/unsupervised improvements. 2) We contribute a new high quality dataset which uses DPM detector and includes a number of distractor images. Our dataset reaches closer to realistic settings, and new perspectives are provided. Compared with approaches that rely on feature-feature match, our method is faster by over two orders of magnitude. Moreover, on three datasets, we report competitive results compared with the state-of-the-art methods.
- In fading channels, power allocation over channel state may bring a rate increment compared to the fixed constant power mode. Such a rate increment is referred to power allocation gain. It is expected that the power allocation gain varies for different relay protocols. In this paper, Decode-and-Forward (DF) and Compress-and-Forward (CF) protocols are considered. We first establish a general framework for relay power allocation of DF and CF over channel state in half-duplex relay channels and present the optimal solution for relay power allocation with auxiliary parameters, respectively. Then, we reconsider the power allocation problem for one hybrid scheme which always selects the better one between DF and CF and obtain a near optimal solution for the hybrid scheme by introducing an auxiliary rate function as well as avoiding the non-concave rate optimization problem.
- The 0-1 matrix A contains a 0-1 matrix M if some submatrix of A can be transformed into M by changing some ones to zeroes. If A does not contain M, then A avoids M. Let ex(n,M) be the maximum number of ones in an n x n 0-1 matrix that avoids M, and let ex_k(m,M) be the maximum number of columns in a 0-1 matrix with m rows that avoids M and has at least k ones in every column. A method for bounding ex(n,M) by using bounds on the maximum number of edges in bar visibility graphs was introduced in (R. Fulek, Discrete Mathematics 309, 2009). By using a similar method with bar visibility hypergraphs, we obtain linear bounds on the extremal functions of other forbidden 0-1 matrices.
- Keystroke Dynamics is an important biometric solution for person authentication. Based upon keystroke dynamics, this paper designs an embedded password protection device, develops an online system, collects two public databases for promoting the research on keystroke authentication, exploits the Gabor filter bank to characterize keystroke dynamics, and provides benchmark results of three popular classification algorithms, one-class support vector machine, Gaussian classifier, and nearest neighbour classifier.
- In this paper, we mainly consider quasi-cyclic (QC) codes over finite chain rings. We study module structures and trace representations of QC codes, which lead to some lower bounds on the minimum Hamming distance of QC codes. Moreover, we investigate the structural properties of 1-generator QC codes. Under some conditions, we discuss the enumeration of 1-generator QC codes and describe how to obtain the one and only one generator for each 1-generator QC code.
- In this work, we study a class of generalized quasi-cyclic (GQC) codes called skew GQC codes. By the factorization theory of ideals, we give the Chinese Remainder Theorem over the skew polynomial ring, which leads to a canonical decomposition of skew GQC codes. We also focus on some characteristics of skew GQC codes in details. For a 1-generator skew GQC code, we define the parity-check polynomial, determine the dimension and give a lower bound on the minimum Hamming distance. The skew quasi-cyclic (QC) codes are also discussed briefly.
- Generalized quasi-cyclic (GQC) codes with arbitrary lengths over the ring $\mathbb{F}_{q}+u\mathbb{F}_{q}$, where $u^2=0$, $q=p^n$, $n$ a positive integer and $p$ a prime number, are investigated. By the Chinese Remainder Theorem, structural properties and the decomposition of GQC codes are given. For 1-generator GQC codes, minimal generating sets and lower bounds on the minimum distance are given. As a special class of GQC codes, quasi-cyclic (QC) codes over $\mathbb{F}_q+u\mathbb{F}_q$ are also discussed briefly in this paper.
- The developable surface is an important surface in computer aided design, geometric modeling and industrial manufactory. It is often given in the stan- dard parametric form, but it can also be in the implicit form which is commonly used in algebraic geometry. Not all algebraic developable surfaces have rational parametrizations. In this paper, we focus on the rational developable surfaces. For a given algebraic surface, we first determine whether it is developable by geometric inspection, and we give a rational proper parametrization for the af- firmative case. For a rational parametric surface, we can also determine the developability and give a proper reparametrization for the developable surface.
- In this paper, we present an algorithm for reparametrizing algebraic plane curves from a numerical point of view. That is, we deal with mathematical objects that are assumed to be given approximately. More precisely, given a tolerance $\epsilon>0$ and a rational parametrization $\cal P$ with perturbed float coefficients of a plane curve $\cal C$, we present an algorithm that computes a parametrization $\cal Q$ of a new plane curve $\cal D$ such that ${\cal Q}$ is an \it $\epsilon$--proper reparametrization of $\cal D$. In addition, the error bound is carefully discussed and we present a formula that measures the "closeness" between the input curve $\cal C$ and the output curve $\cal D$.
- The ruled surface is a typical modeling surface in computer aided geometric design. It is usually given in the standard parametric form. However, it can also be in the forms than the standard one. For these forms, it is necessary to determine and find the standard form. In this paper, we present algorithms to determine whether a given implicit surface is a rational ruled surface. A parametrization of the surface is computed for the affirmative case. We also consider the parametric situation. More precisely, after a given rational parametric surface is determined as a ruled one, we reparameterize it to the standard form.
- The problem of 1-bit compressive sampling is addressed in this paper. We introduce an optimization model for reconstruction of sparse signals from 1-bit measurements. The model targets a solution that has the least l0-norm among all signals satisfying consistency constraints stemming from the 1-bit measurements. An algorithm for solving the model is developed. Convergence analysis of the algorithm is presented. Our approach is to obtain a sequence of optimization problems by successively approximating the l0-norm and to solve resulting problems by exploiting the proximity operator. We examine the performance of our proposed algorithm and compare it with the binary iterative hard thresholding (BIHT) [10] a state-of-the-art algorithm for 1-bit compressive sampling reconstruction. Unlike the BIHT, our model and algorithm does not require a prior knowledge on the sparsity of the signal. This makes our proposed work a promising practical approach for signal acquisition.
- The prevention of dangerous chemical accidents is a primary problem of industrial manufacturing. In the accidents of dangerous chemicals, the oil gas explosion plays an important role. The essential task of the explosion prevention is to estimate the better explosion limit of a given oil gas. In this paper, Support Vector Machines (SVM) and Logistic Regression (LR) are used to predict the explosion of oil gas. LR can get the explicit probability formula of explosion, and the explosive range of the concentrations of oil gas according to the concentration of oxygen. Meanwhile, SVM gives higher accuracy of prediction. Furthermore, considering the practical requirements, the effects of penalty parameter on the distribution of two types of errors are discussed.
- The purpose of this study was to provide insights into the eBook market in China through case studies on eBook companies and a survey research with individual eBook users. The information from three companies, Beijing Superstar Electric Company, Beijing Founder APABI Technology Limited, and Beijing Sursen Electronic Technology Company Limited, showed that the B2B market has been developed due to the huge requirement from organization customers, universities libraries in particularly, and the B2C market is still immature. The information from interviews and relative data revealed that both Superstar and Sursen have serious copyright infringement which is an important problem impeding the further development of the eBook market. The questionnaire explored awareness, purchase, reading and other experiences of eBook end-users. Questions indicated that readers were attracted by the technical advantages including costless to copy, easy to transfer, searchable and easy to store, but did not want to pay for eBooks. Because the computers, especially desktop PCs, were the main device for reading and the CRT displays were massive used while there were few dedicated reading device in the market, many eBook end-users still preferred to read extended passages of text on papers rather than screens. Today the copyrights issue, user acceptance and the reading device are three significant obstacles for eBook industry in China.
- We present an approach of computing the intersection curve $\mathcal{C}$ of two rational parametric surface $\S_1(u,s)$ and $\S_2(v,t)$, one being projectable and hence can easily be implicitized. Plugging the parametric surface to the implicit surface yields a plane algebraic curve $G(v,t)=0$. By analyzing the topology graph $\G$ of $G(v,t)=0$ and the singular points on the intersection curve $\mathcal{C}$ we associate a space topology graph to $\mathcal{C}$, which is homeomorphic to $\mathcal{C}$ and therefore leads us to an approximation for $\mathcal{C}$ in a given precision.
- Approximating complex curves with simple parametric curves is widely used in CAGD, CG, and CNC. This paper presents an algorithm to compute a certified approximation to a given parametric space curve with cubic B-spline curves. By certified, we mean that the approximation can approximate the given curve to any given precision and preserve the geometric features of the given curve such as the topology, singular points, etc. The approximated curve is divided into segments called quasi-cubic Bézier curve segments which have properties similar to a cubic rational Bézier curve. And the approximate curve is naturally constructed as the associated cubic rational Bézier curve of the control tetrahedron of a quasi-cubic curve. A novel optimization method is proposed to select proper weights in the cubic rational Bézier curve to approximate the given curve. The error of the approximation is controlled by the size of its tetrahedron, which converges to zero by subdividing the curve segments. As an application, approximate implicit equations of the approximated curves can be computed. Experiments show that the method can approximate space curves of high degrees with high precision and very few cubic Bézier curve segments.
- Nov 04 2011 cs.SC arXiv:1111.0732v1Loop invariants play a very important role in proving correctness of programs. In this paper, we address the problem of generating invariants of polynomial loop programs. We present a new approach, for generating polynomial equation invariants of polynomial loop programs through computing vanishing ideals of sample points. We apply rational function interpolation, based on early termination technique, to generate invariants of loop programs with symbolic initial values. Our approach avoids first-order quantifier elimination and cylindrical algebraic decomposition(CAD). An algorithm for generating polynomial invariants is proposed and some examples are given to illustrate the algorithm. Furthermore, we demonstrate on a set of loop programs with symbolic initial values that our algorithm can yield polynomial invariants with degrees high up to 15.
- Pattern learning in an important problem in Natural Language Processing (NLP). Some exhaustive pattern learning (EPL) methods (Bod, 1992) were proved to be flawed (Johnson, 2002), while similar algorithms (Och and Ney, 2004) showed great advantages on other tasks, such as machine translation. In this article, we first formalize EPL, and then show that the probability given by an EPL model is constant-factor approximation of the probability given by an ensemble method that integrates exponential number of models obtained with various segmentations of the training data. This work for the first time provides theoretical justification for the widely used EPL algorithm in NLP, which was previously viewed as a flawed heuristic method. Better understanding of EPL may lead to improved pattern learning algorithms in future.
- A wide class of regularization problems in machine learning and statistics employ a regularization term which is obtained by composing a simple convex function \omega with a linear transformation. This setting includes Group Lasso methods, the Fused Lasso and other total variation methods, multi-task learning methods and many more. In this paper, we present a general approach for computing the proximity operator of this class of regularizers, under the assumption that the proximity operator of the function \omega is known in advance. Our approach builds on a recent line of research on optimal first order optimization methods and uses fixed point iterations for numerically computing the proximity operator. It is more general than current approaches and, as we show with numerical simulations, computationally more efficient than available first order methods which do not achieve the optimal rate. In particular, our method outperforms state of the art O(1/T) methods for overlapping Group Lasso and matches optimal O(1/T^2) methods for the Fused Lasso and tree structured Group Lasso.