------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Kai Shen My research interests span the areas of operating systems, distributed/networked systems, and fault-tolerant computing. I have a number of possible research problems for the 400 project. Please speak to me for specific details. Below is a specific example of a possible 400 project: "virtual machine support for data recovery". A modern OS often employs delayed writes in file cache to improve performance. Dirty data is kept in memory for quick later references. The OS periodically flushes the dirty data to disk to ensure data persistence. However, the dirty data in memory is vulnerable to power outages and system crashes. An uninterrupted power supply (UPS) can keep system running sufficiently long to safely shutdown in the event of a power outage. It is a more difficult problem to deal with file cache data loss due to OS crashes (assume to follow the fail stop model). In particular, dirty data and metadata changes need to be recovered from the crashed OS. Chen et al. [ASPLOS 1996] proposed an OS-level approach that protects and recovers the file cache upon machine crashes. However, this approach increases the OS complexity and it might fail if the crashed OS interferes with the recovery process. Here we describe a possible approach of virtual machine support for data recovery. While the target system runs within a virtual machine, the underlying virtual machine monitor keeps track of the two-way mappings between memory pages and corresponding disk locations. When the target system crashes, the virtual machine monitor then flushes dirty data in the crashing system's file cache into corresponding storage locations. Your task in this 400 project is to explores the feasibility of virtual machine support for data recovery upon system crashes. A successful project includes the partial construction of a prototype that can demonstrate certain aspect of such data recovery. A discovery and experimental validation of some major challenge in this approach is also considered a successful project. ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Henry Kautz 400 Project idea: Build a system that recognizes human behavior from sensor data using a hidden Markov model (HMM). Data could come from one or more of the following sources: (1) The MIT PlaceLab public data sets: http://architecture.mit.edu/house_n/data/PlaceLab/PlaceLab.htm (2) Data you help collect in our own Laboratory for Assisted Cognition Environment. (3) Data you collect in your own office by instrumenting your own desktop or laptop computer. References for this project include: S. S. Intille, K. Larson, E. Munguia Tapia, J. Beaudin, P. Kaushik, J. Nawyn, and R. Rockinson, "Using a live-in laboratory for ubiquitous computing research," in Proceedings of PERVASIVE 2006, vol. LNCS 3968, K. P. Fishkin, B. Schiele, P. Nixon, and A. Quigley, Eds. Berlin Heidelberg: Springer-Verlag, 2006, pp. 349-365. http://web.media.mit.edu/~intille/papers-files/IntilleETAL06.pdf Fine-Grained Activity Recognition by Aggregating Abstract Object Usage. Donald Patterson, Dieter Fox, Henry Kautz, Matthai Philipose. Proceedings of the IEEE International Symposium on Wearable Computers, Osaka, Japan, Oct. 2005. http://www.cs.rochester.edu/u/kautz/papers/djp3-iswc-2005.pdf ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Some possible CSC 400 projects - Len Schubert On any of these, I'd be happy to say more (in person or email) and to provide guidance. In some cases, Fabrizio and/or Benjamin can help as well. 1. Engineering some basic lexical and world knowledge axioms ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ to enable some "obvious" forward inferencing. (E.g., John's car broke down, therefore it isn't working, therefore he can't drive it, therefore he can't use it to get around; and he'll want to get it repaired and he's probably unhappy about the break-down, etc.) This would probably involve becoming acquainted with the EPILOG KR&R system. Fabrizio Morbini is an expert on the functioning (and malfunctioning) of that system, and would happily advise on it. (So would I, though he knows the nitty-gritty better than I do.) EPILOG is an experimental system based on the premise that internal representations of verbalizable knowledge in an intelligent system should themselves be "natural language-like", with the same kinds of expressive devices that are available in all natural languages (such as generalized quantifiers, uncertainty, event representations, mental attitudes, predicate & sentence modifiers, and predicate & sentence reification operators). EPILOG also employs "specialist" reasoners that use analog representations for time, part-structure, color space, etc., to obtain improved inference efficiency. Fabrizio's own current work is concerned with improving EPILOG, and developing a capability for self-awareness in an EPILOG-based system called Epi2me ("epitome") that knows what it knows, what it can and can't do, what its own nature and history are, what the current dialog situation and recent dialog events are, etc. The demo exists in a very rudimentary form, but to make it more interesting a lot of general knowledge will be required. As mentioned, the general knowledge will be of roughly 2 kinds; a. Lexical knowledge; e.g., - if X (physically) goes from Y to Z in episode E, then X is at Y at the start of E and at Z at the end of E; - if X converses with Y then Y converses with X - every (physical) "going" is an action by some animate agent and it is from some place to some other place; - every person is an animate agent; every book contains textual material and possibly pictures/diagrams; everything that is (constituted of) gold is metallic stuff; etc. b. Basic world knowledge; e.g., - if an object is unsupported it will fall to the ground; - if you turn on a faucet, water will (probably) flow out; - a car in working order can be driven by a person from one place to another (connected by roadways), much faster than a person could walk or run from one to the other; - a hungry predator encountering a nonpredatory animal smaller than itself is apt to attack and try to eat it; - if X asks Y a question, X probably wants Y to tell X the answer to the question, and Y will normally answer, if able to do so; - a person with normal sensory capacities and in a normal state of alertness will notice conspicuous actions or events happening within plain sight or earshot of him or her; - people try to avoid getting hurt, or having their possessions taken away or damaged, or being prevented from doing what they wish to do; etc. A good deal of type-(a) knowledge can probably by imported from the basic knowledge engineering efforts by Bruce Porter at U. Texas (Austin). FrameNet is another potentially useful source. Also a good deal of hierarchy knowledge could be obtained from WordNet (which we have locally available) or other sources. Some type-(b) knowledge may be available from miscellaneous sources: OpenCyc, MindNet, the work by J. Hobbs and his collaborators on "commonsense psychology", and our own local work on knowledge mining from text (the KNEXT system). But there's also a definite, inescapable need for hand-coding of such knowledge, at least in the short run. The "payoff" and validation of such a project would be in demonstrating forward inferences performed by EPILOG in response to given input, of the sort that humans would consider immediate and obvious conclusions from what they are told. Examples similar to the car break-down are: If I tell you about a hungry wolf encountering a rabbit, this evokes the expectation that the wolf may try to attack and eat it; if I ask you a question, you normally infer that I want you to tell me the answer (if you can), and this imposes an obligation on you; if I tell you that my cat died, you will probably infer that the cat is dead, can no longer be my pet, and that I am sad about the loss; etc. Epi2me should be able to make similar inferences. A variant ~~~~~~~~~ A somewhat differently focused variant of this idea would be to study examples from the "Pascal Recognizing Textual Entailment Challenge" (RTE, e.g., see http://www.pascal-network.org/Challenges/RTE2/ and http://www.pascal-network.org/Challenges/RTE3), and engineer the knowledge needed to recognize the entailments. This would again involve coding lexical and world knowledge, and would be useful for getting a feel for the kinds of knowledge that seem to be required for seeing entailment relations. A putative example of such a relation is that "Israel's Ariel Sharon became prime minister in 2001" entails that "Sharon is Israel's prime minister" (though the inference would now more properly be "...WAS Israel's prime minister"!) 2. Quasi-probabilities: This is a project for someone who enjoys math ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ and logic. ~~~~~~~~~~ Background: ~~~~~~~~~~ I have partially worked out a "quasiprobability (QP) logic" that collapses logical inference and probabilistic inference into a single symbolic algebraic system. For example, a conjunction like (phi/\psi) can be viewed simultaneously as a logical formula, and as a symbolic probability -- the probability of that conjunction being true. From the latter perspective, phi and psi are themselves (quasi)probabilities, and '/\' is a product operator. Now, it may seem incorrect to suppose that the probability of a conjunction is the product of probabilities of the conjuncts; we are accustomed to thinking this is true only for *independent* conjuncts. Well, it turns out that as long as probabilities are in their symbolic, QP form, and as long as "product" is understood in a certain sense somewhat different from ordinary arithmetic product, the claim holds not just for independent conjuncts, but for all conjuncts. In particular, the product operator in the QP algebra is *idempotent*. To take an extreme example, the conjunction of phi with itself, (phi/\phi) (which has the strongest possible "interdependence" of the two conjuncts, namely identity) viewed as a quasiprobability product is just phi. (Idempotency means that any element of the algebra multiplied by itself gives back that element.) Another example would be the inconsistent formula (phi/\~phi), where again the two conjuncts are as strongly "interdependent" as possible (one is the negation of the other). Now, the algebraic representation of negation is as subtraction from 1; i.e., we have (phi/\(1-phi)). This can be "multiplied out" to (phi/\1)-(phi/\phi) = phi - phi = 0 (which is falsity). Or, we could just have said directly that in the QP algebra, the product of a probability term with its negation is 0. Often when thinking of logical expressions as QPs we use '*' (weak product) rather than '/\' for conjunction. For example, we write (p*q*r)*(q*r*s) = p*q*r*s = pqrs. Universal quantification can be expressed as an extended product, and given that we have ways to express conjunction, negation and universal quantification, we have the tools to do anything that can be done in first-order predicate calculus; however, we have more, because we can also compute probabilities of formulas in an uncertain world (or probability bounds, or comparative probabilities -- whatever is implied by the numerical bounds or other relationships we have for our quasiprobabilities). Ultimately, the idea in QP logic is that the world can be modelled by a set of independent, "elementary" random variables that influence the various properties and relationships we care about. Their influence is exerted either as "random conjuncts" in logical conjunctions or as random "inhibitors" that tend to prevent certain propositions from being true. Another way of putting it is that they exert their influence on the world through randomized AND gates and randomized NOT gates. There are strong connections of this approach to work that has been done by David Poole on "independent choice logic" (within a Prolog framework), and perhaps to Pedro Domingos' combination of "Markov networks" with probabilities, though in the latter case the exact connections remain unclear. (However, he deals strictly in numerical rather than symbolic probabilities, and thus cannot symbolically manipulate or bound or compare probabilities.) So far, the QP algebra has been fully worked out only for Bayesian networks, but they provide an interesting new perspective, and new computational methods for such networks. There is an "Uncertainty in AI" (UAI 2004 -- available from my web page) paper on this, and a nearly complete detailed TR. It turns out that we can easily map any Bayesian network into a network with noisy logic gates (where noisy AND and NOT are in principle sufficient). We can then do Bayesian network computations by assigning marginal (symbolic) QPs to all nodes (which can be done in polynomial time), and then computing arbitrary conditional probabilities as ratios of joint probabilities -- which is the usual method EXCEPT that we now obtain joint (quasi)probabilities just by (idempotent) products of appropriate node marginals. Getting from symbolic conditional probabilities to numerical ones still remains intractable in the worst case (as is inevitable unless P = NP), *but* the products turn out to be easily reducible in all cases where special solution methods have been employed in the past -- e.g., for polytrees. In a sense the exploitation of special structural features of networks is an automatic byproduct of the symbolic manipulation of QPs. Project (i) ~~~~~~~~~~~ The greatest computational promise of QPs in the case of Bayesian networks lies in their potential for allowing systematic "small probability" approximations. The symbolic form of quasiprobabilities allows us to successively bound the contributions of various subterms, and the errors in setting relatively small probabilities to 0. (In Bayesian networks, e.g., for medical diagnosis, many probabilities are typically very small.) This potential has not yet been exploited, and is one of the most promising projects that could be undertaken. A "difficult" realistic Bayesian network called QMR (Quick Medical Reference) is available on which such approximation methods could be tried. Project (ii) ~~~~~~~~~~~~ Another possible project, also applicable to Bayesian networks but of potentially broader general significance, is "effective expansion and reduction" of QP expressions, to minimize as far as possible the computational effort required to derive numerical probabilities from QPs. A set of operations for these expansions/reductions has been defined, and the question is how to apply these operations most effectively. Preliminary work was done by an undergraduate (Dave Sloan) to implement the basic transformations, but not in an optimal ordering. A good solution appears to require graph-theoretic algorithms, e.g., breaking a graph representing a QP expression into two components with minimal connections between the components. Other possibilities ~~~~~~~~~~~~~~~~~~~ Quasi-probabilities also have other potential applications, such as a new method of SAT-solving (an example is given in the incomplete TR). Another undergrad (Tom Weingarten) has also implemented Bayesian network calculations based on QPs, using the fact that QPs can be implemented very directly as pulse trains in a neural-net-like architecture. (This was published as an undergraduate research conference paper, at NCUR 2005.) However, the method so far only works for small Bayesian networks, because the length of pulse trains required for accurate calculations grows exponentially with the size of networks. It will take new ideas, perhaps some method based on representing logarithms of QPs rather than QPs directly as pulse trains, to obtain more practical performance, but the connection to neural nets is a tantalizing one. 3. Reasoning by "miscellaneous" example generation: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ It's possible to do at least approximate deduction, probabilistic inference, and generalization from examples by generating miscellaneous instances of general axioms and "observing" the consequences. I've tried it out on some examples, and it might be fun to implement, and to compare with more formal methods. The idea is attractive inasmuch as a lot of human reasoning seems to be of this sort (e.g., the psychologist Philip Johnson-Laird has studied the apparent dependence of much reasoning on "mental models" that are constructed as-needed; also the most effective theorem-proving methods of recent years have been model generation/elimination methods, and these seem related to reasoning by example generation. They can be thought of as exploring specific instances of general axioms in a systematic way, to see whether or not a model of the axioms exists. If yes, then the axioms have been proved to be consistent, and if not, an inconsistency has been found, providing a proof by contradiction.) An example I tried is this: given that - If a movie is funny, some viewers like it. - If a movie has a bad ending, no viewer likes it. Conclusion: If a movie has a bad ending, it isn't funny. I used a graphical method that creates a separate sample set for each concept referred to (movies, funny things, viewers, having a bad ending), and equality links for identical elements (e.g., if we want an instance of a funny movie, draw an equality link from a movie-instance to a funny-instance), and labeled edges for relations (e.g., an edge from a viewer to a movie s/he likes). For each axiom, we generate some instances, and then check whether the conclusion holds; we might further try to construct a counterexample, and if we fail, draw our conclusion with greater confidence. One interesting question is whether (and under what assumptions) we can generate examples in such a way that when we "read off" a conclusion, we can have full confidence in that conclusion. (Again, this is surely related to model generation/elimination methods.) One attractive aspect of the approach is that it seems generalizable to vague or uncertain knowledge. For instance, suppose we are given that most students in a certain class passed the final exam, and all students who passed the final exam also passed the course. Then we can conclude that most students passed the course (it's easy to see how to do this reasoning in the above "graphical" way, say, using 3 instances of students). Furthermore, we should be able to conclude rather easily that for a given student in the class, given no other information, it is *likely* that the student passed the exam, and the course. One can also see how to incorporate approximate cardinality information. For example, suppose we know that the class in question has 100 students. Then we should be able to conclude something about the number of students that passed, and the number that *may* have failed. Model-based reasoning has a long history, going back to H. Gelernter, "Empirical explorations of the geometry theorem-proving machine", and "Realization of a geometry theorem-proving machine", in Feigenbaum and Feldman, Computers and Thought, pages 153 -- 63, 134 -- 52. McGraw Hill, 1963. I have made a quick google check for recent literature, but "example generation" seemed to yield mostly papers on program verification by example generation (not a totally unrelated topic, but not what I was looking for). Probably more relevant references could be located by checking papers that reference Gelernter. But I don't know what has been done, if anything, on the sort of "rough and ready" example generation approach, yielding somewhat but not totally reliable conclusions (as opposed to systematic exploration of the space of models) that I am suggesting. Note that example generation can also lead to general hypotheses. For example, in the "unfunny movies" example, even if we're not given the conclusion to be proved, we may still reach that conclusion (that movies with bad endings aren't funny) by observing relationships between sets of generated examples (e.g., equality links from all elements of one set to elements of another). Of course, in a sense this just provides another way to do forward (input-driven) inference, but perhaps this has some advantages such as ease of computation, and/or generalizability to vague and probabilistic knowledge. Example generation might also serve to generate hypotheses to be subsequently confirmed (or rejected) by more formal reasoning methods (or more thorough model exploration). 4. Designing (and perhaps beginning implementation of) a "reason ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ maintenance" mechanism in EPILOG. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This would be quite a challenging project, because it would require close study of the EPILOG system. (However, Fabrizio and I would be there to help.) "Reason maintenance" means keeping a record of how conclusions accepted by EPILOG, based on direct input, linguistic input, or inference, were reached. For example, EPILOG might conclude for a particular dog, say Fido, that it is probably friendly, based on a general axiom that most dogs are friendly, and a proposition that Fido is a dog. So a reason maintenance system would record this "provenance", e.g., using pointers to the two premises used to reach the conclusion. These premises might again point to their own justifications, which might for instance be that a certain user *told* the system that Fido is a dog, etc. The claim that Fido is a dog might not be accepted with 100% confidence, if there is some doubt about the veracity of the user, in the context in which the information was supplied. When we keep track in this way of reasons for reaching conclusions, we may also be able to update the knowledge base in a somewhat reasonable way. For example, if new information is supplied by a user that Fido is a pit bull terrier, and EPILOG already has the belief (rightly or wrongly -- apologies to pit bull enthusiasts!) that pit bull terriers are mostly nasty, then assuming that EPILOG also recognizes (by forward inference) the conflict between being friendly and being nasty, it might examine its reasons for having thought that Fido is probably friendly, and compare this with the new reasons for thinking that Fido is nasty, and decide that the reasons based on the more specific category of Fido (pit bull) wins over the reason based on more general information (dog). There is a connection here to project (2) (quasiprobabilities): Since quasiprobabilities (QPs) are symbolic probabilities that directly derive from (indeed, *are*) logical formulas, the "provenance" (derivational history) of a given conclusion provides a way of computing its marginal QP, and new information can easily be accommodated by multiplication of marginals (using the idempotent "weak product" operator). Under certain assumptions on how QPs are cast in terms of elementary QPs (independent random variables), the conclusion that the "pit bull"-based conclusion about Fido "wins" over the conclusion based on his being a dog would fall out of the QP algebra. In this way, reason maintenance becomes maintenance of links that support updating of marginal QPs of all propositions in the KB. (HOWEVER, much remains to be learned about QPs in a general logical setting to implement these ideas in a general way.) There is a substantial literature on reason maintenance and "truth maintenance" (essentially the same notion, but not allowing for degrees of certainty). One author who comes to mind is Jon Doyle; probably most papers in the reason maintenance area reference his work. There are no papers relating reason maintenance to quasiprobabilities. 5. Analogical/prototype inference in EPILOG ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ It is a striking feature of human cognition that we can make analogical inferences based on a single example. To see this in a context that is relatively unbiased by familiar world knowledge, consider the following outlandish example: You are exploring a distant planet and encounter a beach-ball-sized, silvery, globular entity floating two feet off the ground; it splits open, releasing a smaller blue globe that drifts two feet upward, and bursts, spattering blue droplets over you; these produce no apparent ill effect, but you are disconcerted, and hastily depart the scene -- but minutes later you encounter a beach-ball-sized, silvery, globular entity floating two feet off the ground; it splits open, releasing a smaller red globe ... We have definite expectations about what is likely to come next, just based on the one previous event sequence. More mundane examples would be the way a child might learn properties of common types of objects in the world. For instance, the first time the child encounters a dog, if the word "dog" (or "doggie", or whatever) is applied to the animal by someone, the child will immediately associate multiple properties with that concept, as observed in that one instance; say, general shape and 4-leggedness, furriness, friendliness, the prominent tongue and teeth, manner and speed of motion, sniffing behavior, responsiveness to petting, barking, etc. If the next dog encountered by the child is at first seen only vaguely (say in the distance, or a head poking up in the back of a car), the child will nonetheless "fill in" whatever was learned from the original instance, expecting the body to be furry, four-legged, etc., and the behavior to be similar. (Or so I suppose!) One way of looking at such examples of "one-shot" learning by example is to suppose that we simply match new instances to ones we already have encountered and represented in some way (presumably picking out "prominent" features). Having matched some aspects of a new exemplar to those of one or more previous ones, we "expect" the remaining features to be instantiated as well. This is the perspective taken by researchers at Northwestern University (Ken Forbus, Chris Riesbeck, et al.) in their "Learning Reader" project (and previously "MAC/FAC"). However, the more examples we see, the more burdensome the process of making analogies with previous instances (of many sorts!) becomes, so one might reasonably suppose that we very quickly form a "prototype" that abstracts from specific examples, and we modify that prototype, or split it into multiple prototypes (or in some other way allow for alternatives) when a single prototype cannot be kept consistent with the examples, or becomes too ambiguous or unspecific. From an EPILOG perspective, a "prototype" would be a set of uncertain generalizations abstracted from one or more examples. For instance, given some anatomical and behavioral features of a particular dog, we might form general hypotheses such as that a dog *generally* (not only in the instance at hand) is 4-legged, furry, friendly, eager for food, likes company, and so on. Features not found on subsequent examples would be dropped or at least made less probable. Note that in this process of generalization, statements such as that Fido has legs L1, L2, L3, and L4 become something like "For virtually any dog, there *exist* (distinct) legs x1, x2, x3, x4 that are part of the dog". So we have a mix of generic and existential quantification. The existential quantification could be Skolemized (as is common in resolution theorem proving), and the Skolem functions thus obtained could be viewed as representing "roles" or "slots", as in a frame-like representations. (Forbus & co. do some such abstracting, but in a way that leaves unclear just what their prototypes mean; they do not use anything like a generic quantifier.) A major puzzle in all this is on what basis we can pick certain kinds of features as probably being generally present, while others (let's say, particular details of the pattern of body fur, or particular motion sequences) seem incidental and not generalizable. This applies as much to constellations of events as to constellations of parts and other features of some object. The Learning Reader project at NU in fact has focused primarily on terrorist incidents, making use of the assumption that patterns of events tend to repeat themselves. James Allen et al.'s PLOW project can also be viewed as resting on assumptions like "when you've seen one way of (e.g.) purchasing a book via the web, you've seen them all", and this enables one-shot learning. Early work in concept formation, by Patrick Winston at MIT, is relevant here, though he assumed that in addition to examples of a concept, the learner was supplied with "near misses" (exemplars that were "nearly" instances of the concept, but differed in some crucial way), and these are not generally available (or, seemingly, needed; though perhaps something like a cat could be viewed as a "near miss" of a dog...) Two random refs on analogy: Dedre Gentner and Kenneth Kurtz, "Relations, objects, and the composition of analogies", Cognitive Science 30, 2006, 609-642. Peter D. Turney, "Similarity of semantic relations", Computational Linguistics 32(3), Sep. 2--6, 379-416. A related theme: summary inference ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A related theme, also of great importance in human learning and reasoning (and mostly neglected, as far as I can tell) is "summary inference". For example, we can summarize a shopping expedition as "I went to three clothing stores and a supermarket, and brought home a new pair of shoes and some essential groceries". Question: *Where* do these propositions come from? They are certainly not inferences in any ordinary KR&R sense as understood in AI. Rather they are abstractions from a welter of detail. In the same way we come up with "statistical" summaries such as "More students were admitted from foreign countries than from the U.S.", or qualitative ones like "You've had a rough day", after someone tells of their car not starting in the morning, getting mugged at the bus stop, and being fired from their job". This sort of inference shares with analogical reasoning and protoype reasoning that it is based on abstraction from specific instances of things and events, finding commonalities among them (a kind of analogy-making?), and using these to construct more abstract, more comprehensive representations. To my knowledge, almost no work has been done in this area. (I do recall a paper by Gordon McCalla long ago on forming summary statements based on information in databases -- which of course can be viewed as collections of basic facts). The remaining 3 ideas are just briefly indicated, to be elaborated if anyone requests it. 6. Invariant discovery in modifiable domains ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is a version of the "scientific/mathematical discovery" problem: how can we discover the "laws" or invariants of a given domain? The recent PhD work by Proshanto Mukherji was along these lines, but it was concerned with static invariants, i.e., properties that hold *at all times* in a modifiable domain, such as a STRIPS-like planning domain. What I have in mind here is discovery of action invariants, i.e., what is unchanged by a sequence of actions, or more generally, what the effects are of certain action sequences (or event sequences brought about by external agencies, not under the control of the theorizer). E.g., consider manipulating list structure. When we move the first item to last place, and repeat this, then after n moves, where n is the length of the list, we obtain the original state. On the other hand, if we pop elements from one list and push them onto another, we end up with the reverse of the list; if we reverse twice, we get back the original list; etc. 7. Siphoning Cyc knowledge into EPILOG ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Work in this direction has already been undertaken by Fabrizio Morbini, in the hope of initializing the EPILOG KB with a significant amount of world knowledge. However, much of the knowledge in Cyc is expressed in a very idiosyncratic vocabulary whose connections to language are often obscure (e.g., EverydayLifeAnthropacity, AmbientConditionsMt, HumanlyOccupiedSpatialObject, etc.) But in other cases the connection is clear (e.g., RoadVehicle, Motorcycle, TransportingPeople, Weapon, etc). The goal would be to use a lexicon (such as WordNet) to select propositions from Cyc that involve mostly (or only) concepts that are easily identified with lexical entries, or are in a small set of concepts used throughout Cyc, such as "isa", "genls", "disjointWith", etc., or certain role-words derived from English words, such as "Transportees", "driverActor", etc. It seems that we should be able to extract many thousands of ordinary facts such as that an automobile is a road vehicle, that it serves for transporting people, that it is controlled by a driver, etc. 8. Devising "incoherency filters" for the KNEXT knowledge extraction system ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ KNEXT (see my web page) has been used to extract millions of simple propositions from the British National Corpus (BNC -- a large collection of miscellaneous texts). But many of these are incoherent because of parser and interpreter failures. Though a variety of filters are already being applied, much more could be done to "clean up" the outputs, and this would be very beneficial for subsequent use of these propositions (in parsing or in a KB). ------------------------------------------------------------------------------ ------------------------------------------------------------------------------