Arrow Research search

Author name cluster

John Shawe-Taylor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

73 papers
2 author rows

Possible papers

73

AAAI Conference 2025 Conference Paper

General Uncertainty Estimation with Delta Variances

  • Simon Schmitt
  • John Shawe-Taylor
  • Hado van Hasselt

Decision makers may suffer from uncertainty induced by limited data. This may be mitigated by accounting for epistemic uncertainty, which is however challenging to estimate efficiently for large neural networks. To this extent we investigate Delta Variances, a family of algorithms for epistemic uncertainty quantification, that is computationally efficient and convenient to implement. It can be applied to neural networks and more general functions composed of neural networks. As an example we consider a weather simulator with a neural-network-based step function inside - here Delta Variances empirically obtain competitive results at the cost of a single gradient computation. The approach is convenient as it requires no changes to the neural network architecture or training procedure. We discuss multiple ways to derive Delta Variances theoretically noting that special cases recover popular techniques and present a unified perspective on multiple related methods. Finally we observe that this general perspective gives rise to a natural extension and empirically show its benefit.

PDF Details DOI

AIJ Journal 2025 Journal Article

Human-AI coevolution

  • Dino Pedreschi
  • Luca Pappalardo
  • Emanuele Ferragina
  • Ricardo Baeza-Yates
  • Albert-László Barabási
  • Frank Dignum
  • Virginia Dignum
  • Tina Eliassi-Rad

Human-AI coevolution, defined as a process in which humans and AI algorithms continuously influence each other, increasingly characterises our society, but is understudied in artificial intelligence and complexity science literature. Recommender systems and assistants play a prominent role in human-AI coevolution, as they permeate many facets of daily life and influence human choices through online platforms. The interaction between users and AI results in a potentially endless feedback loop, wherein users' choices generate data to train AI models, which, in turn, shape subsequent user preferences. This human-AI feedback loop has peculiar characteristics compared to traditional human-machine interaction and gives rise to complex and often “unintended” systemic outcomes. This paper introduces human-AI coevolution as the cornerstone for a new field of study at the intersection between AI and complexity science focused on the theoretical, empirical, and mathematical investigation of the human-AI feedback loop. In doing so, we: (i) outline the pros and cons of existing methodologies and highlight shortcomings and potential ways for capturing feedback loop mechanisms; (ii) propose a reflection at the intersection between complexity science, AI and society; (iii) provide real-world examples for different human-AI ecosystems; and (iv) illustrate challenges to the creation of such a field of study, conceptualising them at increasing levels of abstraction, i.e., scientific, legal and socio-political.

Details DOI

IJCAI Conference 2025 Conference Paper

Human-AI Coevolution (Abstract Reprint)

  • Dino Pedreschi
  • Luca Pappalardo
  • Emanuele Ferragina
  • Ricardo Baeza-Yates
  • Albert-László Barabási
  • Frank Dignum
  • Virginia Dignum
  • Tina Eliassi-Rad

Human-AI coevolution, defined as a process in which humans and AI algorithms continuously influence each other, increasingly characterises our society, but is understudied in artificial intelligence and complexity science literature. Recommender systems and assistants play a prominent role in human-AI coevolution, as they permeate many facets of daily life and influence human choices through online platforms. The interaction between users and AI results in a potentially endless feedback loop, wherein users' choices generate data to train AI models, which, in turn, shape subsequent user preferences. This human-AI feedback loop has peculiar characteristics compared to traditional human-machine interaction and gives rise to complex and often “unintended” systemic outcomes. This paper introduces human-AI coevolution as the cornerstone for a new field of study at the intersection between AI and complexity science focused on the theoretical, empirical, and mathematical investigation of the human-AI feedback loop. In doing so, we: (i) outline the pros and cons of existing methodologies and highlight shortcomings and potential ways for capturing feedback loop mechanisms; (ii) propose a reflection at the intersection between complexity science, AI and society; (iii) provide real-world examples for different human-AI ecosystems; and (iv) illustrate challenges to the creation of such a field of study, conceptualising them at increasing levels of abstraction, i. e. , scientific, legal and socio-political.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound

  • Reuben Adams
  • John Shawe-Taylor
  • Benjamin Guedj

Current PAC-Bayes generalisation bounds are restricted to scalar metrics of performance, such as the loss or error rate. However, one ideally wants more information-rich certificates that control the entire distribution of possible outcomes, such as the distribution of the test loss in regression, or the probabilities of different mis-classifications. We provide the first PAC-Bayes bound capable of providing such rich information by bounding the Kullback-Leibler divergence between the empirical and true probabilities of a set of $M$ error types, which can either be discretized loss values for regression, or the elements of the confusion matrix (or a partition thereof) for classification. We transform our bound into a differentiable training objective. Our bound is especially useful in cases where the severity of different mis-classifications may change over time; existing PAC-Bayes bounds can only bound a particular pre-decided weighting of the error types. In contrast our bound implicitly controls all uncountably many weightings simultaneously.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Exploration via Epistemic Value Estimation

  • Simon Schmitt
  • John Shawe-Taylor
  • Hado van Hasselt

How to efficiently explore in reinforcement learning is an open problem. Many exploration algorithms employ the epistemic uncertainty of their own value predictions -- for instance to compute an exploration bonus or upper confidence bound. Unfortunately the required uncertainty is difficult to estimate in general with function approximation. We propose epistemic value estimation (EVE): a recipe that is compatible with sequential decision making and with neural network function approximators. It equips agents with a tractable posterior over all their parameters from which epistemic value uncertainty can be computed efficiently. We use the recipe to derive an epistemic Q-Learning agent and observe competitive performance on a series of benchmarks. Experiments confirm that the EVE recipe facilitates efficient exploration in hard exploration tasks.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Chaining Value Functions for Off-Policy Learning

  • Simon Schmitt
  • John Shawe-Taylor
  • Hado van Hasselt

To accumulate knowledge and improve its policy of behaviour, a reinforcement learning agent can learn ‘off-policy’ about policies that differ from the policy used to generate its experience. This is important to learn counterfactuals, or because the experience was generated out of its own control. However, off-policy learning is non-trivial, and standard reinforcementlearning algorithms can be unstable and divergent. In this paper we discuss a novel family of off-policy prediction algorithms which are convergent by construction. The idea is to first learn on-policy about the data-generating behaviour, and then bootstrap an off-policy value estimate on this onpolicy estimate, thereby constructing a value estimate that is partially off-policy. This process can be repeated to build a chain of value functions, each time bootstrapping a new estimate on the previous estimate in the chain. Each step in the chain is stable and hence the complete algorithm is guaranteed to be stable. Under mild conditions this comes arbitrarily close to the off-policy TD solution when we increase the length of the chain. Hence it can compute the solution even in cases where off-policy TD diverges. We prove that the proposed scheme is convergent and corresponds to an iterative decomposition of the inverse key matrix. Furthermore it can be interpreted as estimating a novel objective – that we call a ‘k-step expedition’ – of following the target policy for finitely many steps before continuing indefinitely with the behaviour policy. Empirically we evaluate the idea on challenging MDPs such as Baird’s counter example and observe favourable results.

