Machine Learning and History

I’ve had this idea for doing clustering and data mining of history texts.  Would be interesting to creating learning algorithms that can learn timelines and context.  Essentially history textbooks are structured possibly geographically and as a time series of events.  Then doing graphical analysis and social analysis on these structures.  Could compare history texts and see what is left out and maybe what each text places more emphasis on what events.  Also, doing this across time to see how history texts have changed in what the historians themselves find interesting.  Possibly finding patterns in history itself that were not evident or obvious without such algorithms that can crunch large large volumes quickly.  Doing the normal sentiment analysis as well.

This could then lead to producing a better picture of different countries and people groups and how they were formed.  Possibly doing anomaly analysis or creating other types of filters to uncover gaps in the history texts themselves.

This of course seems like it should have been done.  Main issue is getting digital copies of the history books for the algorithm to work with.  So, it may not have been studied.  Creating learning algorithms that can understand human history seems like an important area of research.  Especially as we are writing history now it is important to maintain a grasp of the entire picture and how everything fits together.

Starting on IROS 2016 paper

I got the rejection email from AAMAS last week for my paper on task abandonment for my bounty hunting system.  However, I sort of was expecting this as it needs some more theoretical basis.  So, I have to work on that.

In the mean time there is still IROS!  That is in Korea :).  The paper is due March 1st and I just started working on getting the code written for that.  But this is a fun paper as it is combining cloud robotics (can’t stand that name!) and my bounty hunting work.  So, I’m giving myself a lightning fast tutorial on ROS, raspberry pi, and the pioneer 3dx robot!  Plan is to get the base system working by friday so next week we can start doing experiments and collecting results.  Then the week before the paper is due we can write it!  So, I think we will have just enough time to pull it off.  At least this paper seems likely to be accepted as it both cloud robotics and bounty hunting are very cutting edge and putting it all on an actual robot should seal the deal :)!  So, hopefully I’ll be going to Korea in October!

MAS applications

I found this journal Practical Applications of Agents and Multi-Agent Systems and their list of publications and conference proceedings here.  They look like a very neat conference.  I took a look at their most recent proceedings and found to my delight that they have some cool applications that I’m interested in and make me think that some of my ideas for applications for the Bounty system aren’t so bad.

First, I think that my idea for using the bounty system for reducing traffic problem in an earlier post might be a good one (here and maybe here but it seems like maybe they could be developed a bit more).  Or at least that the bounty model should be applied.  I found the paper, From Goods to Traffic: First Steps Toward an Auction-Based Traffic Signal Controller, that was published this year in paamas which shows that there is some interest in using these sorts of methods.

The other idea I had a while back was to use the bounty system for parking (here)!  They have a paper, Evaluating the Social Benefit of a Negotiation–Based Parking Allocation, which looks into the problem of parking in cities and methods for doing this and how it can help both the city and the drivers.  So, again there is a body of work (they cite) that is interested in this problem.

Maybe I should put together some of my ideas for applying bounties to these problems and try and publish them there?  Also, I’m excited to find out what other problems that paamas has published.  Glad I found this and can’t wait for the semester to begin :).

 

Decision Theory Paradoxes

I’ve been researching decision theory paradoxes because in my Bounty’s task allocation system I am considering the benefits of giving the bondsman the decision to allocate particular tasks through an auction (ie exclusive) or through its normal bounty (non-exclusive) method.  This brings with it a potentially multi-criteria decision which has me interested about the theoretical ramifications of such a decision.

In my search I have encountered quite a few paradoxes in decision theory, utility theory, and social choice (ie voting).  However, other than the wikipedia listing I haven’t found an authoritative reference (a book) on the subject!  I find this quite strange.  I know probably there are very few people that like this sort of thing, but I believe that knowing about them and that they exist might be of use to multiagent systems researchers who use such theories as the basis for their work.  So, if I can’t find a book or a survey paper on the subject I might write a paper on them.  That would be fun.  I would relate them all to problems in MAS and AI or computer science.  So, it would be Paradoxes that are relevant to an AI researcher.

Multi-team Systems

A multi team system consists of multiple teams where each team may have their own goals, but system in general has a common ultimate goal http://en.wikipedia.org/wiki/Multiteam_system.  This is really interesting.  I think that this would be an interesting direction to move bounties.

