Class: Ariel::Learner
- Inherits:
-
Object
- Object
- Ariel::Learner
- Defined in:
- lib/ariel/learner.rb
Overview
Implements a fairly standard separate and conquer rule learning system. Using a list of labeled examples, candidate rules are generated. A rule is refined until it covers as many as possible of the labeled examples. This rule is recorded, the covered examples are removed and the process repeats on the remaining examples. Once all examples are covered, the disjunct of all generated rules is returned.
Instance Attribute Summary collapse
-
#candidates ⇒ Object
Returns the value of attribute candidates.
-
#current_rule ⇒ Object
Returns the value of attribute current_rule.
-
#current_seed ⇒ Object
Returns the value of attribute current_seed.
-
#direction ⇒ Object
Returns the value of attribute direction.
Instance Method Summary collapse
-
#add_new_landmarks(landmark, index) ⇒ Object
Implements topology refinements - new landmarks are added to the current rule.
-
#example_is_unsuitable?(tokenstream) ⇒ Boolean
When learning list iteration rules, some examples may be unsuitable.
-
#find_best_rule ⇒ Object
Equivalent of LearnDisjunct in STALKER algorithm.
-
#generate_initial_candidates ⇒ Object
Using the seed example passed to it, generates a list of initial rule candidates for further refinement and evaluation.
-
#get_best_refiner ⇒ Object
Given a list of candidate rules, uses heuristics to determine a rule considered to be the best refiner.
-
#get_best_solution ⇒ Object
Given a list of candidate rules, use heuristics to determine the best solution.
-
#initialize(*examples) ⇒ Learner
constructor
Takes a list of TokenStreams containing labels.
-
#learn_rule(direction, exhaustive = false) ⇒ Object
Initiates and operates the whole rule induction process.
-
#lengthen_landmark(landmark, index) ⇒ Object
Implements landmark refinements.
-
#perfect?(rule) ⇒ Boolean
A given rule is perfect if it successfully matches the label on at least one example and fails all others.
-
#refine ⇒ Object
Oversees both landmark (e.g. changing skip_to(“<b>”) in to skip_to(“Price”,“<b>”) and topology (skip_to(:html_tag) to a chain of skip_to() commands). Takes the current rule being generated and the example against which it is being created (the current seed_rule) as arguments..
-
#set_seed ⇒ Object
The seed example is chosen from the array of remaining examples.
Constructor Details
#initialize(*examples) ⇒ Learner
Takes a list of TokenStreams containing labels.
14 15 16 17 18 19 20 21 22 |
# File 'lib/ariel/learner.rb', line 14 def initialize(*examples) if examples.any? {|example| example.label_index.nil?} raise ArgumentError, "Passed a TokenStream with no label" end Log.debug "ATTENTION: New Learner instantiated with #{examples.size} labeled examples" @examples=examples @candidates=[] set_seed end |
Instance Attribute Details
#candidates ⇒ Object
Returns the value of attribute candidates.
11 12 13 |
# File 'lib/ariel/learner.rb', line 11 def candidates @candidates end |
#current_rule ⇒ Object
Returns the value of attribute current_rule.
11 12 13 |
# File 'lib/ariel/learner.rb', line 11 def current_rule @current_rule end |
#current_seed ⇒ Object
Returns the value of attribute current_seed.
11 12 13 |
# File 'lib/ariel/learner.rb', line 11 def current_seed @current_seed end |
#direction ⇒ Object
Returns the value of attribute direction.
11 12 13 |
# File 'lib/ariel/learner.rb', line 11 def direction @direction end |
Instance Method Details
#add_new_landmarks(landmark, index) ⇒ Object
Implements topology refinements - new landmarks are added to the current rule.
-
Takes a landmark and its index in the current rule.
-
Applies the rule consisting of all landmarks up to and including the current landmark to find where it matches.
-
Only tokens between the label_index and the position at which the partial rule matches are considered.
-
Tokens before the rule match location will have no effect, as adding new landmarks before or after the current landmark will not make the rule match any earlier.
-
For every token in this slice of the TokenStream, a new potential rule is created by adding a new landmark consisting of that token. This is also done for each of that token’s matching wildcards.
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 |
# File 'lib/ariel/learner.rb', line 226 def add_new_landmarks(landmark, index) topology_refs=[] start_pos = current_rule.partial(0..index).closest_match(current_seed, :early) end_pos = current_seed.label_index #No point adding tokens that occur after the label_index current_seed.tokens[start_pos...end_pos].each do |token| r=current_rule.deep_clone r.landmarks.insert(index+1, [token.text]) topology_refs << r topology_refs.concat r.generalise_feature(index+1) end Log.debug "Topology refinements before uniq! #{topology_refs.size}" topology_refs.uniq! @candidates.concat topology_refs Log.debug "#{topology_refs.size} topology refinements generated" return topology_refs.size end |
#example_is_unsuitable?(tokenstream) ⇒ Boolean
When learning list iteration rules, some examples may be unsuitable. For instance if there is a list item at the start of an example with no tokens before it, a skip_to(nil) start rule would be generated that wouldn’t make sense for exhaustive rules. The example should be caught by the corresponding end rule. This should only be run after tokenstream’s have been prepared (reversed based on whether a :forward or :back rule is being searched for). Only returns a valid conclusion if the examples are intended to be used for exhaustive rule learning
251 252 253 254 255 256 257 |
# File 'lib/ariel/learner.rb', line 251 def example_is_unsuitable?(tokenstream) if tokenstream.label_index==0 return true else return false end end |
#find_best_rule ⇒ Object
Equivalent of LearnDisjunct in STALKER algorithm. Generates initial candidate rules, refines, and then returns a single rule.
83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
# File 'lib/ariel/learner.rb', line 83 def find_best_rule @candidates=[] generate_initial_candidates while true best_refiner = get_best_refiner best_solution = get_best_solution @current_rule = best_refiner break if perfect?(best_solution) refine end # return post_process(best_solution) Log.debug "Rule found: #{best_solution.inspect}" return best_solution end |
#generate_initial_candidates ⇒ Object
Using the seed example passed to it, generates a list of initial rule candidates for further refinement and evaluation. The Token prior to the labeled token is considered, and separate rules are generated that skip_to that token’s text or any of it’s matching wildcards.
68 69 70 71 72 73 74 75 76 77 78 79 |
# File 'lib/ariel/learner.rb', line 68 def generate_initial_candidates if current_seed.label_index==0 @candidates << Rule.new([], @direction, @exhaustive) else end_token=current_seed.tokens[current_seed.label_index-1] Log.debug "Creating initial candidates based on #{end_token.text}" @candidates<< Rule.new([[end_token.text]], @direction, @exhaustive) @candidates.concat(@candidates[0].generalise_feature(0)) Log.debug "Initial candidates: #{@candidates.inspect} created" end return @candidates.size end |
#get_best_refiner ⇒ Object
Given a list of candidate rules, uses heuristics to determine a rule considered to be the best refiner. Prefers candidate rules that have:
-
Larger coverage = early + correct matches.
-
If equal, prefer more early matches - can be made in to fails or perfect matches. Intuitively, if there are more equal matches the rule is finding features common to all documents.
-
If there is a tie, more failed matches wins - we want matches to fail rather than match incorrectly
-
Fewer wildcards - more specific, less likely to match by chance.
-
Shorter unconsumed prefixes - closer to matching correctly
-
fewer tokens in SkipUntil() - huh? Perhaps because skip_until relies on slot content rather than document structure.
-
longer end landmarks - prefer “local context” landmarks.
129 130 131 132 133 134 135 136 137 138 139 140 |
# File 'lib/ariel/learner.rb', line 129 def get_best_refiner r = CandidateRefiner.new(@candidates, @examples) r.refine_by_match_type :early, :perfect #Discriminate on coverage r.refine_by_match_type :early r.refine_by_match_type :fail r.refine_by_fewer_wildcards r.refine_by_label_proximity r.refine_by_longer_end_landmarks best_refiner = r.random_from_remaining #just pick a random one for now if still multiple Log.debug "best_refiner found => #{best_refiner.inspect}" return best_refiner end |
#get_best_solution ⇒ Object
Given a list of candidate rules, use heuristics to determine the best solution. Prefers:
-
More correct matches
-
More failed matches if a tie - failed matches preferable to incorrect matchees.
-
Fewer tokens in SkipUntil()
-
fewer wildcards
-
longer end landmarks
-
shorter unconsumed prefixes
149 150 151 152 153 154 155 156 157 158 159 |
# File 'lib/ariel/learner.rb', line 149 def get_best_solution r = CandidateRefiner.new(@candidates, @examples) r.refine_by_match_type :perfect r.refine_by_match_type :fail r.refine_by_fewer_wildcards r.refine_by_label_proximity r.refine_by_longer_end_landmarks best_solution = r.random_from_remaining Log.debug "best_solution found => #{best_solution.inspect}" return best_solution end |
#learn_rule(direction, exhaustive = false) ⇒ Object
Initiates and operates the whole rule induction process. Finds an example to use as its seed example, then finds a rule that matches the maximum number of examples correctly and fails on all overs. All matched examples are then removed and the process is repeated considering all examples that remain. Returns an array of the rules found (in order). learn_rule will take care of reversing the given examples if necessary.
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# File 'lib/ariel/learner.rb', line 30 def learn_rule(direction, exhaustive=false) Log.debug "Searching for a #{direction} rule" @examples=@examples.collect {|tokenstream| Rule.prepare_tokenstream(tokenstream, direction)} @direction=direction @exhaustive=exhaustive if exhaustive @examples.delete_if {|example| example_is_unsuitable?(example)} raise StandardError, "No examples are suitable for exhaustive rule learning" if @examples.empty? end @current_rule=Rule.new([], direction, exhaustive) combined_rules=[] while not @examples.empty? set_seed unless @examples.include? @current_seed rule = find_best_rule() # Find the rule that matches the most examples and fails on the others prev_size = @examples.size @examples.delete_if {|example| rule.apply_to(example)} #separate and conquer! Log.debug "Removing #{prev_size - @examples.size} examples matched by the generated rule, #{@examples.size} remain" combined_rules << rule end # rule = order_rule(rule) #STALKER paper suggests that the generated rules should be ordered. This doesn't make sense, seeing as they are all generated based only on examples not matched by previous rules Log.debug "Generated rules: #{combined_rules.inspect}" Rule.clear_cache return combined_rules end |
#lengthen_landmark(landmark, index) ⇒ Object
Implements landmark refinements. Landmarks are lengthened to make them more specific.
-
Takes a landmark and its index in the current rule.
-
Applies the rule consisting of all previous landmarks in the current rule, so the landmark can be considered in the context of the point from which it shall be applied.
-
Every point at which the landmark matches after the cur_loc is considered.
-
Two extended landmarks are generated - a landmark that includes the token before the match, and a landmark that includes that token after the match.
-
Rules are generated incorporating these extended landmarks, including alternative landmark extensions that use relevant wildcards.
187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 |
# File 'lib/ariel/learner.rb', line 187 def lengthen_landmark(landmark, index) current_seed.rewind #In case apply_rule isn't called as index=0 result = @current_rule.partial(0..(index-1)).closest_match current_seed if index > 0 #Don't care about already matched tokens return 0 unless result # Rule doesn't match, no point refining refined_rules=[] width = landmark.size while current_seed.skip_to(*landmark) #Probably should stop when cur_pos > label_index break if current_seed.cur_pos > current_seed.label_index match_start = (current_seed.cur_pos - 1) - width #pos of first matched token match_end = current_seed.cur_pos - 1 #pos of last matched token preceding_token = current_seed.tokens[match_start-1] trailing_token = current_seed.tokens[match_end+1] front_extended_landmark = landmark.clone.insert(0, preceding_token.text) if preceding_token back_extended_landmark = landmark.clone.insert(-1, trailing_token.text) if trailing_token f = current_rule.deep_clone b = current_rule.deep_clone f.landmarks[index] = front_extended_landmark if front_extended_landmark b.landmarks[index] = back_extended_landmark if back_extended_landmark refined_rules << f refined_rules.concat f.generalise_feature(index, 0) refined_rules << b refined_rules.concat b.generalise_feature(index, -1) end @candidates.concat refined_rules Log.debug "#{refined_rules.size} landmark refinements generated" return refined_rules.size end |
#perfect?(rule) ⇒ Boolean
A given rule is perfect if it successfully matches the label on at least one example and fails all others.
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
# File 'lib/ariel/learner.rb', line 100 def perfect?(rule) perfect_count=0 fail_count=0 @examples.each do |example| if rule.matches(example, :perfect) perfect_count+=1 elsif rule.matches(example, :fail) fail_count+=1 end end if (perfect_count >= 1) && (fail_count == (@examples.size - perfect_count)) return true else Log.debug "Rule was not perfect, perfect_count=#{perfect_count}, fail_count=#{fail_count}" return false end end |
#refine ⇒ Object
Oversees both landmark (e.g. changing skip_to(“<b>”) in to skip_to(“Price”,“<b>”) and topology (skip_to(:html_tag) to a chain of skip_to() commands). Takes the current rule being generated and the example against which it is being created (the current seed_rule) as arguments.
166 167 168 169 170 171 172 173 |
# File 'lib/ariel/learner.rb', line 166 def refine @candidates=[] current_rule.landmarks.each_with_index do |landmark, index| add_new_landmarks(landmark, index) #Topology refinements lengthen_landmark(landmark, index) #Landmark refinements end return @candidates.size end |
#set_seed ⇒ Object
The seed example is chosen from the array of remaining examples. The LabeledStream with the fewest tokens before the labeled token is chosen.
57 58 59 60 61 62 |
# File 'lib/ariel/learner.rb', line 57 def set_seed sorted = @examples.sort_by {|example| example.label_index} self.current_seed=sorted.first Log.debug "current_seed=#{current_seed.text}" return current_seed end |