PDF Details

JMLR Journal 2021 Journal Article

Tighter Risk Certificates for Neural Networks

  • María Pérez-Ortiz
  • Omar Rivasplata
  • John Shawe-Taylor
  • Csaba Szepesvári

This paper presents an empirical study regarding training probabilistic neural networks using training objectives derived from PAC-Bayes bounds. In the context of probabilistic neural networks, the output of training is a probability distribution over network weights. We present two training objectives, used here for the first time in connection with training neural networks. These two training objectives are derived from tight PAC-Bayes bounds. We also re-implement a previously used training objective based on a classical PAC-Bayes bound, to compare the properties of the predictors learned using the different training objectives. We compute risk certificates for the learnt predictors, based on part of the data used to learn the predictors. We further experiment with different types of priors on the weights (both data-free and data-dependent priors) and neural network architectures. Our experiments on MNIST and CIFAR-10 show that our training methods produce competitive test set errors and non-vacuous risk bounds with much tighter values than previous results in the literature, showing promise not only to guide the learning algorithm through bounding the risk but also for model selection. These observations suggest that the methods studied here might be good candidates for self-certified learning, in the sense of using the whole data set for learning a predictor and certifying its risk on any unseen data (from the same distribution as the training data) potentially without the need for holding out test data. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2021. ( edit, beta )

PDF Details

NeurIPS Conference 2020 Conference Paper

PAC-Bayes Analysis Beyond the Usual Bounds

  • Omar Rivasplata
  • Ilja Kuzborskij
  • Csaba Szepesvari
  • John Shawe-Taylor

We focus on a stochastic learning model where the learner observes a finite set of training examples and the output of the learning process is a data-dependent distribution over a space of hypotheses. The learned data-dependent distribution is then used to make randomized predictions, and the high-level theme addressed here is guaranteeing the quality of predictions on examples that were not seen during training, i. e. generalization. In this setting the unknown quantity of interest is the expected risk of the data-dependent randomized predictor, for which upper bounds can be derived via a PAC-Bayes analysis, leading to PAC-Bayes bounds. Specifically, we present a basic PAC-Bayes inequality for stochastic kernels, from which one may derive extensions of various known PAC-Bayes bounds as well as novel bounds. We clarify the role of the requirements of fixed ‘data-free’ priors, bounded losses, and i. i. d. data. We highlight that those requirements were used to upper-bound an exponential moment term, while the basic PAC-Bayes theorem remains valid without those restrictions. We present three bounds that illustrate the use of data-dependent priors, including one for the unbounded square loss.

PDF Details

AAAI Conference 2020 Short Paper

Towards an Integrative Educational Recommender for Lifelong Learners (Student Abstract)

  • Sahan Bulathwela
  • María Pérez-Ortiz
  • Emine Yilmaz
  • John Shawe-Taylor

One of the most ambitious use cases of computer-assisted learning is to build a recommendation system for lifelong learning. Most recommender algorithms exploit similarities between content and users, overseeing the necessity to leverage sensible learning trajectories for the learner. Lifelong learning thus presents unique challenges, requiring scalable and transparent models that can account for learner knowledge and content novelty simultaneously, while also retaining accurate learners representations for long periods of time. We attempt to build a novel educational recommender, that relies on an integrative approach combining multiple drivers of learners engagement. Our first step towards this goal is TrueLearn, which models content novelty and background knowledge of learners and achieves promising performance while retaining a human interpretable learner model.

PDF Details

AAAI Conference 2020 Conference Paper

TrueLearn: A Family of Bayesian Algorithms to Match Lifelong Learners to Open Educational Resources

  • Sahan Bulathwela
  • Maria Perez-Ortiz
  • Emine Yilmaz
  • John Shawe-Taylor

The recent advances in computer-assisted learning systems and the availability of open educational resources today promise a pathway to providing cost-efficient high-quality education to large masses of learners. One of the most ambitious use cases of computer-assisted learning is to build a lifelong learning recommendation system. Unlike short-term courses, lifelong learning presents unique challenges, requiring sophisticated recommendation models that account for a wide range of factors such as background knowledge of learners or novelty of the material while effectively maintaining knowledge states of masses of learners for significantly longer periods of time (ideally, a lifetime). This work presents the foundations towards building a dynamic, scalable and transparent recommendation system for education, modelling learner’s knowledge from implicit data in the form of engagement with open educational resources. We i) use a text ontology based on Wikipedia to automatically extract knowledge components of educational resources and, ii) propose a set of online Bayesian strategies inspired by the well-known areas of item response theory and knowledge tracing. Our proposal, TrueLearn, focuses on recommendations for which the learner has enough background knowledge (so they are able to understand and learn from the material), and the material has enough novelty that would help the learner improve their knowledge about the subject and keep them engaged. We further construct a large open educational video lectures dataset and test the performance of the proposed algorithms, which show clear promise towards building an effective educational recommendation system.

PDF Details

YNIMG Journal 2019 Journal Article

Combining heterogeneous data sources for neuroimaging based diagnosis: re-weighting and selecting what is important

  • Michele Donini
  • João M. Monteiro
  • Massimiliano Pontil
  • Tim Hahn
  • Andreas J. Fallgatter
  • John Shawe-Taylor
  • Janaina Mourão-Miranda

Combining neuroimaging and clinical information for diagnosis, as for example behavioral tasks and genetics characteristics, is potentially beneficial but presents challenges in terms of finding the best data representation for the different sources of information. Their simple combination usually does not provide an improvement if compared with using the best source alone. In this paper, we proposed a framework based on a recent multiple kernel learning algorithm called EasyMKL and we investigated the benefits of this approach for diagnosing two different mental health diseases. The well known Alzheimer's Disease Neuroimaging Initiative (ADNI) dataset tackling the Alzheimer Disease (AD) patients versus healthy controls classification task, and a second dataset tackling the task of classifying an heterogeneous group of depressed patients versus healthy controls. We used EasyMKL to combine a huge amount of basic kernels alongside a feature selection methodology, pursuing an optimal and sparse solution to facilitate interpretability. Our results show that the proposed approach, called EasyMKLFS, outperforms baselines (e. g. SVM and SimpleMKL), state-of-the-art random forests (RF) and feature selection (FS) methods.

Details DOI

EWRL Workshop 2018 Workshop Paper

ACCME: Actively Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning

  • Ronnie Stafford
  • John Shawe-Taylor

