% in this version, when the two candidates are competing, the ClaID of the computing are computed as a whole. % while that's not fair, maybe one particular branch ruin the whole thing :- use_module(library(lists)). :- use_module(library(apply_macros)). % 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. /* what variables required? 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 description length is a sum of each candidate 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. To avoid recalculating the coverage and description length of each branch, please record them for each branch. 3. endNode -- for the nodes ended with the same claID, they should be gathered, otherwise, they have to compete with each other at that point. */ % call hypothesisSelection(startNode,FinalHypothesis) % hypothesisSelection(endNode-EI-TI,[[]-[EI-TI]]). % no clauses at all % each candidate is DL-CoverEITI-[ClaID-[EITI]] hypothesisSelection(CurrentNode,BestCandidate):- expandNode(CurrentNode,ChildNodes), extractEndNode(ChildNodes,EndNodeEITIs0,NonEndChildNodes),sort(EndNodeEITIs0,EndNodeEITIs), %exExtraction(EndNodeEITIs,EndNodeEICoverge), maplist(hypothesisSelection,NonEndChildNodes,ReturnedCandidates), % if NonEndChildNodes=[], then (EndNodeEITIs0==[]-> candidateSelection(ReturnedCandidates,CurrentNode,BestCandidate); candidateSelection([0-EndNodeEITIs-[]|ReturnedCandidates],CurrentNode,BestCandidate)). % (1) only one (2) beam search -- consider those equal score %[]-EndNodeEITIs extractEndNode([],[],[]). extractEndNode([ChildNode|ChildNodes],EndNodeCoverge,NonEndNode):- extractEndNode(ChildNodes,PreEndNodeCoverge,PreNonEndNode), (ChildNode=endNode-EI-TI -> EndNodeCoverge=[EI-TI|PreEndNodeCoverge], NonEndNode=PreNonEndNode; EndNodeCoverge=PreEndNodeCoverge, NonEndNode=[ChildNode|PreNonEndNode] ). expandNode(CurrentNode,ChildNodes):- findall(Child,connect(CurrentNode,Child),ChildNodes). % 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,DescriptionLength-EITIs-[CurrentNode-EITIs|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,DescriptionLength0-EICoverage-EITIs-NewCandidate), claLength(CurrentNode,CurrentNodeDescriptionLength), DescriptionLength is DescriptionLength0+CurrentNodeDescriptionLength. nonNegativeScoreBranch(Score-EICoverage-DL-EITIs-CandidateBranch):- Score>=0. % coverage and description length % the new candidate means combining the currentNode scoreCandidateBranches(CurrentNode,CandidateDescriptionLength-CandidateEITIs-Candidate,Score-EICoverage-DescriptionLength-NewCandidateEITIs-Candidate):-%[CurrentNode-NewCandidateEITIs|Candidate] %claLength(CurrentNode,ClaDescriptionLength), DescriptionLength is CandidateDescriptionLength, %DescriptionLength is CandidateDescriptionLength+ClaDescriptionLength, claNode(CurrentNode,CurrendNodeEITICovergae), ord_intersection(CandidateEITIs,CurrendNodeEITICovergae,NewCandidateEITIs), exExtraction(NewCandidateEITIs,EICoverage), length(EICoverage,NewCandiateCoveredEINum), Score is 3*NewCandiateCoveredEINum-DescriptionLength. % Input is [1-1,1-2,2-1,2-2,2-3], then the output is [1,2] exExtraction([],[]). exExtraction([EI-TI|Record],EIs):- exExtraction(Record,PreEIs), (PreEIs=[EI|Rest] -> EIs=PreEIs; EIs=[EI|PreEIs] ). % 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). */ % not to have new variables, but recheck every time % Score-EICoverage-DescriptionLength-NewCandidateEITIs-Candidate % the returned New candidate (which is derived from by combining branches) should have description length which add the currentNode's length, the covered EITI is the union. -- the CurrentNode's coverage also need to be updated according to the competing result. %combine_and_competing(Candidates,CombinedCanididate):- % add descriptions for each branches % append all ClaID in each branch. -- that's the new candidate % union all the EITI covergae. % Combined Candidate is DescriptionLength-EICoverage-EITIs-NewCandidate combine_and_competing([Score-EICoverage-DescriptionLength-CandidateEITIs-Candidate],DescriptionLength-EICoverage-CandidateEITIs-Candidate). combine_and_competing([Score-EICoverage-DescriptionLength-CandidateEITIs-Candidate|SortedScoredCandidates],DL-NewEICoverage-NewEITIs-NewCandidate):- combine_and_competing(SortedScoredCandidates,PreDL-PreEICoverage-PreEITIs-PreCandidate), % (ord_subset(EICoverage,PreEICoverage)-> % EICoverage is the candidate to be added, PreEICoverage is the combined one % DL-NewEICoverage-NewEITIs-NewCandidate=PreDL-PreEICoverage-PreEITIs-PreCandidate; ord_intersection(EICoverage,PreEICoverage,CompetingEIs), (CompetingEIs=[] -> DL is PreDL+DescriptionLength, ord_union(EICoverage,PreEICoverage,NewEICoverage), % don't use append, that won't ord_union(CandidateEITIs,PreEITIs,NewEITIs), append(Candidate,PreCandidate,NewCandidate); % what if there are redundancy there? isolation(Candidate,CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart), descriptionLength(CandidateOverlapPart,OverlapDescriptionLength), isolation(PreCandidate,CompetingEIs,PreRemainEITIs-PreRemainCandidate,PreOverlapEITIs-PreCandidateOverlapPart), descriptionLength(PreCandidateOverlapPart,PreOverlapDescriptionLength), (OverlapDescriptionLength>=PreOverlapDescriptionLength-> write({OverlapDescriptionLength,PreOverlapDescriptionLength}),write('the new one is more expensive, so keep the previous one'), DL is PreDL+DescriptionLength-OverlapDescriptionLength, % then you should keep the one in PreOverlap exExtraction(RemainEITIs,RemainEIs), ord_union(RemainEIs,PreEICoverage,NewEICoverage), ord_union(RemainEITIs,PreEITIs,NewEITIs), maplist(removeAlones(OverlapEITIs),RemainCandidate,RemainCandidate_noRedundant), append(RemainCandidate_noRedundant,PreCandidate,NewCandidate); write({OverlapDescriptionLength,PreOverlapDescriptionLength}),write('not more expensive, so use the old one'), DL is PreDL+DescriptionLength-PreOverlapDescriptionLength, ord_union(EICoverage,PreRemainEITIs,NewEICoverage), ord_union(CandidateEITIs,PreRemainEITIs,NewEITIs), maplist(removeAlones(PreOverlapEITIs),PreRemainCandidate,PreRemainCandidate_noRedundant), append(Candidate,PreRemainCandidate_noRedundant,NewCandidate) ) ). %). % *** when you remove certain bits, the EITI coverage is changed! -- the EITI is not simply the isolation you have now removeAlones(AloneEITIs,ClaID-EITIs,ClaID-EITIsNoAlone):- nl,write({EITIs,AloneEITIs}), write('check whether they are in order'),nl, ord_subtract(EITIs,AloneEITIs,EITIsNoAlone). isolation([],CompetingEIs,[]-[],[]-[]). isolation([ClaID-ClaEITIs|Candidate],CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart):- isolation(Candidate,CompetingEIs,PreRemainEITIs-PreRemainCandidate,PreOverlapEITIs-PreCandidateOverlapPart), exExtraction(ClaEITIs,ClaEIs), (ord_subset(ClaEIs,CompetingEIs)-> % Here maybe a problem, what if it just contains part of the computing EI? RemainEITIs-RemainCandidate=PreRemainEITIs-PreRemainCandidate, ord_union(ClaEITIs,PreOverlapEITIs,OverlapEITIs), CandidateOverlapPart=[ClaID-ClaEITIs|PreCandidateOverlapPart]; OverlapEITIs-CandidateOverlapPart=PreOverlapEITIs-PreCandidateOverlapPart, ord_union(ClaEITIs,PreRemainEITIs,RemainEITIs), RemainCandidate=[ClaID-ClaEITIs|PreRemainCandidate] ). % 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. 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.