tspooner / lfa / 102

pending completion

Build # 102

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #17 from tspooner/ft-serde

New manifest feature: "serialize"

Run Details

19 of 19 new or added lines in 15 files covered. (100.0%)

1313 of 1748 relevant lines covered (75.11%)

0.75 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

80.49

/src/basis/ifdd.rs

use crate::{
    basis::Projector,
    core::*,
    geometry::{Card, Space, Vector},
};
use itertools::Itertools;
use std::{
    cmp::Ordering,
    collections::HashMap,
    hash::{Hash, Hasher},
};

#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Feature {
    pub index: usize,
    pub parent_indices: IndexSet,
}

impl Feature {
    pub fn union(&self, other: &Self) -> IndexSet {
        let g = &self.parent_indices;
        let h = &other.parent_indices;

        g.union(h).cloned().collect()
    }
}

impl Hash for Feature {
    fn hash<H: Hasher>(&self, state: &mut H) { self.index.hash(state); }
}

#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct CandidateFeature {
    pub relevance: f64,
    pub parent_indices: IndexSet,
}

impl CandidateFeature {
    pub fn new<T: Into<IndexSet>>(parent_indices: T) -> Self {
        CandidateFeature {
            relevance: 0.0,
            parent_indices: parent_indices.into(),
        }
    }

    pub fn from_vec(index_vec: Vec<usize>) -> Self {
        let mut parent_indices = IndexSet::new();

        for i in index_vec {
            parent_indices.insert(i);
        }

        CandidateFeature::new(parent_indices)
    }

    pub fn into_feature(self, index: usize) -> Feature {
        Feature {
            index: index,
            parent_indices: self.parent_indices,
        }
    }
}

impl Hash for CandidateFeature {
    fn hash<H: Hasher>(&self, state: &mut H) { self.parent_indices.hash(state); }
}

impl PartialOrd for CandidateFeature {
    fn partial_cmp(&self, other: &CandidateFeature) -> Option<Ordering> {
        self.relevance.partial_cmp(&other.relevance)
    }
}

#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
#[derive(Clone, Debug)]
pub struct IFDD<P> {
    pub base: P,
    pub features: Vec<Feature>,

    candidates: HashMap<IndexSet, CandidateFeature>,
    discovery_threshold: f64,
}

impl<P: Space> IFDD<P> {
    pub fn new(base_projector: P, discovery_threshold: f64) -> Self {
        let initial_dim: usize = base_projector.dim();
        let mut base_features: Vec<Feature> = (0..initial_dim)
            .map(|i| Feature {
                index: i,
                parent_indices: {
                    let mut index_set = IndexSet::new();
                    index_set.insert(i);
                    index_set
                },
            })
            .collect();

        base_features.reserve(initial_dim);

        IFDD {
            base: base_projector,

            features: base_features,
            candidates: HashMap::new(),

            discovery_threshold: discovery_threshold,
        }
    }

    #[inline]
    fn inspect_candidate(&mut self, g: usize, h: usize, error: f64) -> Option<CandidateFeature> {
        let key = self.features[g].union(&self.features[h]);
        let rel = {
            let c = self
                .candidates
                .entry(key.clone())
                .or_insert_with(|| CandidateFeature::new(key.clone()));

            c.relevance += error.abs();

            c.relevance
        };

        if rel >= self.discovery_threshold {
            Some(self.candidates.remove(&key).unwrap())
        } else {
            None
        }
    }

    #[inline]
    fn discover_dense(&mut self, phi: Vector<f64>, error: f64) -> Vec<CandidateFeature> {
        (0..phi.len())
            .filter(|&i| phi[i].abs() < 1e-7)
            .combinations(2)
            .filter_map(|indices| self.inspect_candidate(indices[0], indices[1], error))
            .collect()
    }

    #[inline]
    fn discover_sparse(&mut self, active_indices: IndexSet, error: f64) -> Vec<CandidateFeature> {
        active_indices
            .iter()
            .tuple_combinations()
            .filter_map(|(&g, &h)| self.inspect_candidate(g, h, error))
            .collect()
    }

    fn add_feature(&mut self, candidate: CandidateFeature) -> Option<(usize, IndexSet)> {
        let idx = self.features.len();
        let feature = candidate.into_feature(idx);
        let mapping = (idx, feature.parent_indices.clone());

        self.features.push(feature);

        Some(mapping)
    }
}