We present a novel approach for integrating deep non-linear parametric function approximators into an existing reinforcement learning (RL) control algorithm while maintaining stable policy updates. Actively compressed conditional mean embeddings (ACCME) replaces computationally expensive batch kernel regression with a stochastically-trained neural network architecture for learning the kernel weights of a conditional mean embedding (CME) transition model. The embeddings model is then used in a model-based dynamic programming (DP) control algorithm. The ACCME variant i) improves the practicality of continual training of a CME model in online and data-abundant environments, ii) maintains a fast-evaluated contraction constraint by a sparse softmax activation function. Additionally we propose a neurobiologically-inspired mechanism for adding and removing states from the set of successor states that the embedding is defined over. This is in contrast to the original CME and later the compressed CME (CCME) models that only add new states to the set, which is problematic for maintaining non-parametric value functions in large Markov decision processes (MDPs).

PDF Details

NeurIPS Conference 2018 Conference Paper

Empirical Risk Minimization Under Fairness Constraints

  • Michele Donini
  • Luca Oneto
  • Shai Ben-David
  • John Shawe-Taylor
  • Massimiliano Pontil

We address the problem of algorithmic fairness: ensuring that sensitive information does not unfairly influence the outcome of a classifier. We present an approach based on empirical risk minimization, which incorporates a fairness constraint into the learning problem. It encourages the conditional risk of the learned classifier to be approximately constant with respect to the sensitive variable. We derive both risk and fairness bounds that support the statistical consistency of our methodology. We specify our approach to kernel methods and observe that the fairness requirement implies an orthogonality constraint which can be easily added to these methods. We further observe that for linear models the constraint translates into a simple data preprocessing step. Experiments indicate that the method is empirically effective and performs favorably against state-of-the-art approaches.

PDF Details

NeurIPS Conference 2018 Conference Paper

PAC-Bayes bounds for stable algorithms with instance-dependent priors

  • Omar Rivasplata
  • Emilio Parrado-Hernandez
  • John Shawe-Taylor
  • Shiliang Sun
  • Csaba Szepesvari

PAC-Bayes bounds have been proposed to get risk estimates based on a training sample. In this paper the PAC-Bayes approach is combined with stability of the hypothesis learned by a Hilbert space valued algorithm. The PAC-Bayes setting is used with a Gaussian prior centered at the expected output. Thus a novelty of our paper is using priors defined in terms of the data-generating distribution. Our main result estimates the risk of the randomized algorithm in terms of the hypothesis stability coefficients. We also provide a new bound for the SVM classifier, which is compared to other known bounds experimentally. Ours appears to be the first uniform hypothesis stability-based bound that evaluates to non-trivial values.

PDF Details

AAAI Conference 2016 Conference Paper

Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning

  • Guy Lever
  • John Shawe-Taylor
  • Ronnie Stafford
  • Csaba Szepesvari

We present a model-based approach to solving Markov decision processes (MDPs) in which the system dynamics are learned using conditional mean embeddings (CMEs). This class of methods comes with strong performance guarantees, and enables planning to be performed in an induced finite (pseudo-)MDP, which approximates the MDP, but can be solved exactly using dynamic programming. Two drawbacks of existing methods exist: firstly, the size of the induced finite (pseudo-)MDP scales quadratically with the amount of data used to learn the model, costing much memory and time when planning with the learned model; secondly, learning the CME itself using powerful kernel least-squares is costly – a second computational bottleneck. We present an algorithm which maintains a rich kernelized CME model class, but solves both problems: firstly we demonstrate that the loss function for the CME model suggests a principled approach to compressing the induced (pseudo-)MDP, leading to faster planning, while maintaining guarantees; secondly we propose to learn the CME model itself using fast sparse-greedy kernel regression well-suited to the RL context. We demonstrate superior performance to existing methods in this class of modelbased approaches on a range of MDPs.

PDF Details

YNIMG Journal 2015 Journal Article

Sparse network-based models for patient classification using fMRI

  • Maria J. Rosa
  • Liana Portugal
  • Tim Hahn
  • Andreas J. Fallgatter
  • Marta I. Garrido
  • John Shawe-Taylor
  • Janaina Mourao-Miranda

Pattern recognition applied to whole-brain neuroimaging data, such as functional Magnetic Resonance Imaging (fMRI), has proved successful at discriminating psychiatric patients from healthy participants. However, predictive patterns obtained from whole-brain voxel-based features are difficult to interpret in terms of the underlying neurobiology. Many psychiatric disorders, such as depression and schizophrenia, are thought to be brain connectivity disorders. Therefore, pattern recognition based on network models might provide deeper insights and potentially more powerful predictions than whole-brain voxel-based approaches. Here, we build a novel sparse network-based discriminative modeling framework, based on Gaussian graphical models and L1-norm regularized linear Support Vector Machines (SVM). In addition, the proposed framework is optimized in terms of both predictive power and reproducibility/stability of the patterns. Our approach aims to provide better pattern interpretation than voxel-based whole-brain approaches by yielding stable brain connectivity patterns that underlie discriminative changes in brain function between the groups. We illustrate our technique by classifying patients with major depressive disorder (MDD) and healthy participants, in two (event- and block-related) fMRI datasets acquired while participants performed a gender discrimination and emotional task, respectively, during the visualization of emotional valent faces.

Details DOI

NeurIPS Conference 2014 Conference Paper

Multilabel Structured Output Learning with Random Spanning Trees of Max-Margin Markov Networks

  • Mario Marchand
  • Hongyu Su
  • Emilie Morvant
  • Juho Rousu
  • John Shawe-Taylor

We show that the usual score function for conditional Markov networks can be written as the expectation over the scores of their spanning trees. We also show that a small random sample of these output trees can attain a significant fraction of the margin obtained by the complete graph and we provide conditions under which we can perform tractable inference. The experimental results confirm that practical learning is scalable to realistic datasets using this approach.

PDF Details

ICML Conference 2013 Conference Paper

Smooth Operators

  • Steffen Grünewälder
  • Arthur Gretton
  • John Shawe-Taylor

We develop a generic approach to form smooth versions of basic mathematical operations like multiplication, composition, change of measure, and conditional expectation, among others. Operations which result in functions outside the reproducing kernel Hilbert space (such as the product of two RKHS functions) are approximated via a natural cost function, such that the solution is guaranteed to be in the targeted RKHS. This approximation problem is reduced to a regression problem using an adjoint trick, and solved in a vector-valued RKHS, consisting of continuous, linear, smooth operators which map from an input, real-valued RKHS to the desired target RKHS. Important constraints, such as an almost everywhere positive density, can be enforced or approximated naturally in this framework, using convex constraints on the operators. Finally, smooth operators can be composed to accomplish more complex machine learning tasks, such as the sum rule and kernelized approximate Bayesian inference, where state-of-the-art convergence rates are obtained.

