:- use_module(library(lists)). :- use_module(library(apply_macros)). %:-['testExamples/1.pl']. /* what variables required? -- end node(base case); start node (stop) 1. score related to each returned hypothesis -- it is contained in the variable of hypothesis: [ClaID-Length-EIList,] -- which Cla is specially for which example can be determined from this information. The length is a sum of each The potential example covered is the union of those appeared at the EI-List. % to improve efficiency, you may want to have seperated variable, and only alter them each time (rather than compute from scratch). 2. anything to be passed between each branch? -- is it OK to use maplist? */ % call hypothesisSelection(startNode,FinalHypothesis) hypothesisSelection(endNode-EI-TI,[[]-[EI-TI]]). % no clauses at all hypothesisSelection(CurrentNode,BestCandidate):- expandNode(CurrentNode,ChildNodes), maplist(hypothesisSelection,ChildNodes,ReturnedCandidates), candidateSelection(ReturnedCandidates,CurrentNode,BestCandidate). % (1) only one (2) beam search -- consider those equal score % % How to make endNode unit with others? -- in case one endNode -- need a score for it. yes including that branch. % all branches that are scored more than zero. expandNode(CurrentNode,ChildNodes):- findall(Child,connect(CurrentNode,Child),ChildNodes). /* The previous selection method (backwards competing) looks fine , then why do u need forward selection? The dilemma is for one example, the best one have to consider the others, while the others although cover more, maybe trade-off for expensive description length. This dilemma is solved by Minimum Description Length. -- a balance between coverage and description length. With the heuristic, which is non-overstimated, it is A*, so optimal. */ % Not to update the Cla Coverage, it is contained in the returned hypothesis % Not only score, but also combine the current node :) candidateSelection(ReturnedCandidates,CurrentNode,NewCandidate):- maplist(scoreCandidateBranches(CurrentNode),ReturnedCandidates,ScoredCandidates0), selectlist(nonNegativeScoreBranch,ScoredCandidates0,ScoredCandidates), % combining those nonZero branches -- filter out those nonZero branches first. sort(ScoredCandidates,SortedScoredCandidates), % combining from the highest score. -- for the last one, which has highest score, just % competing with each other for the same example. combine_and_competing(SortedScoredCandidates,NewCandidate). % not to have new variables, but recheck every time combine_and_competing([],[]). combine_and_competing([Score-CandidateEICoverage-Candidate|SortedScoredCandidates],NewCandidate):- combine_and_competing(SortedScoredCandidates,PreCandidate), exExtraction(PreCandidate,[],PreEICoverage), exExtraction(Candidate,[],EICoverage), (EICoverage==PreEICoverage-> NewCandidate=PreCandidate; ((nonOverlapping(EICoverage,PreEICoverage);nonOverlapping(PreEICoverage,EICoverage))-> append(Candidate,PreCandidate,NewCandidate); overlapPart(EICoverage,PreEICoverage,CompetingEIs), % what to do if they overlap (1) identify the overlap part. ) ). % if a subset, then remove that clause -- update the EITI in the rest of the clauses. % what if the remaining become uncompressed because -- no worry, it will be removed when new branch come. -- simply check whether the remaining still has coverage -- remove the one with single coverage -- long description: e.g. two computing components -- you can't simply remove that branch, maybe the rest still worth for that -- you are allowing the flexibility to decompose the module. % no worry, you can make the selection at this step more complicated later. % selectlist(extractCompetingCla(CompetingEIs),) % no, it is better to isolate % for each claID, removing those belongs -- for the competing part, it doesn't necessarily always one branch, maybe a combination. % 1. competing based on one by one % if a subset like [1,2], then all the others are considered as a pair. -- you can still do the cross production. then certain example will be explained by more than one theory. % 2. competing based on the whole thing competing(Candidate,PreCandidate,CompetingEIs,NewCandidate):- subset(CompetingEIs). /*% competing([],CompetingEIs,). competing(Candidate,PreCandidate,CompetingEIs,NewCandidate):- isolation(Candidate,CompetingEIs,OverlapedCla,CandidateRest),descriptionLength(CandidateRest,DescriptionLength), isolation(PreCandidate,CompetingEIs,PreOverlapedCla,PreCandidateRest),descriptionLength(PreCandidateRest,PreCandidates), competing(Candidate,CompetingEIs,NewCandidate,OverlapedCla):- % if a claID in canididate contains only a subset of -- isolate them -- compute their description -- then decide which branch to remove. isolation(), competing(Candidate,PreCandidate,NewCandidate). */ %overlapPart(Set1,Set2,Intersection) overlapPart(Set1,Set2,Intersection):- sort(Set1,SortedSet1), sort(Set2,SortedSet2), ord_intersection(SortedSet1, SortedSet2, Intersection). %[6,5],[2,1] nonOverlapping(Set1,Set2):- smallestEI(Set1,Set1_RightEnd), biggestEI(Set2,Set2_LeftEnd), Set1_RightEnd>Set2_LeftEnd. biggestEI([],0). biggestEI([EI|EIs],EI). smallestEI([],0). smallestEI(EIList,EI):- last(EIList,EI). /* (SortedScoredCandidates==[] -> BestCandidate=[]; SortedScoredCandidates=[BestScore-BestCandidate|Rest] ).*/ % combining -- (1) remove score; (2) combining the ClaID -- if there are any nonNegativeScoreBranch(Score-CandidateBranch):- Score>=0. % coverage and description length scoreCandidateBranches(CurrentNode,Candidate,Score-EICoverage-[CurrentNode-NewCandidateEITICovergae|Candidate]):- descriptionLength(Candidate,DescriptionLength), coverage(CurrentNode,Candidate,NewCandidateEITICovergae,NewCandiateCoveredEINum-EICoverage), Score is NewCandiateCoveredEINum-DescriptionLength, nl. % coverage of current node.-- EI-TI; % you need to assign EI-TI to the currentNode, it will be an subset % Candidate is [ClaID1-EIList1,ClaID2-EIList2] descriptionLength([],0). descriptionLength([ClaID-ClaEICoverage|Candidate],DescriptionLength):- descriptionLength(Candidate,PreDescriptionLength), %claInterprete(ClaID,Cla),length(Cla,ClaDescriptionLength), -- don't worry about translate them more than once, since there is no redundant node -- probably there is (due to the DAG) length(ClaID,ClaDescriptionLength), DescriptionLength is PreDescriptionLength+ClaDescriptionLength. getEITIList(ClaID-ClaCoverage,ClaSortedCoverage):- sort(ClaCoverage,ClaSortedCoverage). getEI(EI-TI,EI). % Candidate is [ClaID1-[EI-TI1,EI-TI2],ClaID2-EIList2] coverage(CurrentNode,Candidate,NewCandidateEITICovergae,NewCandiateCoveredEINum-EICoverage):- claNode(CurrentNode,CurrendNodeEITICovergae0), sort(CurrendNodeEITICovergae0,CurrendNodeEITICovergae), maplist(getEITIList,Candidate,CandidateEITICoverages), ord_union(CandidateEITICoverages,CandidateEITICoverageUnion), ord_intersection(CandidateEITICoverageUnion,CurrendNodeEITICovergae,NewCandidateEITICovergae), exExtraction(NewCandidateEITICovergae,[],EICoverage), %maplist(getEI,NewCandidateEITICovergae,EICoverage0),remove_duplicates(EICoverage0,EICoverage), length(EICoverage,NewCandiateCoveredEINum). % to obtain score, you need to reaggreagate % ??? always EI-TI, EI-TI, when need coverage, count them. % simple length for coverage % However, you need to de-aggregate and re-aggregate every time. % Input is [1-1,1-2,2-1,2-2,2-3], then the output is [1,2] % exExtraction(Record,[],EIs). exExtraction([],EIs,EIs). exExtraction([EI-TI|Record],[EI|EIs],FinalEI):- !, exExtraction(Record,[EI|EIs],FinalEI). exExtraction([EI-TI|Record],EIs,FinalEI):- !, exExtraction(Record,[EI|EIs],FinalEI). % how does pruning work? -- the competing of same example will be ignored; on the other hand, it consider more combination than pure covering. Because it doesn't simply choose one and continue, but scoring as a whole.