- Moved arguments and expected result values for special function tests from inlined code to csv files.
- Added a python script to compute expected result values for tested special functions in high precision.
- Improved accuracy of NormalCdfLn for `x < -8`. Truncated series was too short, test used to pass, because the expected value itself was incorrect.
* Update to .NET Core 3.1
This update was faily trivial change of project properties with only one caveat
```
error CS0104: 'Range' is an ambiguous reference between 'Microsoft.ML.Probabilistic.Models.Range' and 'System.Range'
```
which require sprinkling everywhere following line of code
```
using Range = Microsoft.ML.Probabilistic.Models.Range;
```
* Update build definition to use more modern images
- Windows 2019 for .NET Core 3.1
- Mac OS 10.14 (Specifically https://docs.microsoft.com/en-us/azure/devops/pipelines/agents/hosted?view=azure-devops)
Co-authored-by: Tom Minka <8955276+tminka@users.noreply.github.com>
It really is not required - at all points it is known with which automaton we operate right now.
Also, where only state index was needed we store now the int index instead of fat State object
which contains extra information.
Contracts has been changed: `TryEnumerateSupport()` does not throw if it encounters non-enumerable automata.
- Implementation of `TryEnumerateSupport` was changed a lot:
- It avoids recursion (and "stacked IEnumerables")
- An optimization has been added - traversing states with single point-mass forward transition
(90+% of real-world cases) is cheaper, because it avoids some extra allocations
Also "is enumerable" status is cached. It is set proactively at automaton construction
in 2 common cases which are cheap to detect:
- automaton with self-loops can not be enumerated
- automaton with only forward transitions (and thus no loops) can always be enumerated
In all other cases this flag is calculated lazily on first enumeration try.
`System.Collections.Immutable` has `ImmutableArray` that serves the same purpose as
`ReadOnlyArray` but has different API. This type is available (without extra dependencies)
only in netcore, so can't be used in Infer.NET which has to support netframework.
Until netframework support can be dropped reimplement a subset of `ImmutableArray`
in Infer.NET codebase.
* Python tool to generate expressions for truncated series.
* Using the generated series in special functions
* Test projects set Optimize=true in Release configuration
Co-authored-by: Tom Minka <8955276+tminka@users.noreply.github.com>
Fixed an issue where DependencyAnalysisTransform would give incorrect SkipIfUniform dependencies, causing statements to be incorrectly pruned from the generated code.
Removed FactorManager.AnyItem. Added FactorManager.All.
GaussianProductOp.AAverageConditional handles uniform B.
MMath.ChooseLn handles more cases.
- Introduced an abstraction for truncated power series
- Introduced an abstraction for power series
- Made [Di|Tri|Tetra]Gamma[Ln] use it
- Added internal interface to recompute power series used in MMath and make them longer/shorter depending on the necessary precision. It can be used in tests.
Currently, power series computation is rather primitive (cut-off some precomputed series at a point where it used to be cut as long as the precision in <= 53, don't cut-off otherwise).
o Marked each non-packing assembly as "IsPackage=false" because the default is to package the assemblies. Done this via a common.props import.
o Switched to using integrated CSProj NuGet properties. Done this via a nuget-properties.props import.
o Switched to using msbuild in release.yml rather than nuget, since nuget.exe does not support the new spec.
o Added a LearnersNuGet project to be the "csproj" host for the learners nuspec (since the learners nuget does not correspond to any particular existing csproj project).
o Updated ClickThroughModel.csproj and ClinicalTrial.csproj and Image_Classifier.cs and MontyHall.csproj to new-style csprojs because otherwise new msbuild commands reject them.
o Made release.yml msbuild calls multiprocess to speed them up.
o Factored out some common properties into the common.props file.
GammaPower creates a point mass whenever Rate would be infinite.
Added GammaPower.FromMeanAndMeanLog.
Improved numerical accuracy of GammaPower.GetLogProb, GetMean, and GetMode.
Added GammaPowerEstimator
GammaProductOp supports GammaPower distributions.
GammaProductOp handles uniform message from product.
Added GammaPowerProductOp_Laplace
Fixed PowerOp for GammaPower distributions.
Added PlusGammaOp for GammaPower distributions.
MMath.GammaUpper has an unregularized option.
Added TruncatedGamma.GetMeanPower.
PowerOp supports TruncatedGamma.
Swapped the argument order of (internal) MMath.LargestDoubleProduct and LargestDoubleRatio.
UnlimitedStatesComputation() is used temporary to alter maximal size of automaton
which is defined my MaxStateCount. Using it from different threads could mess up the limit.
Now each threads gets its own limit.
Also, the default MaxStateCount limit is increased to 300k, because that is what the biggest String inference customer uses.
After recent refactoring that removed `ProbabilityOutsideRanges`, `DiscreteChar.Complement()`
started to work incorrectly in case ranges were going one after another.
For example DiscreteChar.Point('\0').Complement() was equal to uniform distribution, i.e. still included the \0 char.
Automaton determinization procedure used to keep a running total of weights for each state.
That sum was maintained by adding weights for next open segment and substracting weights
for closed segments. If the weights of segments differ a lot (LogValue difference is bigger than 100)
than due to numerical issues sum could become zero after subtraction which lead to dropping
of transition and automaton language truncation.
Now the weights sum is recalculated from scratch each time. It also results in loss of precision,
but it is important that the precision is lost only for very large weights, not very small ones. So
no accidental zeroing of weights is happening and language is not truncated.
It doesn't really impact runtime because `WeightedStateSet` construction enumerated all weights
anyway (to normalize them), so in the worst case slowdown is at most constant.
And in average case (where we maintain 1 or 2 destination states per transition) the runtime
is actually better due to lower constant costs.
New test (`AutomatonTests.Determinize11`) was added, it used to fail with previous implementation.
To make this change I had to rewrite code substantially which in my opinion makes it easier to follow:
- The determinization procedure now makes use of `CharSegmentsEnumerator` helper class
which enumerates over all char segments from multiple char distributions. These segments are
non-overlapping.
- `WeightedStateSetBuilder` now handles duplicate state indices in `Add()` call. Previously deduplication
had to happen via accumulating sum in `Dictionary<int, WeightSum>`
Fixed corner cases in MMath.LargestDoubleProduct and NormalCdfIntegral.
Improved accuracy of DoubleIsBetweenOp.
Loosened the tolerance of GaussianIsBetweenCRCC_IsMonotonicInXMean and GaussianIsBetweenCRCC_IsMonotonicInXPrecision, to be fixed later.
Fixed cases where MMath.NormalCdf, DoubleIsBetweenOp, IsPositiveOp, DoublePlusOp would throw.
JaggedSubarrayOp uses ForceProper.
PlusDoubleOp gracefully handles improper distributions on input.
Added MMath.NormalCdfIntegral, NormalCdfDiff, NormalCdfExtended.
Added ExtendedDouble class.
MeanVarianceAccumulator correctly handles weight=0.
Region.GetLogVolume has a lower bound.
Variables with PointEstimate do not use JaggedSubarrayWithMarginal.
Due to refactoring mistake `sampleProb / prob * intervalLength`
turned into `sampleProb / (prob * intervalLength)` which is obviosly incorrect.
Fixed that + added a rudimentary test for `DiscreteChar.Sample()`
Made `ArgumentCountToNames` cache thread-safety.
After that another exception appeared with `ArgsToValidatingAutomaton` dictionary (reference null exception). Making the dictionary concurrent fixed this error.
* Determinization doesn't change language of the automaton anymore.
2 new tests were added which check that it doesn't happen.
Previously all very low probability transitions (with probability of less than e^-35) were removed.
That was done because of 2 reasons:
- some probabilities were represented in linear space. And e^-35 is as low resolution
as you can get with regular doubles. (That is, if one probability = 1 and another is e^-35,
then when you add them together, second one is indistinguishable from zero).
This was fixed when discrete charprobabilities
- Trying to determinize some non-determinizable automata lead to explosion of low-probability
states and transitions which led to a very poor performance.
(E.g. `AutomatonNormalizationPerformance3` test). Now a smarter strategy for detecting
these non-determinizable automata is used - during traversal all sets of states from root
are remembered. If automaton comes to the same set of states but with different weights
than it stops immediately, because otherwise it will be caught in infinite loop
* `Equals()` and `GetHashCode()` for `WeightedStateSet` take into account only high 32 bits of weight.
This coupled with normalization of weights allows to reuse already added states with
very close weights. This speeds up the "PropertyInferencePerformanceTest" 2.5x due to
smaller intermediate automata.
* Weighted sets of size one are handled specially in `TryDeterminize` - they don't need to be
determinized and can be copied into result almost as is. (Unless they have non-deterministic
transitions. Simple heuristic of "has different destination states" is used to detect that
and fallback to slow general path).
* Representation for `WeightedStateSet` is changed from (int -> float) dictionary to
sorted array of (int, float) pairs. As an optimization, a common case of single-element
set does not allocate any arrays.
* Determinization code for `ListAutomaton` was removed, because it has never worked
Transition weights may become infinite when going from log space into value space. And
`SetToSum()` which is used by `MergerParallelTransitions` can't handle 2 inifnite weights at once.
To solve this, transitions weights are normalized by max weight prior to passing into `SetToSum()`
* Pair (FirstTranstiionIndex, LastTransitionIndex) changed to pair
(FirstTransitionIndex, TransitionsCount).
* Introduced Automaton.Builder.LinkedStateData struct which
mirrors Automaton.StateData but represents transitions as linked list.
Previously Automaton.StateData was reused for this purpose.
That was confusing.
In some edge cases StringAutomaton needs to represent extremely
low probabilities of character transitions. To be able to do that,
instead of storing probabilities as double values they are stored
as `Weight` structs already used by automatons. Weight stores logarithm
of value instead of value itself.
TryDeterminized() tried to do something even if it is known that automaton is already determinized
or non-determinizable.
Because automaton state is immutable, it is possible to store determinization state alongside with it.
There are 3 states:
* Unknown - TryDeterminize() was never called for this automaton
* IsDeterminized - TryDeterminized() successfully determinized automaton
* IsNonDeterminizable - TryDeterminize() was called but didn't succeed.
Because determinization state depends on maximum number of states,
`TryDeterminize(int maxStatesCount)` method was removed in favour of using defaults.
Because this overload was never used in practice.
Also, as an implementation detail an enum type was exposed as part of automaton quoting interface.
Compiler generated incorrect C# code for quoting enum constants. Fixed that.
We finally reached a point where automatons are big enough that recursive implementations
of algorithms fail with `StackOverflowException`.
There are 4 tests which test operations with big automatons (100k states):
* `TryComputePointLargeAutomaton`
* `SetToProductLargeAutomaton`
* `GetLogNormalizerLargeAutomaton`
* `ProjectSourceLargeAutomaton`
All four used to fail before code was rewritten to use explicit stack instead of recursive calls.
All changes except one didn't change algorithms used, code was almost mechanically changed
to use stack.
The only exception - automaton simplification. Old code used recursion in very non-trivial way.
It was rewritten from scratch, using different algorithm: instead of extraction of generalized
sequences and then reinserting them back new code merges states directly in automaton.
(There's a comment at the beginning of Simplify() method explaining all operations)
To reduce memory pressure automaton data (states and transitions) was
converted from classess to structs and "vectorized" into just two large arrays.
Now, one state costs just 16 bytes and one transition costs 24 bytes.
Previously cost was at least twice of that, due to additional indirection,
object headers and pre-reservation of arrays capacity: 8 bytes pre reference
to state + 16 bytes per state header + 24 bytes per transitions array per state).
In practice memory consumption by automatons was reduced approximately
by the factor of 3.
Important changes:
* `Automaton.StateData` is now a struct instead of class.
* All transitions of automaton are stored in single array instead of
"transition array per state"
* Automatons can not be mutated. All immutable data was moved
to new `DataContainer` struct.
* New Automaton.Builder class was introduces for construction
of new automatons from scratch. All mutation is done through
"copy to builder, mutate, get immutable data" pattern.
* Widely used `AppendInPlace()` method is not actually inplace anymore
and became way more expensive. Multiple `AppendInPlace()` calls
should be replaced with 1 `Automaton.Builder` instance with
multiple `Builder.Append()` calls. Places which were hot in profiler were rewritten.
`AppendInPlace()` will be removed completely in separate pull-request.
Technical changes:
* `Optional<>` struct was moved into Containers namespace. Logically it is
a container of "0-or-1" elements.
* To enforce immutable data-structures new `ReadOnlyArray`, `ReadOnlyArraySegment`
and `ReadOnlyArraySegment` enumerator structs were introduced. They wrap regular
arrays but do not allow to mutate them. Unlike `ReadOnlyList<>` these are value types
and do not introduce any memory-costs.
* In quite a few places Tuples were replaced with ValueTuples.
* Most recursive helper methods were "inlined" as local functions at their call-sites.
Not strictly necessary, but mady refactoring a lot easier by bringing related code together.
* Some code was reformated/updated to more modern style. Either by tooling or manually.
* Softmax factor throws when output is observed under VMP.
* VectorSoftmaxOp_KM11.XAverageLogarithm allows softmax to be a point mass as long as some x[i] is a point mass.
Fixes#101
* Added IrregularQuantiles
* IrregularQuantiles throws ArgumentOutOfRangeException
* Added Region.Equals and CompareTo
* BlogTests.Handedness is a test
* BallCountingTest comment
* More documentation and testing
Automatons didn't support value types for TElementDistribution because they used
null values as a sentinel for epsilon transitions. PairDistributions (and Transducers)
didn't support them because one element of pair can be null.
General idea of this PR: wrap distributions into a struct that can answer if it's value is null.
Like `Nullable<T>` but also suitable for reference types.
Changes done:
1. `Utilities.Option<T>` is introduced. It behaves like `Nullable<T>` but can be constructed
from (null) references. It has the same guarantee - if `HasValue` returns true then
`Value` is guaranteed to return valid non-null result.
2. `Argument.CheckIfNotNull` can have value type as a generic parameter. Obviosly
for value types this function is a no-op. But it allows to write generic code that
checks if argument is not null if it is a reference type, and does not check anything
otherwise.
3. `Utilities.Option<T>` is used everywhere in `Automaton` interfaces. But the
`ElementDistribution` inside `Automaton.Transition` is stored as 2 fields:
`hasElementDistribution` and `elementDistribution`. Due to careful structure
layout (`hasElementDistribution` is packed with `group` field), this takes
8 bytes less space then simple `Option<TElementDistribution>`.
All these changes are done with single purpose - to convert DiscreteChar from class
to struct. That saves 24 bytes per transition in StringAutomaton. That is a lot.
Benchmarking shows no performance penalty for introducing Optional<>.
JIT does a good job of optimizing it away.
Owner and Index properties bring 2 issues:
1. They were taking 16 bytes (after aligning everything)
2. They complicate serialization due to cyclic references
Changes made:
1. State class is split in 2 parts: StateData and State. StateData is stored inside Automaton, State is created on demand and acts as a fat-reference to which allows to read/modify StateData that it references and carries around additional properties - Owner and Index.
2. Introduced StateCollection class which wraps List<StateData> and acts like ReadOnlyList<State> but does StateData to State conversion on demand
C# compiler and .NET runtime are good at optimizing away all StateData->State wrapping. No performance degradation was measured in my tests.
Binary serialization remains backward-compatible, but JSON/BinaryFormatter/DataContract ones are changed.
Added CausalityExample, Crowdsourcing, and CrowdsourcingWithWords examples from the user guide.
Modernized the BayesianPCA example.
Example projects that support .NET Core now build under DebugCore and ReleaseCore.
Removed spurious app.config files.
Fixed EndCoupledChainsTest2.
Added MMath.NextDouble and PreviousDouble.
Split up EpTests.
Added Hidden attributes to factors that should not appear in Factor Manager.
HtmlTransformChainView shows errors.
README clarifies that Mono is optional.
Ivan Korostelev
msdmkats
Tom Minka
Andrey Kurdyumov
Jonathan Tims
Jonathan Tims
John Guiver
Ivan Korostelev
Elena Pochernina
Vijay
Vijay Sharma
msdmkats
Mikhail
Yordan Zaykov
Sergey B. Berezin
dotnet-bot