Details

TCS Journal 2013 Journal Article

Tighter PAC-Bayes bounds through distribution-dependent priors

  • Guy Lever
  • François Laviolette
  • John Shawe-Taylor

We further develop the idea that the PAC-Bayes prior can be informed by the data-generating distribution. We use this framework to prove sharp risk bounds for stochastic exponential weights algorithms, and develop insights into controlling function class complexity in this method. In particular we consider controlling capacity with respect to the unknown geometry defined by the data-generating distribution. We also use the method to obtain new bounds for RKHS regularization schemes such as SVMs.

Details DOI

JMLR Journal 2012 Journal Article

PAC-Bayes Bounds with Data Dependent Priors

  • Emilio Parrado-Hernández
  • Amiran Ambroladze
  • John Shawe-Taylor
  • Shiliang Sun

This paper presents the prior PAC-Bayes bound and explores its capabilities as a tool to provide tight predictions of SVMs' generalization. The computation of the bound involves estimating a prior of the distribution of classifiers from the available data, and then manipulating this prior in the usual PAC-Bayes generalization bound. We explore two alternatives: to learn the prior from a separate data set, or to consider an expectation prior that does not need this separate data set. The prior PAC-Bayes bound motivates two SVM-like classification algorithms, prior SVM and η -prior SVM, whose regularization term pushes towards the minimization of the prior PAC-Bayes bound. The experimental work illustrates that the new bounds can be significantly tighter than the original PAC-Bayes bound when applied to SVMs, and among them the combination of the prior PAC-Bayes bound and the prior SVM algorithm gives the tightest bound. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

PDF Details

UAI Conference 2012 Conference Paper

PAC-Bayesian Inequalities for Martingales

  • Yevgeny Seldin
  • François Laviolette
  • Nicolò Cesa-Bianchi
  • John Shawe-Taylor
  • Peter Auer

We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. Our results extend the PAC-Bayesian analysis in learning theory from the i.i.d. setting to martingales opening the way for its application in reinforcement learning and other interactive learning domains, as well as many other domains in probability theory and statistics, where martingales are encountered. We also present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the [0, 1] interval by the expectation of the same function of independent Bernoulli variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma’s inequality.

Details

JMLR Journal 2011 Journal Article

Introduction to the Special Topic on Grammar Induction, Representation of Language and Language Learning

  • Dorota Głowacka
  • John Shawe-Taylor
  • Alex Clark
  • Colin de la Higuera
  • Mark Johnson

Grammar induction refers to the process of learning grammars and languages from data; this finds a variety of applications in syntactic pattern recognition, the modeling of natural language acquisition, data mining and machine translation. This special topic contains several papers presenting some of recent developments in the area of grammar induction and language learning, as applied to various problems in Natural Language Processing, including supervised and unsupervised parsing and statistical machine translation. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

PDF Details

YNIMG Journal 2011 Journal Article

Neural prediction of higher-order auditory sequence statistics

  • Nicholas Furl
  • Sukhbinder Kumar
  • Kai Alter
  • Simon Durrant
  • John Shawe-Taylor
  • Timothy D. Griffiths

During auditory perception, we are required to abstract information from complex temporal sequences such as those in music and speech. Here, we investigated how higher-order statistics modulate the neural responses to sound sequences, hypothesizing that these modulations are associated with higher levels of the peri-Sylvian auditory hierarchy. We devised second-order Markov sequences of pure tones with uniform first-order transition probabilities. Participants learned to discriminate these sequences from random ones. Magnetoencephalography was used to identify evoked fields in which second-order transition probabilities were encoded. We show that improbable tones evoked heightened neural responses after 200ms post-tone onset during exposure at the learning stage or around 150ms during the subsequent test stage, originating near the right temporoparietal junction. These signal changes reflected higher-order statistical learning, which can contribute to the perception of natural sounds with hierarchical structures. We propose that our results reflect hierarchical predictive representations, which can contribute to the experiences of speech and music.

Details DOI

NeurIPS Conference 2011 Conference Paper

PAC-Bayesian Analysis of Contextual Bandits

  • Yevgeny Seldin
  • Peter Auer
  • John Shawe-Taylor
  • Ronald Ortner
  • François Laviolette

We derive an instantaneous (per-round) data-dependent regret bound for stochastic multiarmed bandits with side information (also known as contextual bandits). The scaling of our regret bound with the number of states (contexts) $N$ goes as $\sqrt{N I_{\rho_t}(S; A)}$, where $I_{\rho_t}(S; A)$ is the mutual information between states and actions (the side information) used by the algorithm at round $t$. If the algorithm uses all the side information, the regret bound scales as $\sqrt{N \ln K}$, where $K$ is the number of actions (arms). However, if the side information $I_{\rho_t}(S; A)$ is not fully used, the regret bound is significantly tighter. In the extreme case, when $I_{\rho_t}(S; A) = 0$, the dependence on the number of states reduces from linear to logarithmic. Our analysis allows to provide the algorithm large amount of side information, let the algorithm to decide which side information is relevant for the task, and penalize the algorithm only for the side information that it is using de facto. We also present an algorithm for multiarmed bandits with side information with computational complexity that is a linear in the number of actions.

PDF Details

YNIMG Journal 2011 Journal Article

Patient classification as an outlier detection problem: An application of the One-Class Support Vector Machine

  • Janaina Mourão-Miranda
  • David R. Hardoon
  • Tim Hahn
  • Andre F. Marquand
  • Steve C.R. Williams
  • John Shawe-Taylor
  • Michael Brammer

Pattern recognition approaches, such as the Support Vector Machine (SVM), have been successfully used to classify groups of individuals based on their patterns of brain activity or structure. However these approaches focus on finding group differences and are not applicable to situations where one is interested in accessing deviations from a specific class or population. In the present work we propose an application of the one-class SVM (OC-SVM) to investigate if patterns of fMRI response to sad facial expressions in depressed patients would be classified as outliers in relation to patterns of healthy control subjects. We defined features based on whole brain voxels and anatomical regions. In both cases we found a significant correlation between the OC-SVM predictions and the patients' Hamilton Rating Scale for Depression (HRSD), i. e. the more depressed the patients were the more of an outlier they were. In addition the OC-SVM split the patient groups into two subgroups whose membership was associated with future response to treatment. When applied to region-based features the OC-SVM classified 52% of patients as outliers. However among the patients classified as outliers 70% did not respond to treatment and among those classified as non-outliers 89% responded to treatment. In addition 89% of the healthy controls were classified as non-outliers.

Details DOI

JMLR Journal 2010 Journal Article

Sparse Semi-supervised Learning Using Conjugate Functions

  • Shiliang Sun
  • John Shawe-Taylor

