Changeset 5

Timestamp:

04/11/11 14:43:03 (13 years ago)

Author:

sherbold

Message:

• major debugging of PPM and Trie. Results are now correct, but both classes need major refactorings

Location:

trunk/EventBenchCore

Files:

• .classpath (modified) (1 diff)
• lib/collections-generic-4.01.jar (added)
• lib/commons-codec-1.5.jar (added)
• src/de/ugoe/cs/eventbench/data/Event.java (modified) (3 diffs)
• src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java (modified) (10 diffs)
• src/de/ugoe/cs/eventbench/ppm/Trie.java (modified) (7 diffs)
• src/de/ugoe/cs/eventbench/ppm/TrieNode.java (modified) (3 diffs)

trunk/EventBenchCore/.classpath

@@ -20 +20 @@
         <classpathentry kind="lib" path="lib/vecmath-1.3.1.jar"/>
         <classpathentry kind="lib" path="lib/wstx-asl-3.2.6.jar"/>
+        <classpathentry kind="lib" path="lib/commons-codec-1.5.jar"/>
         <classpathentry combineaccessrules="false" kind="src" path="/JavaHelperLib"/>
         <classpathentry kind="output" path="bin"/>

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java

@@ -26 +26 @@
 
 
-        private String idInfo = null;
+        private String idInfo = "";
         
         public Event(String type) {
@@ -59 +59 @@
                 if (targetShort!=null) {
                         shortId = targetShort+"."+getType();
-                        if (idInfo!=null) {
+                        if (idInfo!="") {
                                 shortId += "."+idInfo;
                         }
@@ -68 +68 @@
         public String getStandardId() {
                 String id = target + "." + getType();
-                if ( idInfo!=null ) {
+                if ( idInfo!="" ) {
                         id += "." + idInfo;
                 }

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java

@@ -1 +1 @@
 package de.ugoe.cs.eventbench.ppm;
 
+import java.util.ArrayList;
 import java.util.LinkedHashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Random;
@@ -12 +14 @@
 public class PredictionByPartialMatch {
         
-        private String initialSymbol = "GLOBALSTARTSTATE";
-        private String endSymbol = "GLOBALENDSTATE";
+        private String initialSymbol = "GS";
+        private String endSymbol = "GE";
         
         private int maxOrder = 3;
@@ -20 +22 @@
         
         private Set<String> knownSymbols;
+        
+        private double probEscape = 0.2d; // TODO getter/setter - steering parameter!
+        
+        private Random r = new Random(); // TODO should be defined in the constructor
         
         // the training is basically the generation of the trie
@@ -29 +35 @@
                 
                 for(List<Event<?>> sequence : sequences) {
-                        IncompleteMemory<String> latestActions = new IncompleteMemory<String>(maxOrder); // TODO need to check if it should be maxOrder+1
-                        latestActions.add(initialSymbol);
-                        for(Event<?> currentAction : sequence) {
-                                String currentId = currentAction.getStandardId();
-                                latestActions.add(currentId);
-                                knownSymbols.add(currentId);
-                                if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder
-                                        trie.add(latestActions.getLast(maxOrder));
-                                }
-                        }
-                        latestActions.add(endSymbol);
-                        if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder
+                        List<String> stringSequence = new LinkedList<String>();
+                        stringSequence.add(initialSymbol);
+                        for( Event<?> event : sequence ) {
+                                stringSequence.add(event.getStandardId());
+                        }
+                        stringSequence.add(endSymbol);
+                        
+                        trainStringTrie(stringSequence);
+                }
+        }
+        
+        private void trainStringTrie(List<String> sequence) {
+                knownSymbols = new LinkedHashSet<String>();             
+                IncompleteMemory<String> latestActions = new IncompleteMemory<String>(maxOrder);
+                int i=0;
+                for(String currentAction : sequence) {
+                        String currentId = currentAction;
+                        latestActions.add(currentId);
+                        knownSymbols.add(currentId);
+                        i++;
+                        if( i>=maxOrder ) {
                                 trie.add(latestActions.getLast(maxOrder));
                         }
                 }
-        }
-        
-        public void printRandomWalk(Random r) {
+                int sequenceLength = sequence.size();
+                for( int j=maxOrder-1 ; j>0 ; j-- ) {
+                        trie.add(sequence.subList(sequenceLength-j, sequenceLength));
+                }
+        }
+        
+        public void testStuff() {
+                // basically an inline unit test without assertions but manual observation
+                List<String> list = new ArrayList<String>();
+                list.add(initialSymbol);
+                list.add("a");
+                list.add("b");
+                list.add("r");
+                list.add("a");
+                list.add("c");
+                list.add("a");
+                list.add("d");
+                list.add("a");
+                list.add("b");
+                list.add("r");
+                list.add("a");
+                list.add(endSymbol);
+                
+                PredictionByPartialMatch model = new PredictionByPartialMatch();
+                model.trie = new Trie<String>();
+                model.trainStringTrie(list);
+                model.trie.display();
+                Console.println("------------------------");
+                model.randomSequence();/*
+                Console.println("------------------------");
+                model.randomSequence();
+                Console.println("------------------------");
+                model.randomSequence();
+                Console.println("------------------------");*/
+                
+                List<String> context = new ArrayList<String>();
+                String symbol = "a";
+                // expected: 5
+                Console.traceln(""+model.trie.getCount(context, symbol));
+                
+                // expected: 0
+                context.add("b");
+                Console.traceln(""+model.trie.getCount(context, symbol));
+                
+                // expected: 2
+                context.add("r");
+                Console.traceln(""+model.trie.getCount(context, symbol));
+                
+                // exptected: [b, r]
+                context = new ArrayList<String>();
+                context.add("a");
+                context.add("b");
+                context.add("r");
+                Console.traceln(model.trie.getContextSuffix(context).toString());
+                
+                // exptected: []
+                context = new ArrayList<String>();
+                context.add("e");
+                Console.traceln(model.trie.getContextSuffix(context).toString());
+                
+                // exptected: {a, b, c, d, r}
+                context = new ArrayList<String>();
+                Console.traceln(model.trie.getFollowingSymbols(context).toString());
+                
+                // exptected: {b, c, d}
+                context = new ArrayList<String>();
+                context.add("a");
+                Console.traceln(model.trie.getFollowingSymbols(context).toString());
+                
+                // exptected: []
+                context = new ArrayList<String>();
+                context.add("a");
+                context.add("b");
+                context.add("r");
+                Console.traceln(model.trie.getFollowingSymbols(context).toString());
+        }
+        
+        // TODO needs to be changed from String to <? extends Event>
+        public List<String> randomSequence() {
+                List<String> sequence = new LinkedList<String>();
+                
                 IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1);
-                
                 context.add(initialSymbol);
+                sequence.add(initialSymbol);
                 
                 String currentState = initialSymbol;
@@ -61 +154 @@
                                 probSum += getProbability(currentContext, symbol);
                                 if( probSum>=randVal ) {
-                                        currentContext.add(symbol);
+                                        context.add(symbol);
+                                        currentState = symbol;
+                                        sequence.add(currentState);
+                                        break;
+                                }
+                        }
+                }
+                return sequence;
+        }
+        
+        /*public void printRandomWalk(Random r) {
+                IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1);
+                
+                context.add(initialSymbol);
+                
+                String currentState = initialSymbol;
+                
+                Console.println(currentState);
+                while(!endSymbol.equals(currentState)) {
+                        double randVal = r.nextDouble();
+                        double probSum = 0.0;
+                        List<String> currentContext = context.getLast(maxOrder);
+                        // DEBUG //
+                        Console.traceln("Context: " + currentContext.toString());
+                        double tmpSum = 0.0d;
+                        for( String symbol : knownSymbols ) {
+                                double prob = getProbability(currentContext, symbol);
+                                tmpSum += prob;
+                                Console.traceln(symbol + ": " + prob);
+                        }
+                        Console.traceln("Sum: " + tmpSum);
+                        // DEBUG-END //
+                        for( String symbol : knownSymbols ) {
+                                probSum += getProbability(currentContext, symbol);
+                                if( probSum>=randVal-0.3 ) {
+                                        context.add(symbol);
                                         currentState = symbol;
                                         Console.println(currentState);
@@ -68 +196 @@
                         }
                 }
-        }
-        
+        }*/
+        
+        private double getProbability(List<String> context, String symbol) {
+                // FIXME needs exception handling for unknown symbols
+                // if the symbol is not contained in the trie, context.remove(0) will fail
+                double result = 0.0d;
+                double resultCurrentContex = 0.0d;
+                double resultShorterContex = 0.0d;
+                
+                List<String> contextCopy = new LinkedList<String>(context); // defensive copy
+
+        
+                List<String> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
+                int sumCountFollowers = 0; // N(s\sigma')
+                for( String follower : followers ) {
+                        sumCountFollowers += trie.getCount(contextCopy, follower);
+                }
+                
+                int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
+                if( contextCopy.size()==0 ) {
+                        resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
+                } else {
+                        resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape);
+                        contextCopy.remove(0); 
+                        double probSuffix = getProbability(contextCopy, symbol);
+                        if( followers.size()==0 ) {
+                                resultShorterContex = probSuffix;
+                        } else {
+                                resultShorterContex = probEscape*probSuffix;
+                        }
+                }
+                result = resultCurrentContex+resultShorterContex;
+                
+                return result;
+        }
+        
+        /*
         private double getProbability(List<String> context, String symbol) {
                 double result = 0.0; 
@@ -75 +238 @@
                 List<String> contextSuffix = trie.getContextSuffix(context);
                 if( contextSuffix.isEmpty() ) {
-                        result = 1.0d / knownSymbols.size(); 
+                        // unobserved context! everything is possible... assuming identical distribution
+                        result = 1.0d / knownSymbols.size(); // why 1.0 and not N(symbol)
                 } else {
                         countContextSymbol = trie.getCount(contextSuffix, symbol);
@@ -85 +249 @@
                         
                         if( followers.isEmpty() ) {
-                                throw new AssertionError("Invalid return value of getContextSuffix!");
+                                throw new AssertionError("Invalid return value of trie.getContextSuffix()!");
                         }
                         if( countContextSymbol!=0 ) {
@@ -91 +255 @@
                         } else { // escape
                                 double probEscape = ((double) followers.size()) / (followers.size()+countContextFollowers);
-                                contextSuffix.remove(0);
+                                contextSuffix.remove(0); 
                                 double probSuffix = getProbability(contextSuffix, symbol);
                                 result = probEscape*probSuffix;
@@ -98 +262 @@
 
                 return result;
-        }
+        }*/
         
         @Override

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java

