Meta tags:
description=..::A Random Walk::..;

Headings (most frequently used words):

the, to, onionesque, reality, random, on, in, from, learning, via, product, and, mathematics, of, blog, email, recent, blogs, top, posts, subscribe, walk, where, does, sigmoid, logistic, regression, come, note, graph, laplacian, eros, gaia, neighbourhood, gerrymandering, an, approach, discriminative, metric, latent, structured, prediction, jacobian, inner, gradient, outer, implementation, abstraction, evolution, programming, languages, two, notions, information, very, informal, thoughts, no, free, lunch, theorem, stats, visitor, locations, follow, contact, me, comments, pages, archives, twitter, shubhendu, machine, biology, neurobiology, foundations, geek, humor, matlab, movies, digital, art, other, physics, professional, associations, technology, my, del, icio, us, clicks, meta, by, quote, for, week, jump, post,

Text of the page (most frequently used words):
the (543), that (128), and (111), this (100), for (75), #learning (64), are (60), can (39), with (37), point (36), above (36), machine (32), #metric (30), from (29), some (29), gradient (29), one (27), which (27), not (27), points (27), now (24), information (24), set (24), note (23), matrix (23), have (22), there (22), loss (22), but (21), product (20), data (20), problem (20), classification (20), blog (19), kolmogorov (19), about (19), you (19), such (19), knn (19), would (18), function (18), regression (17), complexity (17), any (17), shubhendu (16), also (16), may (16), what (16), similar (16), each (16), linear (16), log (15), graph (15), trivedi (15), theory (15), post (15), more (15), given (15), just (15), following (15), good (15), out (15), vector (15), distance (15), laplacian (14), might (14), thus (14), query (14), structured (13), space (13), was (13), however (13), then (13), class (13), has (13), outer (13), operator (13), defined (13), nearest (13), neighbours (13), how (12), where (12), does (12), simply (12), very (12), using (12), consider (12), these (12), classifier (12), optimization (11), two (11), 2008 (11), 2012 (11), think (11), random (10), 2011 (10), 2013 (10), 2014 (10), posted (10), tagged (10), why (10), since (10), when (10), had (10), definition (10), quantity (10), idea (10), label (10), comments (9), number (9), mathematics (9), ieee (9), here (9), string (9), expected (9), they (9), unknown (9), difference (9), learn (9), same (9), subspace (9), model (9), let (9), want (9), below (9), define (9), correct (9), euclidean (9), risk (9), odds (9), like (8), view (8), onionesque (8), reality (8), free (8), latent (8), prediction (8), logistic (8), science (8), books (8), society (8), convex (8), non (8), map (8), between (8), january (8), august (8), october (8), 2009 (8), 2010 (8), example (8), way (8), most (8), simple (8), only (8), choice (8), diffusion (8), reduction (8), first (8), average (8), suppose (8), neighbors (8), inference (8), minimize (8), com (7), comment (7), sigmoid (7), intelligence (7), image (7), case (7), new (7), lunch (7), nfl (7), over (7), interesting (7), say (7), see (7), used (7), clear (7), time (7), supervised (7), dimensionality (7), usually (7), because (7), edges (7), natural (7), email (6), your (6), inner (6), posts (6), art (6), processing (6), bad (6), matlab (6), machines (6), march (6), april (6), november (6), december (6), will (6), than (6), fixed (6), our (6), makes (6), shannon (6), hence (6), use (6), possible (6), real (6), means (6), relevant (6), infact (6), along (6), error (6), called (6), properties (6), looking (6), valued (6), being (6), classes (6), worst (6), objective (6), examples (6), basically (6), sense (6), ____________________________ (6), conditional (6), get (5), wordpress (5), other (5), jacobian (5), neighbourhood (5), approach (5), via (5), nature (5), computer (5), computational (5), engineering (5), circle (5), system (5), never (5), june (5), september (5), theorem (5), papers (5), reason (5), exist (5), leads (5), particular (5), its (5), distribution (5), different (5), gives (5), better (5), communication (5), while (5), related (5), into (5), another (5), make (5), maps (5), ________________ (5), adjacency (5), approximation (5), sample (5), corresponds (5), direction (5), varies (5), variable (5), binary (5), should (5), previous (5), correspond (5), output (5), native (5), feature (5), similarly (5), figure (5), notion (5), bayes (5), question (5), divergence (5), expression (5), required (4), subscribe (4), much (4), gerrymandering (4), inspired (4), humour (4), mining (4), biology (4), artificial (4), life (4), thoughts (4), edge (4), language (4), etc (4), discussion (4), deep (4), statistics (4), analysis (4), february (4), july (4), evolution (4), been (4), his (4), all (4), found (4), universal (4), structureless (4), algorithms (4), able (4), find (4), done (4), thinking (4), algorithm (4), ofcourse (4), works (4), recently (4), kind (4), purpose (4), selected (4), objects (4), original (4), must (4), course (4), although (4), well (4), again (4), understand (4), local (4), spectral (4), earlier (4), follows (4), variation (4), goal (4), still (4), important (4), dimensional (4), motivation (4), smooth (4), setup (4), easy (4), order (4), were (4), linked (4), training (4), similarity (4), learnt (4), offending (4), mentioned (4), majority (4), vote (4), labels (4), method (4), neighbour (4), optimize (4), illustrated (4), take (4), measure (4), rule (4), many (4), labeled (4), marked (4), basis (4), indexed (4), design (3), write (3), sign (3), feed (3), worth (3), eros (3), gaia (3), recent (3), top (3), regions (3), vision (3), technology (3), quotes (3), physics (3), computing (3), systems (3), communications (3), talks (3), news (3), less (3), wrong (3), jonathan (3), long (3), foundations (3), twitter (3), walk (3), archives (3), projects (3), follow (3), incompleteness (3), thought (3), david (3), concerned (3), particularly (3), search (3), optimal (3), program (3), programming (3), greater (3), short (3), learner (3), argument (3), results (3), sure (3), problems (3), exists (3), depends (3), fails (3), useful (3), seen (3), incorrect (3), least (3), message (3), probability (3), directly (3), messages (3), estimate (3), applications (3), combinatorial (3), fundamental (3), selection (3), paper (3), them (3), version (3), leave (3), type (3), abstraction (3), manuscript (3), main (3), look (3), manifold (3), provided (3), term (3), constructed (3), decomposition (3), semi (3), based (3), work (3), directions (3), recover (3), coordinates (3), stick (3), written (3), motivated (3), before (3), need (3), cases (3), metrics (3), reimannian (3), positive (3), defines (3), thing (3), considered (3), column (3), taking (3), support (3), descent (3), augmented (3), intuitive (3), familiar (3), intuition (3), therefore (3), mahalanobis (3), bit (3), notice (3), parties (3), lmnn (3), around (3), convexity (3), ball (3), closer (3), close (3), give (3), context (3), something (3), age (3), decide (3), classifiers (3), start (3), performance (3), baby (3), book (3), writing (3), vertex (3), finite (3), ratio (3), decision (3), site (2), website (2), collapse (2), subscribed (2), account (2), create (2), discriminative (2), come (2), bbc (2), radio4 (2), reith200 (2), onionesquereality (2), maximum (2), voronoi (2), visual (2), video (2), swarm (2), signal (2), scientists (2), robotics (2), neuroscience (2), game (2), famous (2), cybernetics (2), chemistry (2), scientific (2), american (2), mit (2), reference (2), arxiv (2), business (2), higher (2), optimized (2), carlos (2), blogs (2), evolutionary (2), digital (2), steve (2), central (2), pick (2), week (2), sequences (2), math (2), journal (2), mathematical (2), net (2), foundation (2), brain (2), talking (2), read (2), blogging (2), kernel (2), intelligent (2), geometry (2), library (2), truths (2), profound (2), fact (2), contrast (2), 2015 (2), 2016 (2), zero (2), strangeness (2), minus (2), three (2), richa (2), darwinian (2), dot (2), mail (2), address (2), diagonalization (2), mcallester (2), enough (2), theoretic (2), believe (2), functions (2), assume (2), always (2), upper (2), itself (2), anything (2), stated (2), specific (2), bits (2), compression (2), scheme (2), irrelevant (2), description (2), construct (2), show (2), spirit (2), actual (2), constant (2), axiomatic (2), statement (2), every (2), prior (2), precise (2), fail (2), certain (2), general (2), indeed (2), informal (2), algorithmic (2), individual (2), notions (2), advantage (2), contained (2), novel (2), 1983 (2), semantic (2), chosen (2), 1948 (2), going (2), sharp (2), after (2), obvious (2), reasons (2), languages (2), lisp (2), quick (2), noticed (2), years (2), ideas (2), implementation (2), dimension (2), second (2), values (2), embedding (2), degree (2), estimators (2), estimation (2), shows (2), consistent (2), recovers (2), under (2), rank (2), lemma (2), motivate (2), generalized (2), mapping (2), usual (2), input (2), project (2), involvement (2), across (2), form (2), literature (2), ways (2), made (2), soon (2), otherwise (2), definite (2), associated (2), instead (2), dealing (2), expectation (2), extension (2), regularizer (2), stochastic (2), step (2), efficient (2), best (2), turns (2), gap (2), offenders (2), score (2), intractable (2), remedy (2), surrograte (2), incurred (2), hinge (2), high (2), yet (2), described (2), large (2), sets (2), affects (2), back (2), somewhat (2), terms (2), districts (2), voters (2), ensure (2), farthest (2), deform (2), pulled (2), pushed (2), ranking (2), roweis (2), 2006 (2), optimizing (2), making (2), approaches (2), weinberger (2), semidefinite (2), margin (2), enforced (2), really (2), together (2), radius (2), brief (2), black (2), classified (2), mean (2), their (2), nearness (2), far (2), suboptimal (2), models (2), notes (2), illustrate (2), care (2), freeman (2), dyson (2), begins (2), her (2), world (2), own (2), home (2), whatever (2), piece (2), becomes (2), part (2), larger (2), reading (2), yields (2), value (2), flow (2), discrete (2), incidence (2), orientation (2), arbitrary (2), suffices (2), matrices (2), both (2), div (2), grad (2), once (2), simplest (2), beginning (2), assumptions (2), plug (2), started, name, loading, bar, manage, subscriptions, reader, report, content, privacy, already, join, 147, subscribers, wpthemes, entries, meta, 597, wordpre, nptel, iitm, courses, clicks, arrangement, hyperplanes, portrait, paul, erdős, del, icio, illusions, vintage, lectures, uncategorized, thinkers, innovators, artists, software, philosophy, nanotechnology, memetics, history, fun, photographs, ethics, embedded, darwinism, cosmology, cognitive, bio, medical, aeronautics, wired, ted, review, seed, magazine, reasearch, intel, popular, labnol, amit, agarwal, spectrum, scientist, futility, closet, dark, roasted, blend, man, medicine, acm, professional, associations, frame, cosmic, variance, astronomy, backreaction, metadatta, understanding, ubiwar, education, smart, energy, shtetl, rod, carvalho, rashid, paleoglot, monica, jeans, mixotricha, lids, mahathi, lamentations, kush, varshnay, jkwiens, freelancing, epicurean, dealmaker, gershenson, arabidopsisgirl, vitsly, seventh, lenfirewood, weblog, rosenbaum, generative, chris, marker, movies, seth, simulink, loren, ken, mike, desktop, file, exchange, doug, tutorials, wolfram, mathworld, tim, gowers, squared, online, encyclopedia, category, café, mathpages, travelled, integer, geomblog, terence, tao, planet, nuit, blanche, reflections, lance, fortnow, god, plays, dice, gil, kalai, gödel, lost, letter, lipton, gametheory, chu, carroll, xkcd, phd, comics, brown, sharpie, abstruse, goose, geek, humor, citrus, neurocritic, loom, carl, zimmer, synthetic, novella, psychology, pain, podcast, biocurious, neurobiology, togelius, structuralist, brains, references, spoken, social, media, robots, podcasts, reinforcement, readings, pyevolve, hierarchial, network, nlp, passively, mloss, open, metaoptimize, medal, lingpipe, jorge, tavares, manton, chang, inductio, machina, illigal, icml, hizook, herself, geneura, team, genetic, argonaut, epistasis, epfl, laboratory, developing, datawrangling, bibliography, wonderland, chemoton, vitorino, ramos, research, notebook, fernandes, bayesian, arthur, charpenteir, ars, experientia, alexander, smola, aaai, tweets, _onionesque, trajectory, courtesy, physorg, jump, niels, bohr, favorite, maxims, father, distinction, sorts, recognized, opposite, truth, trivialities, opposites, obviously, absurd, quote, pages, logi, fractal, area, ejournal, final, entr, andrea, lapla, blind, geometers, perception, visio, ofir, gagulashvily, vihan, 1966, film, john, von, neu, yahoo, regarding, copyright, complaints, queries, contact, enter, receive, notifications, visitor, locations, 803, 122, visitors, stats, older, train, calls, appeared, study, including, unrelated, likening, chomsky, grammar, invocation, grounds, enlightening, assumes, generated, process, probably, bound, line, reasoning, naturally, doesn, whether, levin, prove, implies, compress, turing, complete, length, incompressible, structure, appear, encoding, uncomputable, even, bounds, informally, formalized, proven, within, chaitin, instructive, diagnolization, completely, sounds, plausible, light, subtle, absrudity, flaw, corollary, theorems, wolpert, macready, mainstays, crudely, says, giving, handle, tasks, specialization, accidental, justification, incorporate, informaion, hand, perform, oftentimes, argue, theoretically, impossible, possibly, small, thanks, vick, pointing, claude, andrey, mainly, application, usage, computability, equal, entropy, refers, treated, members, probabilistic, convincingly, applied, stream, congratulatory, telegrams, apply, translation, relative, capable, introducing, clarity, principle, calculus, probabilities, reproducing, either, exactly, approximately, frequently, meaning, refer, correlated, according, physical, conceptual, entities, aspects, significant, aspect, designed, operate, actually, through, places, differences, relief, past, decades, quite, nonetheless, nevertheless, paragraphs, nothing, historical, 2000, 80s, 90s, 60s, 70s, 40s, 50s, indicates, conrad, barski, land, list, images, paige, bailey, hilarious, deserved, needless, click, resolution, dynamicwebpaige, couple, ago, taken, graduate, taught, flavour, material, advanced, mention, organized, presentation, polished, presenting, did, certainly, enjoyed, perhaps, audit, consistency, unsupervised, techniques, eigenmaps, interpreted, could, isolate, obtain, borrow, extend, established, tools, interest, neighbor, obtained, powers, settings, sampled, various, involve, derivatives, slope, approximates, repeating, statistically, principal, component, assumed, eigenvectors, corresponding, eigenvalues, true, hard, recovered, vary, null, directional, derivative, fastest, generally, significantly, smaller, achieved, letting, rather, projected, further, linearly, multi, index, down, features, others, discarded, often, behind, nonparametric, came, quadratic, inverse, doing, questions, topic, future, hopefully, saw, vein, eigenvector, highest, dealt, areas, symmetric, smoothly, varying, tangent, tensor, special, suffixed, opposed, estimated, manner, estimating, gradients, working, limitations, restricts, helpful, notation, summarize, outerproduct, extends, embeddings, subtraction, max, concave, procedure, needs, subroutine, determine, finding, presented, frobenius, norm, arrived, arguments, instance, machinery, wanting, increased, stressed, object, penalizes, surrogate, passing, resort, tractable, predicts, predict, respect, interested, predicting, represented, stands, minimizing, sum, involves, key, trivial, choices, prefer, implicit, little, survey, motivations, akin, common, practice, drawing, borders, election, provide, advantages, desired, political, concentrating, party, spreading, cells, diagram, voted, cartoon, requirement, push, irrespective, mcfee, lankriet, takes, treating, induces, permutation, increasing, precision, necessarily, requiring, globerson, attempts, attempting, collapsing, goldberger, hinton, salakhutdinov, 2004, piecewise, replaced, soft, nca, tries, price, losing, components, few, notable, ones, saul, pull, towards, pushing, pure, require, clustered, optimizes, harder, remedied, briefly, earliest, 2002, mapped, separation, moved, xing, jordan, russell, exact, formulation, farther, away, disagree, inspite, classify, combination, proximity, agreement, reduced, rescaling, rotation, distances, family, evident, worthwhile, incorporated, semantically, amplify, informative, squish, incorrectly, correctly, capture, hairstyle, someone, gender, lady, illustration, disadvantages, falls, talked, decided, shortfalls, off, clearly, near, figures, adapted, slides, kilian, moreover, implement, inherently, nonlinear, biggest, opinion, add, retraining, scratch, relatively, robust, noise, attractive, theoretical, universally, infinity, appropriate, digression, moving, excellent, mnist, dataset, competitive, compared, complicated, whose, assign, starting, colours, methods, gaussian, processes, reliance, explained, compare, dissimilar, return, afterall, dissimilarity, summary, mother, forty, she, contrary, fifty, five, published, curled, belly, cannot, born, goes, develops, character, daughter, coming, school, surprises, unexpected, flashes, wisdom, happens, theories, sit, quietly, gestating, nine, months, day, belonging, anymore, whole, community, produce, magic, creation, producing, fully, watch, grow, fits, imagined, belong, company, those, medieval, craftsmen, who, added, carved, stone, scaffolding, built, chartres, cathedral, courage, too, late, afresh, habit, prefaces, glad, sobering, passage, appears, recalling, diagonal, computation, analogy, appropriately, recall, describing, outbound, end, sort, differential, viewed, measures, change, row, vertices, fix, specify, intuitively, suggests, laplace, explicate, operators, behaves, pixel, detect, changes, averaging, twice, differentiable, dimensions, analogue, succinct, gregory, shakhnarovich, took, served, arguably, outputs, field, amongst, favourable, derivation, consequence, modeling, noted, monotonic, rearranging, know, plugging, exponentiating, fallen, accident, remains, option, due, imply, equivalent, saying, absolutely, generalization, sometimes, assuming, middle, chain, next, ask, draw, concretely, mistakes, datapoint, pair, location, boundary, parameters, try, begging, place, modeled, else, front, page, multiple, reshares, uses, article, story, hacker, title, circular, abuse, feeds,