In this paper, we propose a general framework for sparse semi-supervised learning, which concerns using a small portion of unlabeled data and a few labeled data to represent target functions and thus has the merit of accelerating function evaluations when predicting the output of a new example. This framework makes use of Fenchel-Legendre conjugates to rewrite a convex insensitive loss involving a regularization with unlabeled data, and is applicable to a family of semi-supervised learning methods such as multi-view co-regularized least squares and single-view Laplacian support vector machines (SVMs). As an instantiation of this framework, we propose sparse multi-view SVMs which use a squared ε-insensitive loss. The resultant optimization is an inf-sup problem and the optimal solutions have arguably saddle-point properties. We present a globally optimal iterative algorithm to optimize the problem. We give the margin bound on the generalization error of the sparse multi-view SVMs, and derive the empirical Rademacher complexity for the induced function class. Experiments on artificial and real-world data show their effectiveness. We further give a sequential training approach to show their possibility and potential for uses in large-scale problems and provide encouraging experimental results indicating the efficacy of the margin bound and empirical Rademacher complexity on characterizing the roles of unlabeled data for semi-supervised learning. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

PDF Details

NeurIPS Conference 2008 Conference Paper

Theory of matching pursuit

  • Zakria Hussain
  • John Shawe-Taylor

We analyse matching pursuit for kernel principal components analysis by proving that the sparse subspace it produces is a sample compression scheme. We show that this bound is tighter than the KPCA bound of Shawe-Taylor et al swck-05 and highly predictive of the size of the subspace needed to capture most of the variance in the data. We analyse a second matching pursuit algorithm called kernel matching pursuit (KMP) which does not correspond to a sample compression scheme. However, we give a novel bound that views the choice of subspace of the KMP algorithm as a compression scheme and hence provide a VC bound to upper bound its future loss. Finally we describe how the same bound can be applied to other matching pursuit related algorithms.

PDF Details

TCS Journal 2007 Journal Article

Complexity of pattern classes and the Lipschitz property

  • Amiran Ambroladze
  • Emilio Parrado-Hernández
  • John Shawe-Taylor

Rademacher and Gaussian complexities are successfully used in learning theory for measuring the capacity of the class of functions to be learnt. One of the most important properties for these complexities is their Lipschitz property: a composition of a class of functions with a fixed Lipschitz function may increase its complexity by at most twice the Lipschitz constant. The proof of this property is non-trivial (in contrast to the case for the other properties) and it is believed that the proof in the Gaussian case is conceptually more difficult than the one for the Rademacher case. In this paper we give a detailed proof of the Lipschitz property for the general case of a symmetric complexity measure that includes the Rademacher and Gaussian complexities as special cases. We also consider the Rademacher complexity of a function class consisting of all the Lipschitz functions with a given Lipschitz constant. We show that the complexity of the class is surprisingly low in the one-dimensional case. Finally, we introduce a relaxation of the definition of Rademacher complexity to Rademacher Free Complexity and show that not only can this complexity replace the standard definition in the key theorem, but also the bounds for composed function classes are tighter.

Details DOI

JMLR Journal 2007 Journal Article

Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data

  • Zakria Hussain
  • François Laviolette
  • Mario Marchand
  • John Shawe-Taylor
  • Spencer Charles Brubaker
  • Matthew D. Mullin

Marchand and Shawe-Taylor (2002) have proposed a loss bound for the set covering machine that has the property to depend on the observed fraction of positive examples and on what the classifier achieves on the positive training examples. We show that this loss bound is incorrect. We then propose a loss bound, valid for any sample-compression learning algorithm (including the set covering machine), that depends on the observed fraction of positive examples and on what the classifier achieves on them. We also compare numerically the loss bound proposed in this paper with the incorrect bound, the original SCM bound and a recently proposed loss bound of Marchand and Sokolova (2005) (which does not depend on the observed fraction of positive examples) and show that the latter loss bounds can be substantially larger than the new bound in the presence of imbalanced misclassifications. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

PDF Details

YNIMG Journal 2007 Journal Article

Unsupervised analysis of fMRI data using kernel canonical correlation

  • David R. Hardoon
  • Janaina Mourão-Miranda
  • Michael Brammer
  • John Shawe-Taylor

We introduce a new unsupervised fMRI analysis method based on kernel canonical correlation analysis which differs from the class of supervised learning methods (e. g. , the support vector machine) that are increasingly being employed in fMRI data analysis. Whereas SVM associates properties of the imaging data with simple specific categorical labels (e. g. , −1, 1 indicating experimental conditions 1 and 2), KCCA replaces these simple labels with a label vector for each stimulus containing details of the features of that stimulus. We have compared KCCA and SVM analyses of an fMRI data set involving responses to emotionally salient stimuli. This involved first training the algorithm (SVM, KCCA) on a subset of fMRI data and the corresponding labels/label vectors (of pleasant and unpleasant), then testing the algorithms on data withheld from the original training phase. The classification accuracies of SVM and KCCA proved to be very similar. However, the most important result arising form this study is the KCCA is able to extract some regions that SVM also identifies as the most important in task discrimination and these are located manly in the visual cortex. The results of the KCCA were achieved blind to the categorical task labels. Instead, the stimulus category is effectively derived from the vector of image features.

Details DOI

NeurIPS Conference 2007 Conference Paper

Variational Inference for Diffusion Processes

  • Cédric Archambeau
  • Manfred Opper
  • Yuan Shen
  • Dan Cornford
  • John Shawe-Taylor

Diffusion processes are a family of continuous-time continuous-state stochastic processes that are in general only partially observed. The joint estimation of the forcing parameters and the system noise (volatility) in these dynamical systems is a crucial, but non-trivial task, especially when the system is nonlinear and multi-modal. We propose a variational treatment of diffusion processes, which allows us to estimate these parameters by simple gradient techniques and which is computationally less demanding than most MCMC approaches. Furthermore, our parameter inference scheme does not break down when the time step gets smaller, unlike most current approaches. Finally, we show how a cheap estimate of the posterior over the parameters can be constructed based on the variational free energy.

PDF Details

JMLR Journal 2006 Journal Article

Kernel-Based Learning of Hierarchical Multilabel Classification Models

  • Juho Rousu
  • Craig Saunders
  • Sandor Szedmak
  • John Shawe-Taylor

We present a kernel-based algorithm for hierarchical text classification where the documents are allowed to belong to more than one category at a time. The classification model is a variant of the Maximum Margin Markov Network framework, where the classification hierarchy is represented as a Markov tree equipped with an exponential family defined on the edges. We present an efficient optimization algorithm based on incremental conditional gradient ascent in single-example subspaces spanned by the marginal dual variables. The optimization is facilitated with a dynamic programming based algorithm that computes best update directions in the feasible set. Experiments show that the algorithm can feasibly optimize training sets of thousands of examples and classification hierarchies consisting of hundreds of nodes. Training of the full hierarchical model is as efficient as training independent SVM-light classifiers for each node. The algorithm's predictive accuracy was found to be competitive with other recently introduced hierarchical multi-category or multilabel classification learning algorithms. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

