Narrow Results

Complementary prism graphs arise from the disjoint union of a graph $G$ and its complement $Ḡ$ by adding the edges of a perfect matching joining pairs of corresponding vertices of $G$ and $Ḡ$. Classical graph problems such as Clique and Independent Set were proved to be NP-complete on such a class of graphs. In this work, we study the complexity of both problems on complementary prism graphs from the parameterized complexity point of view. First, we prove that both problems admit a kernel and therefore are fixed-parameter tractable (FPT) when parameterized by the size of the solution, $k$. Then, we show that ${k}$-Clique and ${k}$-Independent Set on complementary prisms do not admit polynomial kernel when parameterized by $k$, unless $NP\subseteq coNP/poly$. Furthermore, we address the $2$-Contamination problem in the context of complementary prisms. This problem consists in completely contaminating a given graph $G$ using a minimum set of initially infected vertices. For a vertex to be contaminated, it is enough that at least two of its neighbors are contaminated. The propagation of the contamination follows this rule until no more vertex can be contaminated. It is known that the minimum set of initially contaminated vertices necessary to contaminate a complementary prism of connected graphs $G$ and $Ḡ$ has cardinality at most $5$. In this paper, we show that the tight upper bound for this invariant on complementary prisms is $3$, improving a result of Duarte et al. (2017).

Prototype based classifiers are effective algorithms in modeling classification problems and have been applied in multiple domains. While many supervised learning algorithms have been successfully extended to kernels to improve the discrimination power by means of the kernel concept, prototype based classifiers are typically still used with Euclidean distance measures. Kernelized variants of prototype based classifiers are currently too complex to be applied for larger data sets. Here we propose an extension of Kernelized Generalized Learning Vector Quantization (KGLVQ) employing a sparsity and approximation technique to reduce the learning complexity. We provide generalization error bounds and experimental results on real world data, showing that the extended approach is comparable to SVM on different public data.

As is known, kernel methods are developed to handle nonlinear classification. However, we have found that based on vector representation of face images, it is not easy to improve the performance of LDA-based methods by incorporating the kernel trick. Actually, in the case that the dimensionality of face images in vector form is far greater than the number of samples, linear classifiers are adequate and it is illogical to increase dimensions of vectors using kernel methods. In order to give full play to the strong point of the kernel technique for manipulating the nonlinearity of pattern distribution, we propose a new image feature extraction method for face recognition, called kernel-based two-dimensional Fisher discriminant analysis (K2DFDA), which deals with a face image directly as a matrix, instead of a stacked vector from rows or columns of the image. Moreover, we present a kernel parameter optimization scheme for K2DFDA, based on the maximum margin criterion and the damped Newton's method. Experimental results show the effectiveness of K2DFDA and its parameter optimization scheme.

Recently, deep convolutional neural networks have resulted in noticeable improvements in image classification and have been used to transfer artistic style of images. Gatys et al. proposed the use of a learned Convolutional Neural Network (CNN) architecture VGG to transfer image style, but problems occur during the back propagation process because there is a heavy computational load. This paper solves these problems, including the simplification of the computation of chains of derivatives, accelerating the computation of adjustments, and efficiently choosing weights for different energy functions. The experimental results show that the proposed solutions improve the computational efficiency and render the adjustment of weights for energy functions easier.

Automatic music genre classification based on distance metric learning (DML) is proposed in this paper. Three types of timbral descriptors, namely, mel-frequency cepstral coefficient (MFCC) features, modified group delay features (MODGDF) and low-level timbral feature sets are combined at the feature level. We experimented with k nearest neighbor (kNN) and support vector machine (SVM)-based classifiers for standard and DML kernels (DMLK) using GTZAN and Folk music dataset. Standard kernel-based kNN and SVM-based classifiers report classification accuracy (in%) of 79.03 and 90.16, respectively, on GTZAN dataset and 86.60 and 92.26, respectively, for Folk music dataset, with the best performing RBF kernel. A further improvement was observed when DML kernels were used in place of standard kernels in the kernel kNN and SVM-based classifiers with an accuracy of 84.46%, 92.74% (GTZAN), 90.00 and 96.23 (Folk music dataset) for DMLK-kNN and DMLK-SVM, respectively. The results demonstrate the potential of DML kernels in music genre classification task.

