cdilp
index
(built-in)

ILASP CDILP module documentation.
 
The methods below rely on the concept of a "coverage formula". The goal of the
CDILP procedure is to build up coverage formulas which need to hold for
examples to be covered. A pair <F, e>, where F is a coverage formula that needs
to hold for e to be covered. A coverage formula takes one of the following forms:
 
  - {'rule_in_hyp': [integer rule id]}
  - {'negation':    [coverage formula]}
  - {'disjunction': [list of coverage formulas]}
  - {'conjunction': [list of coverage formulas]}
  - {'ordering': {
        'operator': '<' OR '>' OR '<=' OR '>=' OR '!=' OR '='
        'levels': [list of ordering constraints]
      }
    }
 
Where an ordering constraint is an object of the following form:
 
{
  'priority':          [integer],
  'background-weight': [integer],
  'rule-weights':      [ list of rule-weights ]
}
 
where a rule-weight is of the form {[integer rule id]: [integer weight]}
 
A rule_in_hyp coverage formula is satisfied by a hypothesis if and only if the
hypothesis contains the relevant rule. The semantics of negations, disjunctions
and conjunctions are defined as is usual in propositional logic.
 
The ordering operators are useful for learning weak constraints and are
interpreted as follows. At each level, the rule_weight_sum is the sum of of all
the weights for rule ids which are in the hypothesis. If the rule_weight_sum is
equal to the background weight at every level, then the ordering coverage
formula is satisfied if and only if the operator is '='. If there is at least
one level at which the background weight is not equal to the rule_weight_sum,
then we interpret the formula at the first such level (according to the
priority, which are read in descending order). The formula is satisfied iff (at
this level) rule_weight_sum op background_weight (e.g. if op is <) this is
satisfied iff rule_weight_sum < background_weight.

 
Functions
       
add_coverage_constraint(...)
ilasp.cdilp.add_coverage_constraint(coverage_formula, [list of examples])
 
This method tells the CDILP solver that the coverage formula must be satisfied
for any of the examples in the list to hold. This means that when
ilasp.cdilp.solve() is called, it must either pay the penalty for all of these
examples (and return them as uncovered), or it must satisfy the coverage
formula.
analyse_conflict(...)
constraint = ilasp.cdilp.analyse_conflict(hypothesis, example, conflict_analysis_strategy)
 
Given a hypothesis 'H' and an example 'e', such that 'H' does not cover 'e',
this function computes a constraint that is not satisfied by 'H' but that must
be satisfied for 'e' to be covered. The conflict_analysis_strategy object
specifies the method for computing a constraint from each type of example; for
instance, the default conflict_analysis_strategy object used by ILASP4 is:
 
conflict_analysis_strategy = { 
  'positive-strategy': 'all-ufs',
  'negative-strategy': 'single-as',
  'brave-strategy':    'all-ufs',
  'cautious-strategy': 'single-as-pair'
}
 
Currently, the valid options for conflict_analysis_strategy are 'all-ufs' and
'single-ufs' for positive and brave-ordering examples, 'single-as' for negative
examples and 'single-as-pair' for cautious ordering examples.
 
This method is used in the PyLASP script for ILASP4. Documentation of the
options for constraint strategies will be made available soon. In future
versions of ILASP, it is intended that there will be many more options
available for strategies, which will be targeted at particular types of
learning task. It is also possible for users to implement their own methods of
conflict analysis in a PyLASP script. The conflict analysis step for ILASP3 is
partially implemented in Python, using the generate_sufficient_constraint
function described below.
generate_sufficient_constraint(...)
output_constraint = ilasp.cdilp.generate_sufficient_constraint(example, input_constraint)
 