PDF Details

NeurIPS Conference 2006 Conference Paper

Tighter PAC-Bayes Bounds

  • Amiran Ambroladze
  • Emilio Parrado-Hernández
  • John Shawe-Taylor

This paper proposes a PAC-Bayes bound to measure the performance of Support Vector Machine (SVM) classifiers. The bound is based on learning a prior over the distribution of classifiers with a part of the training samples. Experimental work shows that this bound is tighter than the original PAC-Bayes, resulting in an enhancement of the predictive capabilities of the PAC-Bayes bound. In addition, it is shown that the use of this bound as a means to estimate the hyperparameters of the classifier compares favourably with cross validation in terms of accuracy of the model, while saving a lot of computational burden.

PDF Details

JMLR Journal 2005 Journal Article

Efficient Computation of Gapped Substring Kernels on Large Alphabets

  • Juho Rousu
  • John Shawe-Taylor

We present a sparse dynamic programming algorithm that, given two strings s and t, a gap penalty λ, and an integer p, computes the value of the gap-weighted length- p subsequences kernel. The algorithm works in time O ( p | M | log | t |), where M = {( i,j ) | s i = t j } is the set of matches of characters in the two sequences. The algorithm is easily adapted to handle bounded length subsequences and different gap-penalty schemes, including penalizing by the total length of gaps and the number of gaps as well as incorporating character-specific match/gap penalties. The new algorithm is empirically evaluated against a full dynamic programming approach and a trie-based algorithm both on synthetic and newswire article data. Based on the experiments, the full dynamic programming approach is the fastest on short strings, and on long strings if the alphabet is small. On large alphabets, the new sparse dynamic programming algorithm is the most efficient. On medium-sized alphabets the trie-based approach is best if the maximum number of allowed gaps is strongly restricted. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

PDF Details

NeurIPS Conference 2005 Conference Paper

Two view learning: SVM-2K, Theory and Practice

  • Jason Farquhar
  • David Hardoon
  • Hongying Meng
  • John Shawe-Taylor
  • Sándor Szedmák

Kernel methods make it relatively easy to define complex highdimensional feature spaces. This raises the question of how we can identify the relevant subspaces for a particular learning task. When two views of the same phenomenon are available kernel Canonical Correlation Analysis (KCCA) has been shown to be an effective preprocessing step that can improve the performance of classification algorithms such as the Support Vector Machine (SVM). This paper takes this observation to its logical conclusion and proposes a method that combines this two stage learning (KCCA followed by SVM) into a single optimisation termed SVM-2K. We present both experimental and theoretical analysis of the approach showing encouraging results and insights.

PDF Details

NeurIPS Conference 2003 Conference Paper

Semi-Definite Programming by Perceptron Learning

  • Thore Graepel
  • Ralf Herbrich
  • Andriy Kharechko
  • John Shawe-Taylor

We present a modified version of the perceptron learning algorithm (PLA) which solves semidefinite programs (SDPs) in polynomial time. The algorithm is based on the following three observations: (i) Semidefinite programs are linear programs with infinitely many (linear) constraints; (ii) every linear program can be solved by a sequence of constraint satisfaction problems with linear constraints; (iii) in general, the perceptron learning algorithm solves a constraint satisfaction problem with linear constraints in finitely many updates. Combining the PLA with a probabilistic rescaling algorithm (which, on average, increases the size of the feasable region) results in a prob- abilistic algorithm for solving SDPs that runs in polynomial time. We present preliminary results which demonstrate that the algo- rithm works, but is not competitive with state-of-the-art interior point methods.

PDF Details

NeurIPS Conference 2002 Conference Paper

Inferring a Semantic Representation of Text via Cross-Language Correlation Analysis

  • Alexei Vinokourov
  • Nello Cristianini
  • John Shawe-Taylor

The problem of learning a semantic representation of a text document from data is addressed, in the situation where a corpus of unlabeled paired documents is available, each pair being formed by a short En- glish document and its French translation. This representation can then be used for any retrieval, categorization or clustering task, both in a stan- dard and in a cross-lingual setting. By using kernel functions, in this case simple bag-of-words inner products, each part of the corpus is mapped to a high-dimensional space. The correlations between the two spaces are then learnt by using kernel Canonical Correlation Analysis. A set of directions is found in the first and in the second space that are max- imally correlated. Since we assume the two representations are com- pletely independent apart from the semantic content, any correlation be- tween them should reflect some semantic similarity. Certain patterns of English words that relate to a specific meaning should correlate with cer- tain patterns of French words corresponding to the same meaning, across the corpus. Using the semantic representation obtained in this way we first demonstrate that the correlations detected between the two versions of the corpus are significantly higher than random, and hence that a rep- resentation based on such features does capture statistical patterns that should reflect semantic information. Then we use such representation both in cross-language and in single-language retrieval tasks, observing performance that is consistently and significantly superior to LSI on the same data.

PDF Details

NeurIPS Conference 2002 Conference Paper

Learning Semantic Similarity

  • Jaz Kandola
  • Nello Cristianini
  • John Shawe-Taylor

The standard representation of text documents as bags of words suffers from well known limitations, mostly due to its inability to exploit semantic similarity between terms. Attempts to incorpo(cid: 173) rate some notion of term similarity include latent semantic index(cid: 173) ing [8], the use of semantic networks [9], and probabilistic methods [5]. In this paper we propose two methods for inferring such sim(cid: 173) ilarity from a corpus. The first one defines word-similarity based on document-similarity and viceversa, giving rise to a system of equations whose equilibrium point we use to obtain a semantic similarity measure. The second method models semantic relations by means of a diffusion process on a graph defined by lexicon and co-occurrence information. Both approaches produce valid kernel functions parametrised by a real number. The paper shows how the alignment measure can be used to successfully perform model selection over this parameter. Combined with the use of support vector machines we obtain positive results.

PDF Details

NeurIPS Conference 2002 Conference Paper

String Kernels, Fisher Kernels and Finite State Automata

  • Craig Saunders
  • Alexei Vinokourov
  • John Shawe-Taylor

In this paper we show how the generation of documents can be thought of as a k-stage Markov process, which leads to a Fisher ker(cid: 173) nel from which the n-gram and string kernels can be re-constructed. The Fisher kernel view gives a more flexible insight into the string kernel and suggests how it can be parametrised in a way that re(cid: 173) flects the statistics of the training corpus. Furthermore, the prob(cid: 173) abilistic modelling approach suggests extending the Markov pro(cid: 173) cess to consider sub-sequences of varying length, rather than the standard fixed-length approach used in the string kernel. We give a procedure for determining which sub-sequences are informative features and hence generate a Finite State Machine model, which can again be used to obtain a Fisher kernel. By adjusting the parametrisation we can also influence the weighting received by the features. In this way we are able to obtain a logarithmic weighting in a Fisher kernel. Finally, experiments are reported comparing the different kernels using the standard Bag of Words kernel as a baseline.

