org.hd.d.pg2k.ai.scorer
Class ScorerCacheImpl

java.lang.Object
  org.hd.d.pg2k.ai.scorer.AbstractScorerCache
      org.hd.d.pg2k.ai.scorer.ScorerCacheImpl

All Implemented Interfaces:

ScorerCacheIF

public final class ScorerCacheImpl
extends AbstractScorerCache
implements ScorerCacheIF

Simple/default implementation to compute (and cache) the score and confidence for exhibits. Note: since the result of this computation may be used in computing (EPCM) the ExhibitPropsComputableMutable value for an exhibit, then any implementation of this must avoid forcing recaclulation of any EPCM value to avoid danger of infinite recursion (other than the static calcVoteFactor() method). Ideally the value computed will not depend on any EPCM value.

MAX_SCORER_SCORES_RETAINED

private static final int MAX_SCORER_SCORES_RETAINED

Maximum number of Scorers for which retain/cache scores; strictly positive. This limits the amount of memory dedicated to cache, etc.

In practice 2^14--2^16 seems to be a reasonable limit.

See Also:

Constant Field Values

MIN_VOTE_SAMPLE_NEAR_TERM_TIME_MS

private static final long MIN_VOTE_SAMPLE_NEAR_TERM_TIME_MS

The minimum recent period for which we collect all available votes, in ms; strictly positive. This is usually at least a year to smooth out for seasonal patterns.

See Also:

Constant Field Values

_votedForExhibits

private final java.util.SortedMap<java.lang.Long,java.util.Map<java.lang.String,ScoreAndConf>> _votedForExhibits

Get all voted-for exhibits (by short name) and their converted vote factors; never null. The exhibit set is those that have been voted for or against, possibly including no-longer valid/extant exhibit names, because we will be using this for calibration.

Private to getVotedForExhibits().

We index from the time at which we gathered the set so that we can regenerate or trim this list if the aep or event slot changes.

Because the (first) map is sorted it is quick to find the latest/oldest entries.

Usually we only keep one value (the latest one), and any older values are purged only AFTER a new value has been inserted, ie this map never becomes transiently empty nor more stale than necessary once non-empty.

We can keep older information around to allow some (stale) results to be computed even if we cannot immediately fetch new information.

The outer and inner maps are thread-safe.

Do not assume that other activity in this collection can be locked out by holding a lock on this object. DO NOT hold a lock on this object!

The values must be immutable to enable them to be shared safely without copying.

TODO: upgrade to ConcurrentNavigableMap under JDK 1.6 to improve concurrency.

fixedSimpleScorers

public static final java.util.Map<java.lang.String,ScorerIF> fixedSimpleScorers

The (small) immutable current fixed set of parameterless base Scorer instances. Note that since these are fixed and immutable and have no parameters, we can safely create and store instances here.

These include the test/bogus Scorers as well as the live Scorers.

MIN_VOTED_FOR_SET_SIZE

static final int MIN_VOTED_FOR_SET_SIZE

Minimum desireable site of set of voted-for exhibits for calibration to be fully confident of the result; strictly positive. This may determine the sizing of various memory structures.

See Also:

Constant Field Values

MAX_ECS_ITERATIONS

private static final int MAX_ECS_ITERATIONS

Iterations allowed in extractCalibrationSet() to try to find an optimal result; strictly positive. This should probably be at least 3 or 4; and can much higher if calculation is quick.

See Also:

Constant Field Values

STATISTICAL_SCORER_SAMPLING_CCS

private static final boolean STATISTICAL_SCORER_SAMPLING_CCS

If true then select a partly-random selection of Scorers to measure error in _computeCalibrationSetError().

See Also:

Constant Field Values

MAX_SCORER_SAMPLE_SIZE_CCS

private static final int MAX_SCORER_SAMPLE_SIZE_CCS

Max Scorer sample size in _computeCalibrationSetError() to prevent overflow in calculations.

See Also:

Constant Field Values

_eCS_cache

private final MemoryTools.SimpleLRUMap<Tuple.Triple<java.lang.String,java.lang.Integer,java.lang.Boolean>,Tuple.Pair<java.lang.Long,java.util.Map<java.lang.String,ScoreAndConf>>> _eCS_cache