Given an example 'e' and an input constraint 'c_i', this function computes a
constraint 'c_o' such that:
 
   1) There is at least one hypothesis that satisfies c_o that satisfies c_i.
 
   2) Every hypothesis H that satisfies c_o that satisfies the relevant condition
      for the example type of 'e':
 
         - If e is a positive or negative CDPI, there is at least one answer
           set of B union H union e_{ctx} that extends e_{pi}.
 
         - If e is a brave ordering, there is a pair of answer sets (w.r.t. B
           union H and the pair of contexts in the ordering) which are ordered
           correctly.
 
         - If e is a cautious ordering, there is a pair of answer sets (w.r.t.
           B union H and the pair of contexts in the ordering) which are
           ordered incorrectly.
 
This method allows us to define ILASP3's conflict analysis step within PyLASP.
initialise(...)
ilasp.cdilp.initialise()
 
Initialises the CDILP internal data structures. This should be called before
using the rest of the module.
propagate_constraint(...)
prop_egs = ilasp.cdilp.propagate_constraint(constraint, examples, options)
 
Calculates a list (prop_egs) of examples which the constraint can be
propagated to.
 
Arguments:
 
  constraint: This is a coverage formula, as described above.
 
  examples: This is a list of example ids.
 
  options: This is a Python dictionary, which must take the form
  {'select-examples': LIST, 'strategy': STRATEGY}, where LIST is a list of
  example types (permitted example types are 'positive', 'negative' and
  'brave-order') and STRATEGY is a propagation strategy (permitted propagation
  strategies are 'cdpi-implies-constraint', 'neg-constraint-implies-cdpi' and
  'cdoe-implies-ordering' -- further propagation strategies are currently in
  development and will be released in later versions of ILASP). Note that
  'cdpi' strategies can only be used with 'positive' and 'negative' example
  selection, and 'cdoe' strategies can only be used with 'brave-order' example
  selection.
 
 
The propagation strategy specifies the type of propagation to perform. The
strategies behave as follows.
 
  'cdpi-implies-constraint': prop_egs is the set of examples 'e' (in the set
  examples) that are of the type specified in the example selection and which
  satisfy the following property: all hypotheses H such that there is at least
  one answer set of B union H union e_{ctx} that extends the partial
  interpretation e_{pi} must satisfy the constraint.
 
  'neg-constraint-implies-cdpi': prop_egs is the set of examples 'e' (in the
  set examples) that are of the type specified in the example selection and
  which satisfy the following property: all hypotheses H that do not satisfy
  the constraint must be such that there is at least one answer set of B union
  H union e_{ctx} that extends the partial interpretation.  This is equivalent
  to saying that all hypotheses for which there is no answer set of B union H
  union e_{ctx} that extends the partial interpretation e_{pi} must satisfy the
  constraint.
 
  'cdoe-implies-constraint': prop_egs is the set of examples 'e' (in the set
  examples) that are of the type specified in the example selection and which
  satisfy the following property: all hypotheses H such that B union H bravely
  respects e must satisfy the constraint.
propagate_constraints_pl(...)
result = ilasp.cdilp.propagate_constraints_pl(constraints, examples, options)
 
This behaves similarly to the propagate_constraint function, except that the
first argument is now a list of constraints. These are propagated in parallel,
and the result is now a list of pairs containing a constraint and the list of
examples it has been propagated to.
solve(...)
solve_result = ilasp.cdilp.solve()
 
This is the "hypothesis search" phase of the CDILP process. It computes the
optimal hypothesis w.r.t. the coverage constraints that have been added so far.
It returns this hypothesis, as part of the solve_result, together with a list
of examples which are known to not be covered and information on the score of
the hypothesis. Note that if the task is unsatisfiable, the solve_result will
be null. The structure of the solve result is:
 
{
  'uncovered':         [ list of example ids],
  'expected_score':    [ an integer (the sum of 'hypothesis_length' and
                         'example penalty' )],
  'example_penalty':   [ an integer ]
  'hypothesis':        [ a list of (integer) rule ids ]
  'hypothesis_length': [ an integer ]
}