PDF Details

JMLR Journal 2002 Journal Article

Text Classification using String Kernels

  • Huma Lodhi
  • Craig Saunders
  • John Shawe-Taylor
  • Nello Cristianini
  • Chris Watkins

We propose a novel approach for categorizing text documents based on the use of a special kernel. The kernel is an inner product in the feature space generated by all subsequences of length k. A subsequence is any ordered sequence of k characters occurring in the text though not necessarily contiguously. The subsequences are weighted by an exponentially decaying factor of their full length in the text, hence emphasising those occurrences that are close to contiguous. A direct computation of this feature vector would involve a prohibitive amount of computation even for modest values of k, since the dimension of the feature space grows exponentially with k. The paper describes how despite this fact the inner product can be efficiently evaluated by a dynamic programming technique. Experimental comparisons of the performance of the kernel compared with a standard word feature space kernel (Joachims, 1998) show positive results on modestly sized datasets. The case of contiguous subsequences is also considered for comparison with the subsequences kernel with different decay factors. For larger documents and datasets the paper introduces an approximation technique that is shown to deliver good approximations efficiently for large datasets.

PDF Details

NeurIPS Conference 2002 Conference Paper

The Decision List Machine

  • Marina Sokolova
  • Mario Marchand
  • Nathalie Japkowicz
  • John Shawe-Taylor

We introduce a new learning algorithm for decision lists to allow features that are constructed from the data and to allow a trade- ofi between accuracy and complexity. We bound its generalization error in terms of the number of errors and the size of the classifler it flnds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine.

PDF Details

JMLR Journal 2002 Journal Article

The Set Covering Machine

  • Mario Marchand
  • John Shawe-Taylor

We extend the classical algorithms of Valiant and Haussler for learning compact conjunctions and disjunctions of Boolean attributes to allow features that are constructed from the data and to allow a trade-off between accuracy and complexity. The result is a general-purpose learning machine, suitable for practical learning tasks, that we call the set covering machine. We present a version of the set covering machine that uses data-dependent balls for its set of features and compare its performance with the support vector machine. By extending a technique pioneered by Littlestone and Warmuth, we bound its generalization error as a function of the amount of data compression it achieves during training. In experiments with real-world learning tasks, the bound is shown to be extremely tight and to provide an effective guide for model selection.

PDF Details

NeurIPS Conference 2002 Conference Paper

The Stability of Kernel Principal Components Analysis and its Relation to the Process Eigenspectrum

  • Christopher Williams
  • John Shawe-Taylor

In this paper we analyze the relationships between the eigenvalues of the m x m Gram matrix K for a kernel k(·, .) corresponding to a sample Xl, .. ., Xm drawn from a density p(x) and the eigenvalues of the corresponding continuous eigenproblem. We bound the dif(cid: 173) ferences between the two spectra and provide a performance bound on kernel peA.

PDF Details

NeurIPS Conference 2001 Conference Paper

On Kernel-Target Alignment

  • Nello Cristianini
  • John Shawe-Taylor
  • André Elisseeff
  • Jaz Kandola

We introduce the notion of kernel-alignment, a measure of similar(cid: 173) ity between two kernel functions or between a kernel and a target function. This quantity captures the degree of agreement between a kernel and a given learning task, and has very natural interpre(cid: 173) tations in machine learning, leading also to simple algorithms for model selection and learning. We analyse its theoretical properties, proving that it is sharply concentrated around its expected value, and we discuss its relation with other standard measures of per(cid: 173) formance. Finally we describe some of the algorithms that can be obtained within this framework, giving experimental results show(cid: 173) ing that adapting the kernel to improve alignment on the labelled data significantly increases the alignment on the test set, giving improved classification accuracy. Hence, the approach provides a principled method of performing transduction. Keywords: Kernels, alignment, eigenvectors, eigenvalues, transduction

PDF Details

NeurIPS Conference 2001 Conference Paper

On the Concentration of Spectral Properties

  • John Shawe-Taylor
  • Nello Cristianini
  • Jaz Kandola

We consider the problem of measuring the eigenvalues of a ran(cid: 173) domly drawn sample of points. We show that these values can be reliably estimated as can the sum of the tail of eigenvalues. Fur(cid: 173) thermore, the residuals when data is projected into a subspace is shown to be reliably estimated on a random sample. Experiments are presented that confirm the theoretical results.

PDF Details

NeurIPS Conference 2001 Conference Paper

Spectral Kernel Methods for Clustering

  • Nello Cristianini
  • John Shawe-Taylor
  • Jaz Kandola

In this paper we introduce new algorithms for unsupervised learn(cid: 173) ing based on the use of a kernel matrix. All the information re(cid: 173) quired by such algorithms is contained in the eigenvectors of the matrix or of closely related matrices. We use two different but re(cid: 173) lated cost functions, the Alignment and the 'cut cost'. The first one is discussed in a companion paper [3], the second one is based on graph theoretic concepts. Both functions measure the level of clustering of a labeled dataset, or the correlation between data clus(cid: 173) ters and labels. We state the problem of unsupervised learning as assigning labels so as to optimize these cost functions. We show how the optimal solution can be approximated by slightly relaxing the corresponding optimization problem, and how this corresponds to using eigenvector information. The resulting simple algorithms are tested on real world data with positive results.

PDF Details

NeurIPS Conference 2000 Conference Paper

Text Classification using String Kernels

  • Huma Lodhi
  • John Shawe-Taylor
  • Nello Cristianini
  • Christopher Watkins

We introduce a novel kernel for comparing two text documents. The kernel is an inner product in the feature space consisting of all subsequences of length k. A subsequence is any ordered se(cid: 173) quence of k characters occurring in the text though not necessarily contiguously. The subsequences are weighted by an exponentially decaying factor of their full length in the text, hence emphasising those occurrences which are close to contiguous. A direct compu(cid: 173) tation of this feature vector would involve a prohibitive amount of computation even for modest values of k, since the dimension of the feature space grows exponentially with k. The paper describes how despite this fact the inner product can be efficiently evaluated by a dynamic programming technique. A preliminary experimental comparison of the performance of the kernel compared with a stan(cid: 173) dard word feature space kernel results. [6] is made showing encouraging

PDF Details

NeurIPS Conference 1999 Conference Paper

Large Margin DAGs for Multiclass Classification

  • John Platt
  • Nello Cristianini
  • John Shawe-Taylor