Private cache for extractCalibrationSet(); never null. Thread-safe LRU cache with capped size.

Map from (effectively) basename/size/errors to a calibration set and its time of computation.

The size parameter is the largest (non-negative) power of two no higher than the request size (its rounded-down log to the base 2), thus mapping arbitrary requested maximum sizes to a smaller number of powers of two. (Note that this mapping may be further conflated/condensed to improve the cache effectiveness.)

scorerWork

private final ScorerCreator.ScorerWork scorerWork

Scorer work object; never null.

APPROX_POLL_CYCLE_MS

private static final int APPROX_POLL_CYCLE_MS

Expected approximate poll cycle time (ms); strictly positive.

See Also:

Constant Field Values

inboundScorerQueue

private final java.util.concurrent.ArrayBlockingQueue<java.lang.String> inboundScorerQueue

Thread-safe, bounded size, queue for inbound Scorers; never null. The upper bound on size should usually be set to be a small fraction of population size on the grounds that we are unlikely to be able to quickly accept a large volume of new entrants in any sensible way.

ScorerCacheImpl

public ScorerCacheImpl(SimpleExhibitPipelineIF dataSource,
                       SimpleLoggerIF log)

Construct an instance attached to the supplied data source. We automatically record/persist/share new best-of-breed Scorers via the even mechanism

Parameters:

dataSource - full-access live data source; must not be null

computeCompositeScoreAndConfidence

public ScoreAndConf computeCompositeScoreAndConfidence(java.lang.String exhibitName,
                                                       boolean allowStale)
                                                throws java.io.IOException

Computes a weighted composite score [-1,+1] and confidence [0,+1] for the specified exhibit with the best available scorers/parameters; never null but may be (0,0). This uses the Scorers available from getCurrentScorersWithParameters(), but skipping any marked as BadScorer that have made it through filtering.

This explicitly limits the time it spends on computation, more so if the system is short of power.

This tries to force the evolution of new Scorers in the background if it finds none at all useable during filtering and computation. (This means that the Scorer system can bootstrap itself just by calls to this routine, but will force some possibly-wasteful work for exhibit types that cannot be scored.)

Specified by:

computeCompositeScoreAndConfidence in interface ScorerCacheIF

Parameters:

exhibitName - valid full exhibit name

allowStale - if true then allow a stale value from cache, else throw an exception if nothing is currently available

Returns:

(0,0) if named scorer is not available, cannot be used with the specified parameters, or cannot be applied to the indicated exhibit (eg because of the exhibit type or the exhibit does not exist); else returns a non-null ScoreAndConf value

Throws:

java.io.IOException

computeScorerWeighting

public ScoreAndConf computeScorerWeighting(ScorerIF scorer,
                                           boolean allowStale,
                                           java.lang.String source)
                                    throws java.io.IOException

ScoreAndConfidence for the given scorer itself over all exhibit types; never null but may be (0,0) where the scorer is unknown or untested. Essentially the result of this should be multiplied by the result for each exhibit (for the same scorer and parameters) to normalise the predicted score and confidence for the exhibit, though usually the sign of the correlation (score) is multiplied into the raw score, while the value of correlation (score) is multiplied with the confidence into the final confidence.

We attempt to ignore small numbers of errors for robustness.

Specified by:

computeScorerWeighting in interface ScorerCacheIF

Parameters:

allowStale - if true then allow a stale or low-confidence value from cache, else throw an exception if nothing is currently available and we cannot quickly compute enough points to increase our confidence

scorer - instance of the Scorer; never null

source - the name of the mechanism used to generate this Scorer value, or null if none

Returns:

the score represents the correlation with the underlying votes (and whatever the scoring is measured against) with MAX meaning perfect correlation, 0 meaning no correlation, and -MAX meaning perfectly wrong answers all the time, and the confidence 0 if we have no (or very/too few) data points and approaching MAX as we have a large (enough) number of data points

Throws:

java.io.IOException

computeRawVotedForExhibits