Text of the page (random words):
g the offending points out of this circle thus in a way the goal in lmnn is to deform the metric in such a way that the neighbourhood for each point is pure there are many approaches to the metric learning problem however a few more notable ones are 1 neighbourhood components analysis goldberger roweis hinton and salakhutdinov 2004 here the piecewise constant error of the knn rule is replaced by a soft version this leads to a non convex objective that can be optimized by gradient descent basically nca tries to optimize for the choice of neighbour at the price of losing convexity 2 collapsing classes globerson and roweis 2006 this method attempts to remedy the non convexity above by optimizing a similar stochastic rule while attempting to collapse each class to one point making the problem convex 3 metric learning to rank mcfee and lankriet 2010 this paper takes a different take on metric learning treating it as a ranking problem note that given a fixed p s d matrix a query point induces a permutation on the training set in order of increasing distance the idea thus is to optimize the metric for some ranking measure such as precision k but note that this is not necessarily the same as requiring correct classification neighbourhood gerrymandering as a motivation we can look at the cartoon above for lmnn since we are looking to optimize for the knn objective the requirement to learn the metric should just be correct classification thus we should need to push the points to ensure the same thus we can have the circle around x as simply the distance of the farthest point in the k nearest neighbours irrespective of class now we would like to deform the metric such that enough points are pulled in and pushed out of this circle so as to ensure correct classification this is illustrated below this method is akin to the common practice of gerrymandering in drawing up borders of election districts so as to provide advantages to desired political parties this is done by concentrating voters from a particular party and or by spreading out voters from other parties in the above the districts are cells in the voronoi diagram defined by the mahalanobis metric and parties are class labels voted for by each neighbour motivations and intuition now we can step back a little from the survey above and think a bit about the knn problem in somewhat more precise terms so that the above approach can be motivated better for knn given a query point and a fixed metric there is an implicit latent variable the choice of the k neighbours given this latent variable inference of the label for the query point is trivial since it is just the majority vote but notice that for any given query point there can exist a very large number of choices of k points that may correspond to correct classification basically any set of points with majority of correct class will work now we basically want to learn a metric so that we prefer one of these sets over any set of k neighbours which would vote for a wrong class in particular from the sets that affects correct classification we would like to pick the set that is on average most similar to the query point we can write knn prediction as an inference problem with a structured latent variable being the choice of k neighbours the learning then corresponds to minimizing a sum of structured latent hinge loss and a regularizer computing the latent hinge loss involves loss augmented inference which is basically looking for the worst offending k points points that have high average similarity with the query point yet correspond to a high loss given the combinatorial nature of the problem efficient inference and loss augmented inference is key optimization can basically be just gradient descent on the surrograte loss to make this a bit more clear the setup is described below problem setup suppose we are given training examples that are represented by a native feature map with with class labels with where stands for the set suppose are also provided with a loss matrix with being the loss incurred by predicting when the correct class is we assume that and now let be a set of examples in as stated earlier we are interested in the mahalanobis metrics for a fixed we may define the distance of with respect to a point as therefore the set of k nearest neighbours of in is for any set of examples from we can predict the label of by a simple majority vote the knn classifier therefore predicts thus the classification loss incurred using the set can be defined as learning and inference one might want to learn so as to minimize the training loss however as mentioned in passing above this fails because of the intractable nature of the classification loss thus we d have to resort to the usual remedy define a tractable surrograte loss it must be stressed again that the output of prediction is a structured object the loss in structured prediction penalizes the gap between score of the correct structured output and the score of the worst offending incorrect output this leads to the following definition of the surrogate this corresponds to our earlier intuition on wanting to learn such that the gap between the good neighbours and worst offenders is increased so although the loss above was arrived at by intuitive arguments it turns out that our problem is an instance of a familiar type of problem latent structured prediction and hence the machinery for optimization there can be used here as well the objective for us corresponds to where is the frobenius norm note that the regularizer is convex but the loss is not convex to the subtraction of the max term i e now it is a difference of convex functions which means the concave convex procedure may be used for optimization although we just use stochastic gradient descent also note that the optimization at each step needs an efficient subroutine to determine the correct structured output inference of the best set of neighbours and the worst offending incorrect structured output loss augmented inference i e finding the worst set of neighbors turns out that for this problem this is possible although not presented here it is interesting to think about how this approach extends to regression and to see how it works when the embeddings learnt are not linear posted in machine learning tagged k nearest neighbors machine learning metric learning similarity learning structured prediction structured support vector machines support vector machines 7 comments the jacobian inner product august 20 2014 by shubhendu trivedi this post may be considered an extension of the previous post the setup and notation is the same as in the previous post linked above but to summarize earlier we had an unknown smooth regression function the idea was to estimate at each training point the gradient of this unknown function and then taking the sample expectation of the outerproduct of the gradient this quantity has some interesting properties and applications however it has its limitations for one the mapping restricts the gradient outer product being helpful for only regression and binary classification since for binary classification the problem can be thought of as regression it is not clear if a similar operator can be constructed when one is dealing with classification that is the unknown smooth function is a vector valued function where is the number of classes let us say for the purpose of this discussion that for each data point we have a probability distribution over the classes a dimensional vector in the case of the gradient outer product since we were working with a real valued function it was possible to define the gradient at each point which is simply for a vector valued function we can t have the gradient but instead can define the jacobian at each point note that may be estimated in a similar manner as estimating gradients as in the previous posts which leads us to define the quantity the first thing to note is that defined in the previous post is simply the quantity for the special case when another note is also in order the reason why we suffixed that quantity with outer product as opposed to inner product here is simply because we considered the gradient to be a column vector otherwise they are similar in spirit another thing to note is that it is easy to see that the quantity is a positive semi definite matrix and hence is a reimannian metric which is defined below definition a reimannian metric on a manifold is a symmetric and positive semi definite matrix which defines a smoothly varying inner product in the tangent space for each point and this associated p s d matrix is called the metric tensor in the above case since is p s d it defines a reimannian metric thus is a specific metric more general metrics are dealt with in areas such as metric learning properties we saw some properties of in the previous post in the same vein does have similar properties i e does the first eigenvector also correspond to the direction of highest average variation what about the dimensional subspace what difference does it make that we are looking at a vector valued function also what about the cases when and otherwise these are questions that i need to think about and should be the topic for a future post to be made soon hopefully posted in machine learning tagged classification dimensionality reduction jacobian machine learning manifold learning regression statistics supervised learning 1 comment the gradient outer product august 16 2014 by shubhendu trivedi recently in course of a project that i had some involvement in i came across an interesting quadratic form it is called in the literature as the gradient outer product this operator which has applications in supervised dimensionality reduction inverse regression and metric learning can be motivated in two related ways but before doing so the following is the set up setup suppose we have the usual set up as for nonparametric regression and binary classification i e let for some unknown smooth the input is dimensional 1 supervised dimensionality reduction it is often the case that varies most along only some relevant coordinates this is the main motivation behind variable selection the idea in variable selection is the following that may be written as where projects down the data to only relevant coordinates i e some features are selected by while others are discarded this idea is generalized in multi index regression where the goal is to recover a subspace most relevant to prediction that is now suppose the data varies significantly along all coordinates but it still depends on some subspace of smaller dimensionality this might be achieved by letting from the above to be it is important to note that is not any subspace but rather the dimensional subspace to which if the data is projected the regression error would be the least this idea might be further generalized by means of mapping to some non linearly but for now we only stick to the relevant subspace how can we recover such a subspace ________________ 2 average variation of another way to motivate this quantity is the following suppose we want to find the direction in which varies the most on average or the direction in which varies the second fastest on average and so on or more generally given any direction we want to find the variation of along it how can we recover these ________________ the expected gradient outer product the expected gradient outer product of the unknown classification or regression function is the quantity the expected gradient outer product recovers the average variation of in all directions this can be seen as follows the directional derivative at along is given by or from the above it follows that if does not vary along then must be in the null space of infact it is not hard to show that the relevant subspace as defined earlier can also be recovered from this fact is given in the following lemma lemma under the assumed model i e the gradient outer product matrix is of rank at most let be the eigenvectors of corresponding to the top eigenvalues of then the following is true this means that a spectral decomposition of recovers the relevant subspace also note that the gradient outer product corresponds to a kind of a supervised version of principal component analysis ________________ estimation ofcourse in real settings the function is unknown and we are only given points sampled from it there are various estimators for which usually involve estimation of the derivatives in one of them the idea is to estimate at each point a linear approximation to the slope of this approximation approximates the gradient at that point repeating this at the sample points gives a sample gradient outer product there is some work that shows that some of these estimators are statistically consistent ________________ related gradient based diffusion maps the gradient outer product can not isolate local information or geometry and its spectral decomposition as seen above gives only a linear embedding one way to obtain a non linear dimensionality reduction would be to borrow from and extend the idea of diffusion maps which are well established tools in semi supervised learning the central quantity of interest for diffusion maps is the graph laplacian where is the degree matrix and the adjacency matrix of the nearest neighbor graph constructed on the data points the non linear embedding is obtained by a spectral decomposition of the operator or its powers as above a similar diffusion operator may be constructed by using local gradient information one such possible operator could be note that the first term is the same that is used in unsupervised dimension reduction techniques such as laplacian eigenmaps and diffusion maps the second term can be interpreted as a diffusion on function values this operator gives a way for non linear supervised dimension reduction using gradient information the above operator was defined here however no consistency results for the same are provided also see the jacobian inner product ________________ posted in machine learning tagged classification diffusion maps dimensionality reduction gradient outer product machine learning manifold learning non linear dimensionality reduction regression statistics supervised learning 1 comment implementation and abstraction in mathematics august 13 2014 by shubhendu trivedi i recently noticed on arxiv that the following manuscript implementation and abstraction in mathematics by david mcallester a couple of years ago i had taken a graduate course taught by david that had a similar flavour the material in the manuscript is more advanced in particular the main results not to mention it is better organized and the presentation more polished presenting a type theoretic foundation of mathematics although i can t say i did very well in the course i certainly enjoyed the ideas in it very much and thus the above manuscript might be worth a look per...