We present a new learning architecture: the Decision Directed Acyclic Graph (DDAG), which is used to combine many two-class classifiers into a multiclass classifier. For an N -class problem, the DDAG con(cid: 173) tains N(N - 1)/2 classifiers, one for each pair of classes. We present a VC analysis of the case when the node classifiers are hyperplanes; the re(cid: 173) sulting bound on the test error depends on N and on the margin achieved at the nodes, but not on the dimension of the space. This motivates an algorithm, DAGSVM, which operates in a kernel-induced feature space and uses two-class maximal margin hyperplanes at each decision-node of the DDAG. The DAGSVM is substantially faster to train and evalu(cid: 173) ate than either the standard algorithm or Max Wins, while maintaining comparable accuracy to both of these algorithms.

PDF Details

NeurIPS Conference 1999 Conference Paper

Support Vector Method for Novelty Detection

  • Bernhard Schölkopf
  • Robert Williamson
  • Alex Smola
  • John Shawe-Taylor
  • John Platt

Suppose you are given some dataset drawn from an underlying probabil(cid: 173) ity distribution P and you want to estimate a "simple" subset S of input space such that the probability that a test point drawn from P lies outside of S equals some a priori specified l/ between 0 and 1. We propose a method to approach this problem by trying to estimate a function f which is positive on S and negative on the complement. The functional form of f is given by a kernel expansion in terms of a poten(cid: 173) tially small subset of the training data; it is regularized by controlling the length of the weight vector in an associated feature space. We provide a theoretical analysis of the statistical performance of our algorithm. The algorithm is a natural extension of the support vector algorithm to the case of unlabelled data.

PDF Details

NeurIPS Conference 1999 Conference Paper

The Entropy Regularization Information Criterion

  • Alex Smola
  • John Shawe-Taylor
  • Bernhard Schölkopf
  • Robert Williamson

Effective methods of capacity control via uniform convergence bounds for function expansions have been largely limited to Support Vector ma(cid: 173) chines, where good bounds are obtainable by the entropy number ap(cid: 173) proach. We extend these methods to systems with expansions in terms of arbitrary (parametrized) basis functions and a wide range of regulariza(cid: 173) tion methods covering the whole range of general linear additive models. This is achieved by a data dependent analysis of the eigenvalues of the corresponding design matrix.

PDF Details

NeurIPS Conference 1998 Conference Paper

Dynamically Adapting Kernels in Support Vector Machines

  • Nello Cristianini
  • Colin Campbell
  • John Shawe-Taylor

The kernel-parameter is one of the few tunable parameters in Sup(cid: 173) port Vector machines, controlling the complexity of the resulting hypothesis. Its choice amounts to model selection and its value is usually found by means of a validation set. We present an algo(cid: 173) rithm which can automatically perform model selection with little additional computational cost and with no need of a validation set. In this procedure model selection and learning are not separate, but kernels are dynamically adjusted during the learning process to find the kernel parameter which provides the best possible upper bound on the generalisation error. Theoretical results motivating the approach and experimental results confirming its validity are presented.

PDF Details

NeurIPS Conference 1998 Conference Paper

Optimizing Classifers for Imbalanced Training Sets

  • Grigoris Karakoulas
  • John Shawe-Taylor

Following recent results [9, 8] showing the importance of the fat(cid: 173) shattering dimension in explaining the beneficial effect of a large margin on generalization performance, the current paper investi(cid: 173) gates the implications of these results for the case of imbalanced datasets and develops two approaches to setting the threshold. The approaches are incorporated into ThetaBoost, a boosting al(cid: 173) gorithm for dealing with unequal loss functions. The performance of ThetaBoost and the two approaches are tested experimentally. Keywords: Computational Learning Theory, Generalization, fat-shattering, large margin, pac estimates, unequal loss, imbalanced datasets

PDF Details

NeurIPS Conference 1997 Conference Paper

Data-Dependent Structural Risk Minimization for Perceptron Decision Trees

  • John Shawe-Taylor
  • Nello Cristianini

A novel neural network model of pre-attention processing in visual(cid: 173) search tasks is presented. Using displays of line orientations taken from Wolfe's experiments [1992], we study the hypothesis that the distinction between parallel versus serial processes arises from the availability of global information in the internal representations of the visual scene. The model operates in two phases. First, the visual displays are compressed via principal-component-analysis. Second, the compressed data is processed by a target detector mod(cid: 173) ule in order to identify the existence of a target in the display. Our main finding is that targets in displays which were found exper(cid: 173) imentally to be processed in parallel can be detected by the sys(cid: 173) tem, while targets in experimentally-serial displays cannot. This fundamental difference is explained via variance analysis of the compressed representations, providing a numerical criterion distin(cid: 173) guishing parallel from serial displays. Our model yields a mapping of response-time slopes that is similar to Duncan and Humphreys's "search surface" [1989], providing an explicit formulation of their intuitive notion of feature similarity. It presents a neural realiza(cid: 173) tion of the processing that may underlie the classical metaphorical explanations of visual search. On Parallel versus Serial Processing: A Computational Study a/Visual Search

PDF Details

NeurIPS Conference 1995 Conference Paper

Generalisation of A Class of Continuous Neural Networks

  • John Shawe-Taylor
  • Jieyu Zhao

We propose a way of using boolean circuits to perform real valued computation in a way that naturally extends their boolean func(cid: 173) tionality. The functionality of multiple fan in threshold gates in this model is shown to mimic that of a hardware implementation of continuous Neural Networks. A Vapnik-Chervonenkis dimension and sample size analysis for the systems is performed giving best known sample sizes for a real valued Neural Network. Experimen(cid: 173) tal results confirm the conclusion that the sample sizes required for the networks are significantly smaller than for sigmoidal networks.

PDF Details

TCS Journal 1992 Journal Article

An approximate string-matching algorithm

  • Jong Yong Kim
  • John Shawe-Taylor

An approximate string-matching algorithm is described based on earlier attribute-matching algorithms. The algorithm involves building a trie from the text string which takes time O(N log2 N), for a text string of length N. Once this data structure has been built any number of approximate searches can be made for pattern strings of length m. The expected complexity analysis is given for the look-up phase of the algorithm based on certain regularity assumptions about the background language. The expected look-up time for each pattern is O(m log2 N). The ideas employed in the algorithm have been shown effective in practice before, but have not previously received any theoretical analysis.

Details DOI

NeurIPS Conference 1991 Conference Paper

Threshold Network Learning in the Presence of Equivalences

  • John Shawe-Taylor

This paper applies the theory of Probably Approximately Correct (PAC) learning to multiple output feedforward threshold networks in which the weights conform to certain equivalences. It is shown that the sample size for reliable learning can be bounded above by a formula similar to that required for single output networks with no equivalences. The best previ(cid: 173) ously obtained bounds are improved for all cases.

PDF Details
v2026.09.13