private Tuple.Pair<java.lang.Long,java.util.Set<java.lang.String>> computeRawVotedForExhibits(SimpleVariablePipelineIF vars)
                                                                                       throws java.io.IOException

Compute voted-for-exhibit set; never null but may be empty. This attempts to retrieve the latest vote event sets for all or most time slots (concentrating on more recent ones if necessary) and computes the set of all exhibits that have a vote.

This does NOT attempt to filter the result in any way, ie by which exhibits are still live or even syntactically-valid.

Returns:

the (non-null, possibly empty) set of voted-for-exhibits up to the last full VLONG slot paired with the time at which we started to compute/fetch it

Throws:

java.io.IOException - if the data is not available or there is a timeout

getVotedForExhibitsAndVoteFactors

private java.util.Map<java.lang.String,ScoreAndConf> getVotedForExhibitsAndVoteFactors(SimpleExhibitPipelineIF dataSource,
                                                                                       boolean allowStale)
                                                                                throws java.io.IOException

Get latest (immutable) Map of all voted-for exhibits (by short name) to vote score; never null. Returns a set of extant exhibits that have been voted for or against.

Uses a cache to avoid wasted computation from one event tick to the next, and to allow this mechanism to work even in the face of brief outages in data connectivity (eg when trying to fetch new values of the vote events).

We convert the vote Factor to a ScoreAndConf value so that more computations can be done as integer rather than floating, especially important for Niagara.

Parameters:

dataSource - event source for fetching event set if necessary; never null

allowStale - if true, allow older data to be returned to save time, or if new event data should be used but cannot be fetched (ie allow working from stale event data for speed and/or robustness)

Throws:

java.io.IOException

getBaseScorersWithoutParameters

public java.util.Set<java.lang.String> getBaseScorersWithoutParameters()

Base set of available Scorers' names (no parameters); never null but may be empty. The values returned are of the form ScorerName.

Specified by:

getBaseScorersWithoutParameters in interface ScorerCacheIF

getBaseScorerByName

public ScorerIF getBaseScorerByName(java.lang.String baseName)

Get base non-parameterised Scorer by name; null if no such base Scorer supported.

Specified by:

getBaseScorerByName in interface ScorerCacheIF

Parameters:

baseName - base (no parameters) name of Scorer; must not be null

_computeCalibrationSetError

private int _computeCalibrationSetError(java.util.Map<java.lang.String,ScoreAndConf> putativeCalibrationExhibits,
                                        java.util.List<java.lang.String> breedingSet,
                                        java.util.concurrent.ConcurrentMap<java.lang.String,java.util.concurrent.ConcurrentMap<java.lang.String,ScoreAndConf>> workspace)
                                 throws java.io.IOException

Compute 'error' in calibration set for the given population and cache contents; non-negative. This regards a computed calibration set as 'perfect' (zero error) if:

• It predicts the same Scorers in the same order for the given basename (or with the same composite score if the supplied base name is null). We will generally take a sampling of Scorers of similar size to the calibration exhibit set.
• It marks the best Scorer as the best (or very nearly so), ie so that anything that seems better than the 'best' Scorer by the computed set will very likely prove to be so when measured against the full set.

This implicitly assumes that using the population ranking/comparator is the same as calibrating against the input calibration data (though that may prove false for stale cache values, etc). This avoids potentially-expensive recomputation against all input data.

Note that nothinf is ever removed from the workspace (if supplied) making it (thread-) safe to share even between concurrent calls, but meaning also that its data may be bulky and get stale if preserved longer than the call to extract one calibration set. Use of this retained workspace should however save a great dea of time.

Parameters:

putativeCalibrationExhibits - map of proposed exhibits for calibration set to their real original input data (eg votes); never null nor empty

breedingSet - set of 'best' Scorers (of a single base type) or null for a generic set; never empty

workspace - if non-null then this is some workspace opaque to the caller that can be used to save some results from one call to the next (or even between concurrent calls, though this may not be efficient) while evaluating the error for a single calibration set; the caller must not alter this object

Returns:

zero for an apparently 'perfect' computed calibration set, with increasingly positive values for increasingly-badly-performing computed calibration sets