impl<P> IFDD<P> {
    fn discover<I>(&mut self, input: &I, error: f64) -> Option<HashMap<IndexT, IndexSet>>
    where
        I: ?Sized,
        P: Projector<I>
    {
        let new_features = match self.base.project(input) {
            Features::Sparse(active_indices) => self.discover_sparse(active_indices, error),
            Features::Dense(activations) => self.discover_dense(activations, error),
        };

        self.features.reserve_exact(new_features.len());

        new_features.into_iter().fold(None, |mut acc, f| {
            match self.add_feature(f) {
                Some(nf) => {
                    acc.get_or_insert_with(HashMap::new).insert(nf.0, nf.1);
                },
                None => (),
            };

            acc
        })
    }
}

impl<P: Space> Space for IFDD<P> {
    type Value = Features;

    fn dim(&self) -> usize { self.features.len() }

    fn card(&self) -> Card { unimplemented!() }
}

impl<I: ?Sized, P: Projector<I>> Projector<I> for IFDD<P> {
    fn project(&self, input: &I) -> Features {
        let mut p = self.base.project(input);
        let np: Vec<usize> = (self.base.dim()..self.dim())
            .filter_map(|i| {
                let f = &self.features[i];

                if f.parent_indices.iter().all(|i| p[*i].abs() < 1e-7) {
                    Some(i)
                } else {
                    None
                }
            })
            .collect();

        for i in np.iter() {
            for j in self.features[*i].parent_indices.iter() {
                p.remove(*j)
            }
        }

        p + np.into()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::basis::ifdd::IFDD;

    #[derive(Clone)]
    struct BaseProjector;

    impl Space for BaseProjector {
        type Value = Features;

        fn dim(&self) -> usize { 5 }

        fn card(&self) -> Card { unimplemented!() }
    }

    impl Projector<[f64]> for BaseProjector {
        fn project(&self, input: &[f64]) -> Features {
            input
                .iter()
                .map(|v| v.round().min(4.0).max(0.0) as usize)
                .collect()
        }
    }

    #[test]
    fn test_discover() {
        let mut f = IFDD::new(BaseProjector, 10.0);

        assert_eq!(
            f.discover(&vec![0.0, 4.0], 10.0),
            Some({
                let mut hm = HashMap::new();
                hm.insert(5, [0, 4].iter().cloned().collect());
                hm
            })
        );
        assert_eq!(
            f.features[5],
            Feature {
                index: 5,
                parent_indices: [0, 4].iter().cloned().collect(),
            }
        );

        assert_eq!(f.discover(&vec![0.0, 3.0], 5.0), None);
        assert_eq!(f.features.len(), 6);

        assert_eq!(
            f.discover(&vec![0.0, 3.0], 5.0),
            Some({
                let mut hm = HashMap::new();
                hm.insert(6, [0, 3].iter().cloned().collect());
                hm
            })
        );
        assert_eq!(
            f.features[6],
            Feature {
                index: 6,
                parent_indices: [0, 3].iter().cloned().collect(),
            }
        );
    }
}

1	use crate::{
2	basis::Projector,
3	core::*,
4	geometry::{Card, Space, Vector},
5	};
6	use itertools::Itertools;
7	use std::{
8	cmp::Ordering,
9	collections::HashMap,
10	hash::{Hash, Hasher},
11	};
12
13	#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
14	#[derive(Clone, Debug, PartialEq, Eq)]	1✔
15	pub struct Feature {
16	pub index: usize,	1✔
17	pub parent_indices: IndexSet,	1✔
18	}
19
20	impl Feature {
21	pub fn union(&self, other: &Self) -> IndexSet {	1✔
22	let g = &self.parent_indices;	1✔
23	let h = &other.parent_indices;	1✔
24
25	g.union(h).cloned().collect()	1✔
26	}	1✔
27	}
28
29	impl Hash for Feature {
30	fn hash<H: Hasher>(&self, state: &mut H) { self.index.hash(state); }
31	}
32
33	#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
34	#[derive(Clone, Debug, PartialEq)]	×
35	pub struct CandidateFeature {
36	pub relevance: f64,	×
37	pub parent_indices: IndexSet,	×
38	}
39
40	impl CandidateFeature {
41	pub fn new<T: Into<IndexSet>>(parent_indices: T) -> Self {	1✔
42	CandidateFeature {	1✔
43	relevance: 0.0,
44	parent_indices: parent_indices.into(),	1✔
45	}
46	}	1✔
47
48	pub fn from_vec(index_vec: Vec<usize>) -> Self {	×
49	let mut parent_indices = IndexSet::new();	×
50
51	for i in index_vec {	×
52	parent_indices.insert(i);	×
53	}
54
55	CandidateFeature::new(parent_indices)	×
56	}	×
57
58	pub fn into_feature(self, index: usize) -> Feature {	1✔
59	Feature {	1✔
60	index: index,	1✔
61	parent_indices: self.parent_indices,	1✔
62	}
63	}	1✔
64	}
65
66	impl Hash for CandidateFeature {
67	fn hash<H: Hasher>(&self, state: &mut H) { self.parent_indices.hash(state); }
68	}
69
70	impl PartialOrd for CandidateFeature {
71	fn partial_cmp(&self, other: &CandidateFeature) -> Option<Ordering> {	×
72	self.relevance.partial_cmp(&other.relevance)	×
73	}	×
74	}
75
76	#[cfg_attr(feature = "serialize", derive(Serialize, Deserialize))]
77	#[derive(Clone, Debug)]
78	pub struct IFDD<P> {
79	pub base: P,
80	pub features: Vec<Feature>,
81
82	candidates: HashMap<IndexSet, CandidateFeature>,
83	discovery_threshold: f64,
84	}
85
86	impl<P: Space> IFDD<P> {
87	pub fn new(base_projector: P, discovery_threshold: f64) -> Self {	1✔
88	let initial_dim: usize = base_projector.dim();	1✔
89	let mut base_features: Vec<Feature> = (0..initial_dim)	1✔
90	.map(\|i\| Feature {	1✔
91	index: i,	1✔
92	parent_indices: {
93	let mut index_set = IndexSet::new();	1✔
94	index_set.insert(i);	1✔
95	index_set	1✔
96	},	×
97	})	1✔
98	.collect();	1✔
99
100	base_features.reserve(initial_dim);	1✔
101
102	IFDD {	1✔
103	base: base_projector,	1✔
104
105	features: base_features,	1✔
106	candidates: HashMap::new(),	1✔
107
108	discovery_threshold: discovery_threshold,	1✔
109	}	×
110	}	1✔
111
112	#[inline]
113	fn inspect_candidate(&mut self, g: usize, h: usize, error: f64) -> Option<CandidateFeature> {	1✔
114	let key = self.features[g].union(&self.features[h]);	1✔
115	let rel = {
116	let c = self	1✔
117	.candidates
118	.entry(key.clone())	1✔
119	.or_insert_with(\|\| CandidateFeature::new(key.clone()));	1✔
120
121	c.relevance += error.abs();	1✔
122
123	c.relevance	1✔
124	};
125
126	if rel >= self.discovery_threshold {	1✔
127	Some(self.candidates.remove(&key).unwrap())	1✔
128	} else {
129	None	1✔
130	}
131	}	1✔
132
133	#[inline]
134	fn discover_dense(&mut self, phi: Vector<f64>, error: f64) -> Vec<CandidateFeature> {	×
135	(0..phi.len())	×
136	.filter(\|&i\| phi[i].abs() < 1e-7)	×
137	.combinations(2)
138	.filter_map(\|indices\| self.inspect_candidate(indices[0], indices[1], error))	×
139	.collect()
140	}	×
141
142	#[inline]
143	fn discover_sparse(&mut self, active_indices: IndexSet, error: f64) -> Vec<CandidateFeature> {	1✔
144	active_indices	1✔
145	.iter()
146	.tuple_combinations()
147	.filter_map(\|(&g, &h)\| self.inspect_candidate(g, h, error))	1✔
148	.collect()
149	}	1✔
150
151	fn add_feature(&mut self, candidate: CandidateFeature) -> Option<(usize, IndexSet)> {	1✔
152	let idx = self.features.len();	1✔
153	let feature = candidate.into_feature(idx);	1✔
154	let mapping = (idx, feature.parent_indices.clone());	1✔
155
156	self.features.push(feature);	1✔
157
158	Some(mapping)	1✔
159	}	1✔
160	}
161
162	impl<P> IFDD<P> {
163	fn discover<I>(&mut self, input: &I, error: f64) -> Option<HashMap<IndexT, IndexSet>>	1✔
164	where
165	I: ?Sized,
166	P: Projector<I>
167	{
168	let new_features = match self.base.project(input) {	1✔
169	Features::Sparse(active_indices) => self.discover_sparse(active_indices, error),	1✔
170	Features::Dense(activations) => self.discover_dense(activations, error),	×
171	};	1✔
172
173	self.features.reserve_exact(new_features.len());	1✔
174
175	new_features.into_iter().fold(None, \|mut acc, f\| {	1✔
176	match self.add_feature(f) {	1✔
177	Some(nf) => {	1✔
178	acc.get_or_insert_with(HashMap::new).insert(nf.0, nf.1);	1✔
179	},
180	None => (),
181	};	1✔
182
183	acc	1✔
184	})	1✔
185	}	1✔
186	}
187
188	impl<P: Space> Space for IFDD<P> {
189	type Value = Features;
190
191	fn dim(&self) -> usize { self.features.len() }
192
193	fn card(&self) -> Card { unimplemented!() }
194	}
195
196	impl<I: ?Sized, P: Projector<I>> Projector<I> for IFDD<P> {
197	fn project(&self, input: &I) -> Features {
198	let mut p = self.base.project(input);
199	let np: Vec<usize> = (self.base.dim()..self.dim())
200	.filter_map(\|i\| {
201	let f = &self.features[i];
202
203	if f.parent_indices.iter().all(\|i\| p[*i].abs() < 1e-7) {
204	Some(i)
205	} else {
206	None
207	}
208	})
209	.collect();
210
211	for i in np.iter() {
212	for j in self.features[*i].parent_indices.iter() {
213	p.remove(*j)
214	}
215	}
216
217	p + np.into()
218	}
219	}
220
221	#[cfg(test)]
222	mod tests {
223	use super::*;
224	use crate::basis::ifdd::IFDD;
225
226	#[derive(Clone)]	×
227	struct BaseProjector;
228
229	impl Space for BaseProjector {
230	type Value = Features;
231
232	fn dim(&self) -> usize { 5 }	1✔
233
234	fn card(&self) -> Card { unimplemented!() }	×
235	}
236
237	impl Projector<[f64]> for BaseProjector {
238	fn project(&self, input: &[f64]) -> Features {	1✔
239	input	1✔
240	.iter()
241	.map(\|v\| v.round().min(4.0).max(0.0) as usize)	1✔
242	.collect()
243	}	1✔
244	}
245
246	#[test]
247	fn test_discover() {	1✔
248	let mut f = IFDD::new(BaseProjector, 10.0);	1✔
249
250	assert_eq!(	1✔
251	f.discover(&vec![0.0, 4.0], 10.0),	1✔
252	Some({	1✔
253	let mut hm = HashMap::new();	1✔
254	hm.insert(5, [0, 4].iter().cloned().collect());	1✔
255	hm	1✔
256	})	×
257	);
258	assert_eq!(	1✔
259	f.features[5],	1✔
260	Feature {	1✔
261	index: 5,
262	parent_indices: [0, 4].iter().cloned().collect(),	1✔
263	}
264	);
265
266	assert_eq!(f.discover(&vec![0.0, 3.0], 5.0), None);	1✔
267	assert_eq!(f.features.len(), 6);	1✔
268
269	assert_eq!(	1✔
270	f.discover(&vec![0.0, 3.0], 5.0),	1✔
271	Some({	1✔
272	let mut hm = HashMap::new();	1✔
273	hm.insert(6, [0, 3].iter().cloned().collect());	1✔
274	hm	1✔
275	})	×
276	);
277	assert_eq!(	1✔
278	f.features[6],	1✔
279	Feature {	1✔
280	index: 6,
281	parent_indices: [0, 3].iter().cloned().collect(),	1✔
282	}
283	);
284	}	1✔
285	}

tspooner / lfa / 102

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous