Presentations• Logistics– Think about what you want to do– Thursday we’ll informally sign up, see if we can reach consensus.• Topics– Linear representations of classes– Non-linear representations of classes– Psychology of view-based recognition– Descriptors– Neuroscience– Skeletons– Constellation methods– HMMs– Adaboost– Others???How do Categories Work?Philosophy, Cognitive Science• What can we learn from them?– Problem Definition• What is a category? • What phenomena do people display when they categorize?– Ideas for algorithms• Representations, how they affect learnability• What will be relevant to vision engineers?– May be willing to focus on simple categories– May be less interested in odd exceptions– But may want to mimic human categorization when we build systems that interact with people.Philosophy and Categories• Categories are central to key questions in philosophy.– How do we know things.• Example, Plato’s theory of knowledge– What do statements mean.• Example: statements should be reducible to logic, with primitives verifiable by senses.• How then can we express categories with logic?• WittgensteinBasic Questions• What is a category? (class, concept)– A set of objects/things? What sets are valid?– A probability distribution?• What determines what belongs to a category?– With a category comes the ability to judge in principle whether new things are part of it. How does this work?– Are categories in the world or in our head?• How do we determine categories computationally?– How do we represent and use prior knowledge?– How do we cope with partial information? ….Visual Categories• Papers don’t talk much about specifically visual, but we want to consider this.• Only some categories do we expect to perceive visually.– Yes: Red.• This is nothing but visual.– Probably yes: Chair, desk, maple.• Structure is important to what they are.– Maybe: Measles.• Vision is diagnostic, but not integral to what it is.– Very tough: game, convince.Visual Categories• We don’t ask: “Is this a chair?”, we ask: “Does this look like a chair?”• Viewing conditions (eg., pose, lighting) affect an object’s appearance.The Papers• Women, Fire and Dangerous Things by Lakoff, Chapters 1 and 2.• S. Laurence and E. Margolis, ``Concepts and Cognitive Science'', in Concepts edited by E. Margolis and S. Laurence, MIT Press.• L. Wittgenstein, Philosophical Investigations, sections 65-78.What do we need to account for?• Representational adequacy• Categorization• Acquisition• Compositionality• Internal Structure– Prototype effects• Analytic inference (important for vision?)• Stability (important for vision?)Our plan• Focus on two chief approaches• First, classical theory• Discuss prototype effects• Prototype theoryWe’ll focus first on:• Classical theory – a category is definable. – Certain properties are present or absent. Example: a chair has a seat. A briefcase has a handle.– Eventually, these bottom-out in something verifiable by senses.– Category membership is binary.– Intuitive: we think things have definitions.– Held with little question for ~2,000 years.– Initial focus of AI, cognitive science: eg., Schank, Hayes, expert systems, anthropology.Representational power? (Plato’s problem).• Precise definitions are actually quite difficult.– Wittgenstein’s example game started this. “Don’t think but look”. – Knowledge as justified true belief.• The story of the tennis match.– Paint• X covers Y with paint (exploding paint factory).• Plus x is an agent (I kick over paint bucket).• It’s intentional. (Michaelangelo painting mural).• Intention is to cover with paint (dip brush in paint).– This might be an issue of representational power, or just that definitions are hard to uncover.Question• Do we care about this? Maybe these problems only occur for categories more complex than those we can hope to identify with vision.Question• Even if we can’t always use them, don’t definitions sometimes seem useful? If we want to find soccer games where Sweden beat Norway, Sweden should have scored more goals.Acquisition/Categorization• Seems straightforward• Acquisition: especially easy to hard code these.• Still, issues in finding good algorithms, in choosing best features.Visual Categorization – Are there visual analogs to these?• Visual categories may be simpler(?)• But definitions in terms of visual properties are harder.– Even if I can define a chair as something one person can sit in, this is far from a visual definition. Classical theory assumes ultimately there’s a visual definition, but doesn’t usually try to work it all out.– Even very simple visual properties are hard. Try to define “gray”.Prototype Structure of Classes• Berlin and Kay – focal color stable across cultures.• Rosch – converging evidence of prototypes.– Direct rating: (robin over chicken)– Reaction time:– Production of examples– …Prototypes and Classical view• Mysterious why definitional categories would have prototypes.• Not really a theory, ie., not too specific.• Category is based on statistical occurrence of features• Example of a specific prototype theory: a statistical model based on properties. – Gaussian distribution; – Weighted combination of properties: eg., Bird Properties: flies, sings, lays eggs, is small, nests in trees, eats insects.All are true of a robin, but maybe only some need to be true (eg., a chicken) This could be a linear separator eg., an SVM.• Wittgenstein: Family resemblance, rope.– This could be a manifold representation.Prototype theoryRepresentational power?• Prototype theory– In its vaguest form, has arbitrary power.– In simpler form, more powerful than definitions, but is it powerful enough?– But still faces problem of feature selection, and reducing these to sensory inputs.Categorization/Acquisition• In principle seems do-able• But algorithm must be specified.Prototypes and Prototype Theory• Natural explanations: prototypes are most probable examples (mode of distribution).• But this doesn’t explain all prototypes:– 8 is a better example of an even number than 34.Prototypes and Vision• Prototypes exist in visual terms, (pose).– Often these are most informative (in some sense).– Many algorithms produce prototype effects,