Throws:

java.io.IOException

extractCalibrationSet

public java.util.Map<java.lang.String,ScoreAndConf> extractCalibrationSet(java.lang.String baseName,
                                                                          int maxSamples,
                                                                          java.lang.Boolean difficult,
                                                                          boolean allowStale)
                                                                   throws java.io.IOException

Compute exemplar exhibit sub-set to calibrate Scorers with given base name against; never null but may be empty. This implementation extracts the best available Scorer of the given base name (if any) and finds some of the exhibits that it best predicts and worst predicts and an even sampling of those in between and some random samplings of that median range. The result should usually be a result for which the weighting of the selected Scorer may be reasonably close to zero or to the mean of its accuracy range.

This may return an empty result if there is not enough data to calibrate against, eg human-case votes.

It may be possible to tune or pre-test new Scorers against the results of this as a fast filter.

If a base name is specified that is invalid, it is treated as if null.

We may cache generated results for a short while since this extraction may be expensive, though the cache time is of the order of minutes rather than the day or so elsewhere.

Specified by:

extractCalibrationSet in interface ScorerCacheIF

Parameters:

baseName - base name of Scorer to extract calibration set for, or null for a generic all-Scorers calibration set

maxSamples - the maximum number of samples to return; strictly positive

difficult - if TRUE the return the difficult cases that we do not predict well, if FALSE then return the easy cases that we predict well, else return a mixure of good, bad, and other random cases

allowStale - if true then allow slightly older data for speed and robustness

Returns:

map of zero-or-more exhibits (short names) to calibration-data values; non-null

Throws:

java.io.IOException

evolve

private void evolve(boolean minimal)

Do some 'evolution' in a background thread if possible. If we have too much background activity going on this will do nothing.

This routine always returns quickly.

This should never throw any exceptions.

Parameters:

minimal - if true, run as short a time as possible to make some progress

poll

public final void poll()
                throws java.io.IOException

Called/polled periodically (of the order of 1Hz) to do donkey-work and background tasks. In particular, this call drives the search for improved Scorers, as well as performing housekeeping and maintaining caches to speed foreground tasks.

This launches its work in a low-priority daemon thread, and limits the number of such concurrent work threads globally by silently discarding any excess, ie this call always returns quickly.

This routine should not be called (often) if the host system is under heavy load.

Throws:

java.io.IOException

offerExternalScorer

public boolean offerExternalScorer(java.lang.String externalScorerNameAndParameters)

Attempt to queue an externally-supplied Scorer value; returns true if accepted. This attempts to save the value supplied in our internal bounded-size queue.

Note that this accepts (and discards) anything which is definitely never usable, eg syntactically invalid or not for a valid Scorer base name, so as to help conserve resources such as memory and queue space.

This routine should always be relatively quick/efficient; much more work is performed when an item is dequeued, presumably when we know that we have ample resources available.

This may try to start some work immediately if the queue is now getting full.

Should not throw any exceptions; invalid Scorer values are simply discarded with true returned.

Specified by:

offerExternalScorer in interface ScorerCacheIF

Overrides:

offerExternalScorer in class AbstractScorerCache

canAcceptMoreExternalScorers

public boolean canAcceptMoreExternalScorers()

Returns true if this cache can definitely accept (many) more externally-supplied Scorer values. Even if this returns false we may in practice be able to accept one or more new values: this is indicative.

True if our internal queue is at most about half full, but not any sort of guarantee that we can actually accept another Scorer.

In power-conserving mode only welcome new entries if the queue is currently empty, ie if we seem to be keeping up with any data coming in. This is important because this call can be used to decide when to hand out new work to clients, from which the results will arrive only much later.

Specified by:

canAcceptMoreExternalScorers in interface ScorerCacheIF

Overrides:

canAcceptMoreExternalScorers in class AbstractScorerCache

hasQueuedExternalScorer

public boolean hasQueuedExternalScorer()

Returns true if at least once external Scorer is queued waiting to be processed.

Specified by:

hasQueuedExternalScorer in interface ScorerCacheIF

Overrides:

hasQueuedExternalScorer in class AbstractScorerCache