Also, on a different note, I think that a survey of this field would be useful.  Especially since I think those in the multiagent community should start to think in this manner.  I did some googling and I thought for sure that the robocup rescue simulation league would have some research on this topic.

As always I have to go back over my posts and it seems like I had an idea for multi-teams but in terms of fuzzy sets.  https://drewsblog.herokuapp.com/?p=1621.

HyperNEAT and facial recognition

So, I know that facial recognition is pretty decent, but I think that HyperNEAT would be pretty good at doing this.  I think that it would be able to take advantage of the geometry of the face in order to better characterize the face.  I have found a paper that used HyperNEAT on digits, and it did not do extremely well.  They found that HyperNEAT is good at extracting useful features that could then be used to classify.  So, maybe that would be something else to look at.

Automatic feature and target selection

So, I think that I will need to augment how we make features, behaviors and targets in order to get the automatic feature selection (and now automatic target selection as well.  I forgot about how features can take targets!).

We need to annotate them.  Otherwise, I think that we won’t be able to get a good clustering.  Also, annotation will help to pick the features and the corresponding targets.  I think that maybe that induction from the targets for the behaviors to the features might be something to think about.  The annotations are essentially providing the semantics that we as humans take for granted.  Otherwise the clustering would probably not work.

I also think that targets will need to be chosen based on the overall semantics of the learned behavior.  So, like the behavior for determining whether to play on offense or defense was based on a feature distanceTo(me, centerField) I would have to say that this behavior is semantically a location based behavior.  This would then limit the set of behaviors and targets the feature and target selector would have to choose from.  I think that this is enough.  In the future this could be even more generalized.

If this method doesn’t work to pick the targets for the features, then the targets could be chosen in post by the trainer and then the decision tree could be built based off of that.

Repairmen and Trees

I think I have finally found a problem that has not been studied and is important.  I’m calling it the K-D-Traveling Repairman Problem.  K, the number of repairmen, D, the number of types of repairmen.  The repairman problem is a NP-hard problem and therefore heurstics are used to solve it.  The Predictics group at CMU used Machine learning to approximate solutions to the TRP.  I’ve found one other author that has looked at the K-TRP problem.  I can’t find anyone that has looked at the K-D-TRP.  This is a heterogeneous extension.  Basically I’m saying that there are different types of repairmen that may need to overlap at nodes such in order to perform the repair.

Another interesting extension is a dynamic graph.  Also, I’m interested in looking at saturation levels of repairmen.  Non-deterministic repair times would also be another aspect to look at.  The nice thing with this problem is that it is based on a real world problem that really needs to be solved.

Also, want to look Game theory, optimization theory and expander graphs seem like they will be useful in the theoretic aspect of the problem.  I want to then develop a multi-agent learning algorithm where the agents learn how to solve the problem.

Also, I have been reading about some cool trees: KD-Trees and KD-B-Trees.  They are pretty cool.

Voting and Auction based Monitors

Condition variables and monitors go hand in hand.  There are various monitor protocols: Signal-and-Continue (SC), Signal-and-Urgent-Wait (SU), Signal-and-Exit, Urgent-Signal-and-Continue etc.  Basically these protocols define what order threads get to enter, reenter, and exit methods in a monitor.  They are defined by a first-come first-served (FCFS) queuing schemes to ensure their specific protocols are met.

I am proposing two protocols that are based on Voting and Auctions.  The idea here is that threads get to enter in the order in which they were voted or if they won the auction.  The auction would be like the auctions that google uses for placement of ads on a page.

SU Monitor for producer consumer problem

Monitor queues for producer consumer problem.

The threads could base their decisions on data the monitor has about each of the threads, data the thread has collected, or some other way defined by the coder.  This is the interesting part.

I think that there may be a way to use Arrow’s Theorem to provide some guarantees about some things.

Schepperle, H., & Bohm, K. (2008). Auction-Based Traffic Management: Towards Effective Concurrent Utilization of Road Intersections. E-Commerce Technology and the Fifth …, 105–112. doi:10.1109/CEC/EEE.2008.9

The above reference seems to be heading in the direction I was thinking except they were narrower.

 

And while I was writing this I found http://www.isi.edu/~lerman/projects/task/ has some good papers on mathematical modeling of multiagent systems.