@@ -1 +1 @@
 package de.ugoe.cs.eventbench.ppm;
 
+import java.awt.Dimension;
+import java.awt.Rectangle;
+import java.awt.Shape;
 import java.util.LinkedList;
 import java.util.List;
 
+import javax.swing.JFrame;
+
+import org.apache.commons.collections15.Transformer;
+
+import edu.uci.ics.jung.algorithms.layout.Layout;
+import edu.uci.ics.jung.algorithms.layout.TreeLayout;
+import edu.uci.ics.jung.graph.DelegateTree;
+import edu.uci.ics.jung.graph.Tree;
+import edu.uci.ics.jung.visualization.BasicVisualizationServer;
+import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
+import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;
+
 public class Trie<T> {
         
+        // Children of the Trie root
+        // should contain counts of all elements
         private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
         
@@ -11 +28 @@
         public void add(List<T> subsequence) {
                 if( !subsequence.isEmpty() ) {
-                        subsequence = new LinkedList<T>(subsequence);  // copy list!
+                        subsequence = new LinkedList<T>(subsequence);  // defensive copy!
                         T firstSymbol = subsequence.get(0);
                         getChildCreate(firstSymbol).add(subsequence);
@@ -37 +54 @@
         }
 
+        // get the count of "sequence"
         public int getCount(List<T> sequence) {
                 int count = 0;
@@ -46 +64 @@
         }
         
+        // get the count of "sequence,follower"
         public int getCount(List<T> sequence, T follower) {
                 List<T> tmpSequence = new LinkedList<T>(sequence);
@@ -54 +73 @@
         
         public TrieNode<T> find(List<T> sequence) {
+                List<T> sequenceCopy = new LinkedList<T>(sequence);
                 TrieNode<T> result = null;
-                if( !sequence.isEmpty() ) {
-                        TrieNode<T> node = getChild(sequence.get(0));
+                if( !sequenceCopy.isEmpty() ) {
+                        TrieNode<T> node = getChild(sequenceCopy.get(0));
                         if( node!=null ) {
-                                result = node.find(sequence);
+                                sequenceCopy.remove(0);
+                                result = node.find(sequenceCopy);
                         }
                 }
@@ -64 +85 @@
         }
         
+        // returns all symbols that follow the defined sequence
         public List<T> getFollowingSymbols(List<T> sequence) {
-                List<T> result = null;
-                TrieNode<T> node = find(sequence);
-                if( node!=null ) {
-                        result = node.getFollowingSymbols();
+                List<T> result = new LinkedList<T>();
+                if( sequence==null || sequence.isEmpty() ) {
+                        for( TrieNode<T> child : children ) {
+                                result.add(child.getSymbol());
+                        }
+                } else {
+                        TrieNode<T> node = find(sequence);
+                        if( node!=null ) {
+                                result = node.getFollowingSymbols();
+                        }
                 }
                 return result;
         }
         
+        // longest suffix of context, that is contained in the tree and whose children are leaves
         public List<T> getContextSuffix(List<T> context) {
-                List<T> contextSuffix = new LinkedList<T>(context);
+                List<T> contextSuffix = new LinkedList<T>(context); // defensive copy
                 boolean suffixFound = false;
                 
@@ -87 +116 @@
                                         }
                                 }
-                                contextSuffix.remove(0);
+                                if( !suffixFound ) {
+                                        contextSuffix.remove(0);
+                                }
                         }
                 }
                 
                 return contextSuffix;
+        }
+        
+        
+        static public class Edge{}
+        
+        static public class TrieVertex {
+                private String id;
+                protected TrieVertex(String id) {
+                        this.id = id;
+                }
+                public String toString() {
+                        return id;
+                }
+        }
+        
+        private Tree<TrieVertex, Edge> getGraph() {
+                DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
+                
+                TrieVertex root = new TrieVertex("root");
+                graph.addVertex(root);
+                                
+                for( TrieNode<T> node : children ) {
+                        node.getGraph(root, graph);
+                }
+                
+                return graph;
+        }
+        
+        public void display() {
+                Tree<TrieVertex, Edge> graph = this.getGraph();
+                Layout<TrieVertex, Edge> layout = new TreeLayout<TrieVertex, Edge>(graph, 60);
+                // The BasicVisualizationServer<V,E> is parameterized by the edge types
+                BasicVisualizationServer<TrieVertex,Edge> vv =
+                new BasicVisualizationServer<TrieVertex,Edge>(layout);
+                vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size
+                
+                
+                final Rectangle rect = new Rectangle(40, 20);
+                        
+                Transformer<TrieVertex, Shape> vertexShapeTransformer =
+                        new Transformer<TrieVertex, Shape>() {
+                                public Shape transform(TrieVertex s) {
+                                        return rect;
+                                }
+                };
+                vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
+                vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer);
+                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<TrieVertex>());
+                
+                JFrame frame = new JFrame("Trie");
+                frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
+                frame.getContentPane().add(vv);
+                frame.pack();
+                frame.setVisible(true);
         }
         

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java

@@ -5 +5 @@
 import java.util.List;
 
+import de.ugoe.cs.eventbench.ppm.Trie.Edge;
+import de.ugoe.cs.eventbench.ppm.Trie.TrieVertex;
 import de.ugoe.cs.util.StringTools;
+import edu.uci.ics.jung.graph.DelegateTree;
 
 
@@ -80 +83 @@
         }
         
+        // returns all symbols that follow this node
         public List<T> getFollowingSymbols() {
                 List<T> followingSymbols = new LinkedList<T>();
@@ -97 +101 @@
         }
 
+        public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
+                TrieVertex vertex = new TrieVertex(getSymbol().toString()+"#"+getCount());
+                graph.addChild( new Edge() , parent, vertex );
+                for( TrieNode<T> node : children ) {
+                        node.getGraph(vertex, graph);
+                }               
+        }
+
 }