We consider the problem of learning and verifying hidden graphs and their properties given query access to the graphs. We analyze various queries (edge detection, edge counting, shortest path), but we focus mainly on ...
详细信息
ISBN:
(纸本)9783540752240
We consider the problem of learning and verifying hidden graphs and their properties given query access to the graphs. We analyze various queries (edge detection, edge counting, shortest path), but we focus mainly on edge counting queries. We give an algorithm for learning graph partitions using O (n log n) edge counting queries. We introduce a problem that has not been considered: verifying graphs with edge counting queries, and give a randomized algorithm with error a for graph verification using O(log(1/epsilon)) edge counting queries. We examine the current state of the art and add some original results for edge detection and shortest path queries to give a more complete picture of the relative power of these queries to learn various graph classes. Finally, we relate our work to Freivalds' `fingerprinting technique' - a probabilistic method for verifying that two matrices are equal by multiplying them by random vectors.
Polynomials have proven to be useful tools to tailor generic kernels to specific applications. Nevertheless, we had only restricted knowledge for selecting fertile polynomials which consistently produce positive semid...
详细信息
Polynomials have proven to be useful tools to tailor generic kernels to specific applications. Nevertheless, we had only restricted knowledge for selecting fertile polynomials which consistently produce positive semidefinite kernels. For example, the well-known polynomial kernel can only take advantage of a very narrow range of polynomials, that is, the univariate polynomials with positive coefficients. this restriction not only hinders intensive exploitation of the flexibility of the kernel method, but also causes misuse of indefinite kernels. Our main theorem significantly relaxes the restriction by asserting that a polynomial consistently produces positive semidefinite kernels, if it has a positive semidefinite coefficient matrix. this sufficient condition is quite natural, and hence, it can be a good characterization of the fertile polynomials. In fact, we prove that the converse of the assertion of the theorem also holds true in the case of degree 1. We also prove the effectiveness of our main theorem by showing three corollaries relating to certain applications known in the literature: the first and second corollaries, respectively, give generalizations of the polynomial kernel and the principal-angle (determinant) kernel. the third corollary shows extended and corrected sufficient conditions for the codon-improved kernel and the weighted-degree kernel with shifts to be positive semidefinite. (C) 2009 Elsevier B.V. All rights reserved.
the class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. this paper gives an even more general discussion on the efficiency of identification of very simple gramma...
详细信息
ISBN:
(纸本)9783540752240
the class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. this paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars. (C) 2009 Elsevier B.V. All rights reserved.
In this paper, we present our approach System Evolution Recommender (SysEvoRecomd). In SysEvoRecomd, we used our proposed Graph Evolution and Change learning (GECL) that does matrix reconstruction. Based on SysEvoReco...
详细信息
ISBN:
(纸本)9781538692882
In this paper, we present our approach System Evolution Recommender (SysEvoRecomd). In SysEvoRecomd, we used our proposed Graph Evolution and Change learning (GECL) that does matrix reconstruction. Based on SysEvoRecomd, we developed an automation tool named as SysEvoRecomd-Tool, which is used to conduct experiments on various real-world evolving systems.
Estimated generalization error is the main index that indicates learning performance, but it is inadequate for further analysis. Bias-variance theory tries to overcome the limitation of analyzing learning performance,...
详细信息
ISBN:
(纸本)0769525210
Estimated generalization error is the main index that indicates learning performance, but it is inadequate for further analysis. Bias-variance theory tries to overcome the limitation of analyzing learning performance, but the concept of bias-variance is still controversial when applied to the classification problem. In this paper, we propose a new alternative, simple and practical, analytical method called 'migration analysis' to analyze the learning results. We compare the properties of migration analysis to bias-variance framework, and use it to analyze two so-called ensemble learners: bagging and AdaBoost. the results not only explain these ensemble learners in different ways, but also shed light to the new promising learning algorithm.
the abundance of educational resources available on the Web leads to information overload for the students and the difficulty in finding useful and relevant resources for a specific learning context. the solution that...
详细信息
ISBN:
(纸本)9781479946013
the abundance of educational resources available on the Web leads to information overload for the students and the difficulty in finding useful and relevant resources for a specific learning context. the solution that we propose in this paper is a platform called Edu3R (Educational Resources Retrieval and Recommendation), which relies on community filtering: students enrolled in the same course can perform collaborative search through various learning object repositories, bookmark the resources of interest, rate them and share them with peers. the rationale is that resources found and selected by peers are likely to be relevant since the learning community is centered around the same course and the same learning tasks and is relatively homogeneous (classmates generally having common learning backgrounds and completing the same curriculum). Edu3R also relies on social tagging, through which learners annotate resources with meaningful terms that reflect the educational context, provide a personalized classification and facilitate subsequent retrieval. Finally, Edu3R also integrates a collaborative filtering mechanism for recommending learning resources based on student similarity. the paper provides an overview of the system architecture, functionalities and pedagogical rationale, as well as a comparison with similar platforms.
Mixed reality (MR) concepts gained significant importance in recent years, tending to be more and more domain-specific. the current paper presents a survey on MR educational applications and debates whether they are s...
详细信息
ISBN:
(纸本)9781479946013
Mixed reality (MR) concepts gained significant importance in recent years, tending to be more and more domain-specific. the current paper presents a survey on MR educational applications and debates whether they are suitable or not to support several new learning paradigms. the technological specifications and challenges of each analyzed application are provided, in the context of current trends of MR and technological developments. Among others, the innovative criterion of virtual-real merging degree is introduced. Also, the benefits and drawbacks of exploiting MR to implement such paradigms are underlined.
In transfer learningthe aim is to solve new learning tasks using fewer examples by using information gained from solving related tasks. Existing transfer learning methods have been used successfully in practice and P...
详细信息
ISBN:
(纸本)9783540752240
In transfer learningthe aim is to solve new learning tasks using fewer examples by using information gained from solving related tasks. Existing transfer learning methods have been used successfully in practice and PAC analysis of these methods have been developed. But the key notion of relatedness between tasks has not yet been defined clearly, which makes it difficult to understand, let alone answer, questions that naturally arise ill the context of transfer, such as, how much information to transfer, whether to transfer information, and how to transfer information across tasks. In this paper, we look at transfer learning from the perspective of algorithmic Information theory/Kolmogorov complexity theory, and formally solve these problems in the same sense Solomonoff Induction solves the problem of inductive inference. We define universal measures of relatedness between tasks, and use these measures to develop universally optimal Bayesian transfer learning methods. We also derive results in AlT that are interesting by themselves. To address a concern that arises from the theory, we also briefly look at the notion of Kolmogorov complexity of probability measures. Finally, we present a simple practical approximation to the theory to do transfer learning and show that even these are quite effective, allowing LIS to transfer across tasks that are superficially unrelated. the latter is an experimental feat which has not been achieved before, and thus shows the theory is also useful in constructing practical transfer algorithms. (C) 2009 Elsevier B.V. All rights reserved.
the paper presents the comparative analysis of the computer systems for face recognition. Autoencoder, the typical representative of deep learning is compared withthe classical PCA transformation. Both, autoencoder a...
详细信息
ISBN:
(纸本)9781538610404
the paper presents the comparative analysis of the computer systems for face recognition. Autoencoder, the typical representative of deep learning is compared withthe classical PCA transformation. Both, autoencoder and PCA serve as the tools for feature generation and selection. However, the important difference is the nonlinearity and multilayer structure applied in autoencoder. Final task of recognition is done by the support vector machine or softmax circuit. the numerical results performed on the multiclass base of faces have shown superiority of autoencoding principle, especially when the number of recognized classes is very high.
暂无评论