|
Author
|
Topic: Suggestions for an AI Project
|
Micah Sparacio
Member
Member # 6
|
posted 04. February 2003 18:06
I'm taking a graduate level course in artificial intelligence and have the chance to develop a major AI project. Not that I'm cheating or anything ![[Wink]](wink.gif) but I'd love to take advantage of the Brainstorms community to get a feel for what type of AI projects are worth doing. I'm looking for hot topics in AI, projects that may shed some light on our discussions at Brainstorms, etc.
Thanks in advance for any ideas you share.
IP: Logged
|
|
gedanken
Member
Member # 594
|
posted 04. February 2003 20:50
Micah, if you will consider a suggestion:
Do a genetic algorithm. You can compare it to other search procedures of "generate and test". What is of interest (at the level of an early grad course in AI) is the basics of search procedures. This would give you a grounding in both the various goal-directed search procedures that are regularly taught, and an insight into what remains the same and what is different in a GA search.
One interesting aspect is the nature of parallel processing that will become more important in AI search into the future. One of the major bottlenecks in AI search procedures on parallel processors is the communication between tasks on separate processors. The GA allows fairly independent processing, as the "individuals" (or partial individuals) that are built can be run on independent processors, with only certain comparison information communicated between processors. This is distinct from many other search modes in which the communication bottleneck can limit the speed and addition of new processors does not speed the search.
I would not suggest using the search procedure (GA) to format an advanced system like a neural network. I would recommend some sort of simple direct structural application that doesn’t in itself turn into another major project. Something like construction of logic equations consisting of and, or, not of 1 or 2 variables, and state storage elements might be relatively simple. Or something that you are familiar with. Thus a simple data structure can be built and simulated for the constructed objects. Something greater would be beyond the time you have for an early grad level AI course (it sound’s like this is not your major, just a course -- correct me if I’m wrong.) A goal can be established of an input-output system that exhibits some behavior, for which a quality measure can be developed. This quality measure must show partial success in achieving the goal. A particularly useful “goal” might be recognition of some time sequence digital pattern.
But you would probably have to discuss this extensively with the professor, as the GA technique may be outside of the area of search that is normally considered in such a course. It would be important to propose it as a comparison with some other search techniques, to ground the project in the subject as taught.
In fact, the overview algorithm could be developed as a “GA” and other “generate and test” all in the same algorithm. The only difference would be the search strategy of the “generate” phase, and some control code that deals with the retention of individuals. A depth first, a breadth first, or a GA could be constructed with the same components, using an object oriented approach for the “test” evaluation and maintenance of individuals, with the “generate” differing between the GA and other procedures.
How much time do you plan to spend?
I don’t quite know what you mean by a “major AI project”. Do you mean a project for your “major”. Or do you mean an extremely large system (because “major AI projects” can involve whole teams and years of work.) Or do you just mean larger than anything you have done before. That’s why I ask how much time.
[ 04. February 2003, 21:39: Message edited by: gedanken ]
IP: Logged
|
|
Rex Kerr
Member
Member # 632
|
posted 04. February 2003 22:12
Simulated annealing has much nicer statistical behavior than genetic algorithms, and from what I've seen rarely produces inferior results. It's a more robust search strategy.
However, I would probably not recommend any traditional maximization algorithm for research into AI. Those approaches have been tried and--while some very powerful tools were develped--failed. There's a lot more core functionality that needs to be built up first, I think.
Then again, I don't think you're going to have enough time to get much of anywhere in "a graduate level course". Quarter, semester, or year? Which institution?
If you just want to do a cool project, if you build some sort of simple motivation/action scheme and a language to describe it, using a genetic algorithm (or simulated annealing) to solve a problem could be a lot of fun.
IP: Logged
|
|
gedanken
Member
Member # 594
|
posted 05. February 2003 01:41
Rex, thanks for the tip. I had not thought of “simulated annealing” in this context. But I should learn more, as it relates to certain techniques that we used in constraints satisfaction searches in a very different type of domain. I’m going to have to study the relation of these to certain “relaxation techniques” that were used for constraint satisfaction problems. The overlap occurs (in my interest, not so relevant to Micah’s problem) when one is simultaneously looking at optimization and complexity/connections/relatioinships in a context of constraint satisfaction.
I had brought up the GA because of its relation to subjects discussed here. (And I want to emphasize again the generic nature of “generate and test” algorithms, under which GA and simulated annealing can be viewed.)
From preliminary browsing, it seems to me that simulated annealing would be subject to the limitations suggested by the IDists under the subject of “TRIZ”. (See “evolving inventions” thread for example.)
I don’t think of the genetic algorithms as being inherently limited in the dimensionality of the search space as is simulated annealing. (See example Aerodynamic Optimization of Turbine Cascades for descriptions of use of SA in a kind of complex non-linear optimization problem with many states.)
PS, I understand that there is an implementation of simulated annealing in “Numerical Recipies” (see link).
Also an interesting link in a context of greater emphasis on combinatorial problems.
My thought was to work on some more “connectionist” (or combinatorial) type of problem, wherein the solutions are more novel because the number of connections explored is growing. (This would have more of a relation to the expansion of the search space offered by gene duplication and the like events.)
A problem with strict GA approaches is that no use is made of the gradient information that is available to make the search more efficient when the problem includes parametric optimization on top of the connectionist issues. It looks like the simulated annealing approach may make some use of such gradient information (I’m not clear at this point). (Note this does not confer a greater capability to SA, simply a faster convergence on solutions.)
[ 05. February 2003, 01:55: Message edited by: gedanken ]
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 05. February 2003 06:39
Hey guys, thanks for the suggestions. Yeah, it is a graduate level course with the emphasis being put on a semester long project of our choosing. So, it is not a multi-year, team project. I think your suggestions are exactly the sort of thing I'm looking for.
BTW, gedanken, GAs are being taught as a search strategy in the class.
[ 05. February 2003, 06:51: Message edited by: Micah Sparacio ]
IP: Logged
|
|
gedanken
Member
Member # 594
|
posted 05. February 2003 13:27
quote:
BTW, gedanken, GAs are being taught as a search strategy in the class.
In that case, angle I was thinking of was the comparison of search operators. In other words the problem to be worked on is kept simple, and the effort is put in demonstrating and comparing various search strategies.
The reason I feel it has a special relevance to the subjects of ISCID, is that there are mathematical comparisons of the search spaces of various algorithms (and of comparing physical processes to such “algorithms”). What I see as important is recognizing the way different search strategies work in the same search space, just having different efficiencies of coming up with particular types of solutions. Note that such “efficiencies” are not merely academic, but rather times of completion to particular findings can range from milliseconds to the life of the universe -- and thus “efficiency” also effects capability. But understanding the relationships of all this is very important. That is why I think the idea is relevant to ISCID subjects.
[ 05. February 2003, 13:27: Message edited by: gedanken ]
IP: Logged
|
|
|
|
RBH
Member
Member # 380
|
posted 05. February 2003 15:01
gedanken wrote quote:
A problem with strict GA approaches is that no use is made of the gradient information that is available to make the search more efficient when the problem includes parametric optimization on top of the connectionist issues. It looks like the simulated annealing approach may make some use of such gradient information (I'm not clear at this point). (Note this does not confer a greater capability to SA, simply a faster convergence on solutions.)
A problem - I guess it's a "problem" - we've encountered using SA in the context of a GA is that it can encourage too rapid convergence. In the kind of situation we face, with fitness landscapes of unknown but undoubtedly complex topography (in the sense of being high-dimensioned with lots of hills and valleys and ridges and wormholes and local optima), it turns out we don't want faster convergence. We want the (large - thousands of artificial organisms) population to meander around, splitting into 'species' and subspecies so we can harvest the several species rather than a single "solution." We're interested in groups and families of related outcomes, not an 'optimal' solution. (Not incidentally, that has been a very difficult position to get across to my principal collaborator, who comes out of an engineering background. He wants to find the solution! And quickly!)
In the "Evolving Inventions" thread I mentioned my view that modeling biological evolution as a search process may be a mistake (or at least can be seriously misleading): quote:
This will sound like heresy to some, but biological evolution is not a search process. As conceived by evolutionary theory, it is a process in which variation and selection (along with the other evolutionary operators) in co-evolving populations (with the attendant dynamically deforming fitness landscapes) produce the appearance of search for optima, but that appearance is deceptive. To be sure, populations find sufficiently high local optima (or perish), but they are not searching for those optima. They find optima as a by-product of the operation of evolutionary operators, not as a goal. Hence analyzing biological evolution as a search problem leads to false analogies with human uses of search algorithms on both sides of the debate. (All emphases original)
I think the analogy with search is misleading because it leads to focus on a goal than the immediate processes, on finding a single solution rather than on the dynamics of populations on abstract landscapes, and it leads one away from the central role of variability. In Sewall Wright's metaphor, in evolution as a biological process (as distinguished from GAs as a search process) it's the behavior of the cloud that is of interest, not the peak it happens to cluster 'round at the moment.
RBH
[ 05. February 2003, 15:05: Message edited by: RBH ]
IP: Logged
|
|
kyle7
Member
Member # 191
|
posted 05. February 2003 19:15
Micah,
GA's are very common. A more interesting project woould be to develop an algorithm using Dembski's Exploratory Filter. There are a diverse number of ways that you could implement this. The purpose of this algorithm would be to discern what is natural and what is designed. Some possible applications are the following:
1) Examine a picture to determine where the missile is on the picture.
2) Examine sounds and decide if they are intelligent or "natural".
3) Find a designed object in the sand using a robotic arm/hand.
4) Examine a string of numbers and determine if the string is random or if the string is intelligently designed.
5) Examine radio waves and decide if the signal is
natural or intelligently designed.
I am sure you could think of something simple that would make a good project. I don't think anyone has done this before, so you could be the first using an algorithm of Dembski's filter -- as far as I know. Maybe Dr. Dembski would be kind enough to suggest something.
kyle
IP: Logged
|
|
Rex Kerr
Member
Member # 632
|
posted 05. February 2003 23:23
For a one-semester class, you want to do use a technique that is already established--GAs, SA, multilayer perceptrons, hidden Markov models, etc..
Also, the EF is not amenable to implementation on a computer, in most cases, since it relies on our ability to spot subsets of data that are similar to something we've already seen or know about or can derive. (Hence the discussion of whether your specifications need to be found in advance or not.) We don't have well-established ways to generate that capability in a computerized system, so the power of the system is severely (probably uselessly) hampered: you would be reduced to constructing all the specifications in advance.
I can't offhand think of a way to do this that would work and yet give a nontrivial result.
IP: Logged
|
|
gedanken
Member
Member # 594
|
posted 05. February 2003 23:34
quote:
I think the analogy with search is misleading because it leads to focus on a goal than the immediate processes, on finding a single solution rather than on the dynamics of populations on abstract landscapes, and it leads one away from the central role of variability. In Sewall Wright's metaphor, in evolution as a biological process (as distinguished from GAs as a search process) it's the behavior of the cloud that is of interest, not the peak it happens to cluster 'round at the moment.
Indeed, that is the problem of doing an AI project (in a semester, alone) that has any relevance to ID. Because the problems to be solved in AI (at the level of a first or early graduate course) are focused on search behavior.
The best relevance I was hoping for would be some sense of the degree of surprising results that can be obtained from some rather simple search procedures, in terms of solving complex appearing problems. What I think will be most illuminating will be a search result that prompts the observer (e.g. Micah) to scratch his head and say “how did it do that”. (And at that point Micah will have to implement a tracing log to try to understand how it arrived at the result -- and then discover the extreme volume of data, and have yet another problem to solve to try to understand the behavior of the very program that he already “understands” because he wrote it.)
(One suggestion: be sure to use only truly “pseudorandom” number generators that are actually deterministic, just decoupled from the problem being operated on, if and when any randomness is introduced. And also be sure to either manually input the seed, or if it is randomly generated be sure that it can be re-input so the deterministic result can be reproduced. You will very much want to reproduce the same result in any of the “Monte Carlo” related randomized procedures like SA, GA, or any search that uses random rather than “deterministic” generate order, because you will find something interesting, even if it is an error, and want to generate the same case over and over as you study it.)
And beyond that, one is simply not going to have enough time nor experience to develop anything that really produces a novel result, unless one has an extraordinary commitment to the project.
The problem with Kyle7’s suggestions is that they all involve having a decent search and analysis engine already running, focused on specifics like image processing or some other advanced search and pattern recognition capability. Since the course is “AI” and not “pattern recognition”, there are entire missing areas (involving more courses) to prepare even to get started. 1,2,3, and 5 all involve image processing or signal processing topics. (Not to mention that the definitional problems of what is intelligent will not be clear to the AI professor. E.g. an AI professor will look upon a primitive AI system as exhibiting a primitive ‘intelligence’, so the entire debates of ISCID would need to be resolved as input to the problem specification for that problem.) Option 4 could be reworded but becomes less of an AI problem, and thus not necessarily suitable for the AI techniques that are expected to be studied in the project. I would think the risks of having an ill-defined project would be high, and would not support such a recommendation or want Micah to be basing his grade on such a suggestion relating to anything I said in that direction.
[ 05. February 2003, 23:55: Message edited by: gedanken ]
IP: Logged
|
|
Frances
Member
Member # 169
|
posted 06. February 2003 00:20
Kyle,
Do you have any suggestions how to deal with the concept of specification in the AI algorithm? Specification seems to be a very important aspect of ID inference and yet is also seems to be the most subjective one. Do you propose any ways of inferring an objective specification detector?
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 06. February 2003 13:49
Micah,
Gedanken's remarks are to the point. In developing your project keep the course goals, the time and effort limits, and the object of the exercise firmly in mind. You are not here and now setting out to revolutionize search algorithms and test major substantive hypotheses; you are learning how to approach doing that. More students get in trouble in projects like this one through over-ambition than anything else.
RBH
IP: Logged
|
|
Douglas
Member
Member # 641
|
posted 08. February 2003 16:17
quote:
Do you have any suggestions how to deal with the concept of specification in the AI algorithm? Specification seems to be a very important aspect of ID inference and yet is also seems to be the most subjective one. Do you propose any ways of inferring an objective specification detector?
Wouldn't there be a way, at least in theory, for a neural network to be "trained" to distinguish between that which is "designed" and that which isn't? Using examples to "teach" it, perhaps. For example, teaching it to distinguish between natural landscapes and manmade objects/architecture (the level of "specification" would be up to the researcher to choose to express in the choice of examples). Once it had learned to discern "design" in that "realm", then "design" could perhaps be generalized to other "realms". I don't know how such an approach would work in discerning "design" in a series of letters or words, though. Anyway, just "brainstorming". Take cover.
IP: Logged
|
|
gedanken
Member
Member # 594
|
posted 09. February 2003 10:40
(Once again I recommend heeding the remarks that I and RBH have made in terms of any “practical” project for your paper.)
But I find something interesting in the posts by Kyle7 and Douglas. ID advocates have very much rejected that an AI could actually be successful at advanced intellectual discrimination tasks, such as would be required to do innovative creation of “design”. Yet respondents are quite willing to ascribe such advanced intellectual subtasks as reasonable in development of an AI that “detects design” here.
IP: Logged
|
|
|
Printer-friendly view of this topic