Abnormal cells in the human body that keep on mutating are termed to be cancer in medical terms. There are multiple types of cancer identified in human beings. It is very much essential to identify and classify the type of cancer in its earlier stage. This objective can be satisfied by artificial intelligence which has a subfield of machine learning to create a generalized model that could identify and classify cancer with increased performance. To perform the identification and classification of various cancer types, in this paper, two techniques are adopted. The optimized feature set computation was done using the Kernel-Induced Matriarch path tracking Elephant Herding Optimization (KIM-EHO) and the classification for the given samples was done using the Support Vector Machines (SVM). The proposed techniques are implemented with the benchmark datasets and the results proved that the proposed methodologies outperformed the existing methods in terms of accuracy, specificity, sensitivity and time complexity.

Object tracking in real-time is one of the applications of video processing, where the required computational cost is high due to intensive high data processing. In order to solve these problems, this paper presents an embedded solution, where the Hardware/Software (HW/SW) co-design architecture is used for the implementation of well-known kernel-based tracking system. In this algorithm, the target is searched in consecutive frame by maximizing the statistical match with similarity estimation of color distribution. The whole tracking system is implemented on low cost Field Programmable Gate Array (FPGA) device with image resolution of 1280$\times$720 pixels and target window size of 160$\times$80 pixels. The HW/SW co-design architecture is proposed to accelerate the computational speed of the system. The performance of the system is evaluated in terms of execution speed and frame rate compared with software based implementation. The hardware cost of design is also compared with other existing methods. The proposed design achieves 22 times computational speed and maximum 60 Frames Per Second (FPS) compared with software based design.

This paper proposes an integrated system neutrosophic C-means-based attribute weighting-kernel extreme learning machine (NCMAW-KELM) for medical data classification using NCM clustering and KELM. To do that, NCMAW is developed, and then combined with classification method in classification of medical data. The proposed approach contains two steps. In the first step, input attributes are weighted using NCMAW method. The purpose of the weighting method is twofold: (i) to improve the classification performance in the classification of the medical data, (ii) to transform from nonlinearly separable dataset to linearly separable dataset. Finally, KELM algorithm is used for medical data classification purpose. In KELM algorithm, four types of kernels, such as Polynomial, Sigmoid, Radial basis function and Linear, are used. The simulation result on our three datasets demonstrates that the sigmoid kernel is outperformed to ELM in most cases. From the results, NCMAW-KELM approach may be a promising method in medical data classification problem.

Kernels are widely used in Natural Language Processing as similarity measures within inner-product based learning methods like the Support Vector Machine. The Vector Space Model (VSM) is extensively used for the spatial representation of the documents. However, it is purely a statistical representation. In this paper, we present a Concept Vector Space Model (CVSM) representation which uses linguistic prior knowledge to capture the meanings of the documents. We also propose a linear kernel and a latent kernel for this space. The linear kernel takes advantage of the linguistic concepts whereas the latent kernel combines statistical and linguistic concepts. Indeed, the latter kernel uses latent concepts extracted by the Latent Semantic Analysis (LSA) in the CVSM. The kernels were evaluated on a text categorization task in the biomedical domain. The Ohsumed corpus, well known for being difficult to categorize, was used. The results have shown that the CVSM improves performance compared to the VSM.

We present algorithms for computing the kernel of a closed freeform rational surface. The kernel computation is reformulated as a problem of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the kernel. Using a plane-point duality, this paper also explores a duality relationship between the kernel of a closed surface and the convex hull of its tangential surface.

The paper is devoted on the one hand to (pre)kernel catchers and on the other hand to the coincidence of the kernel K with the prekernel Pr K. Sufficient conditions for the coincidence K = Pr K are given by the inclusions R* ⊆ X or L* ∩ R* ⊆ X. Here X denotes the imputation set. The two sets R* and L* consist of those preimputations of which the payoffs are bounded above by player's maximal marginal contribution or bounded below by player's minimal marginal contribution.

Generalizations of reactive and semi-reactive bargaining sets of TU games are defined for the case when objections and counter-objections are permitted not between singletons but between elements of a family of coalitions ${𝒜}$ and can use coalitions from ${ℬ}\supset {𝒜}$. Necessary and sufficient conditions on ${𝒜}$, ${ℬ}$ that ensure existence results for generalizations of the reactive bargaining set and of the semi-reactive barganing set at each TU game $(N,v)$ with nonnegative values are obtained. The existence conditions for the generalized reactive bargaining set do not coincide with existence conditions for the generalized kernel and coincide with conditions for the generalized semi-reactive bargaining set only if $\left|N\right|\le 4$ and ${ℬ}=2^N$. The conditions for the generalized semi-reactive bargaining set coincide with conditions for the generalized classical bargaining set that were described in the previous papers of the author.

For monotonic ${ℬ}$, the condition on ${𝒜}$ for existence of the generalized semi-reactive bargaining sets on the class of games with nonnegative values is also necessary and sufficient on the class of simple games, but similar result for the generalized classical bargaining sets is proved only for $\left|N\right|\le 6$.

The problem of learning the kernel function has received considerable attention in machine learning. Much of the work has focused on kernel selection criteria, particularly on minimizing a regularized error functional over a prescribed set of kernels. Empirical studies indicate that this approach can enhance statistical performance and is computationally feasible. In this paper, we present a theoretical analysis of its generalization error. We establish for a wide variety of classes of kernels, such as the set of all multivariate Gaussian kernels, that this learning method generalizes well and, when the regularization parameter is appropriately chosen, it is consistent. A central role in our analysis is played by the interaction between the sample error and the approximation error.

Nonparametric regression techniques provide a very effective and simple way of finding structure in data sets without the imposition of a parametric regression model. Wavelet theory has the potential to provide statisticians with powerful new techniques for nonparametric inference. In this paper, we consider the wavelet shrinkage kernel estimator of regression function with a common one-dimensional probability density function. We investigate a new nonparametric curve estimator and convergence ratio of given estimator by using cross-validation method to choice of wavelet threshold when the observations are taken on the regular grid. At the end we used simulation study to examine our proposed estimator. We survey the theoretical outcomes with numerical computation by using $R$ software to compare purpose estimator with another estimators.

As a powerful unsupervised learning technique, clustering is the fundamental task of big data analysis. However, many traditional clustering algorithms for big data that is a collection of high dimension, sparse and noise data do not perform well both in terms of computational efficiency and clustering accuracy. To alleviate these problems, this paper presents Feature K-means clustering model on the feature space of big data and introduces its fast algorithm based on Alternating Direction Multiplier Method (ADMM). We show the equivalence of the Feature K-means model in the original space and the feature space and prove the convergence of its iterative algorithm. Computationally, we compare the Feature K-means with Spherical K-means and Kernel K-means on several benchmark data sets, including artificial data and four face databases. Experiments show that the proposed approach is comparable to the state-of-the-art algorithm in big data clustering.

Subspace clustering aims to seek a multi-subspace representation that is best suitable for data points taken from a high-dimensional space. Sparse representation and low-rank approximation-based methods have become one of the main melodies for subspace clustering. In the existing methods, nuclear norm is used to approximate rank minimization. However, the common deficiency still exists for nuclear norm, which always over-penalizes large singular values and results in a biased solution. In this paper, we propose a nonlinear subspace clustering model that exploits sparsity and low-rank of data in high dimensional feature space by using Schatten-p norm surrogate ($p\in (0,1)$) with learned low-rank kernel. By this manner, the model guarantees that the data mapped in the high-dimensional feature spaces is lower rank and self-expressive. And we show the alternating direction method of multipliers (abbreviated as ADMM) for the corresponding problem in a reproducing kernel Hilbert space. Various experiments on motion segmentation and image clustering display that the proposed model has potentiality in outperforming most of state-of-the-art models in current literature.

We propose a new method to visualize gene expression experiments inspired by the latent semantic indexing technique originally proposed in the textual analysis context. By using the correspondence word-gene document-experiment, we define an asymmetric similarity measure of association for genes that accounts for potential hierarchies in the data, the key to obtain meaningful gene mappings. We use the polar decomposition to obtain the sources of asymmetry of the similarity matrix, which are later combined with previous knowledge. Genetic classes of genes are identified by means of a mixture model applied in the genes latent space. We describe the steps of the procedure and we show its utility in the Human Cancer dataset.

On completely regular semirings, we give alternative characterizations for the kernel of a congruence and idempotent pure congruences. Then we give alternative characterizations for the trace of a congruence and idempotent separating congruences. In addition, we conclude that a congruence is uniquely determined by its kernel and trace.

Let $X$ be a nonempty set and let $T(X)$ be the full transformation semigroup on $X$. The main objective of this paper is to study the subsemigroup $\overline{\mathrm{\Omega }}(X,Y)$ of $T(X)$ defined by

We study upper and lower bounds on the vertex-kernel size for the 3-HITTING SET problem on hypergraphs of degree at most 3, denoted 3-3-HS. We first show that, unless P = NP, 3-3-HS on 3-uniform hypergraphs does not have a vertex-kernel of size at most 35k/19 > 1.8421k. We then give a 4k - k^0.2692 vertex-kernel for 3-3-hs that is computable in time O(k²). We do not assume that the hypergraph is 3-uniform for the vertex-kernel upper bound results. This result improves the upper bound of 4k on the vertex-kernel size for 3-3-HS, implied by the results of Wahlström.