1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 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 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
//! # Utility-Programming: A library for composable utility programming. //! //! This library is brought to you by //! the [AdvancedResearch](https://github.com/advancedresearch/advancedresearch.github.io) community. //! //! ### Introduction //! //! Utility programming can be thought of as a form of programming with soft constraints. //! Instead of programming rules explicitly, various aspects of the solution is assigned a utility. //! An optimization algorithm then generates and modifies objects to maximize the utility. //! //! The advantage of utility programming is that one feature can be traded with another. //! By adjusting the weights of utility of various features, the optimized object can //! be modified to fit new criteria without rewriting the algorithm. //! //! Utility programming differs from other kinds of machine learning in the following ways: //! //! - The goal is to develop reusable composable components based on a common set of abstractions //! - The utility of sub-components are often used in the strategy of higher level components //! - Utilities are not treated as final goals, but as a technique for optimization and learning //! - The objects to be optimized are virtual //! - The optimization process is assumed to a have few side effects //! //! These properties results in higher focus on the programming aspects by adjusting utilities. //! //! From a library perspective, finding utility definitions that interact nicely with //! each other is the challenge of API designers. //! //! ### Design //! //! The abstractions for utility programming consists of 3 parts: //! //! - `Utility` trait (implemented by objects that measure some utility) //! - `Generator` trait (implemented by objects that generate some kind of object) //! - `Modifier` trait (implemented by objects that modify other objects) //! //! All traits are implemented for `Vec<T>` where `T` implements the trait: //! //! - `Vec<T: Utility>` sums the utility of each sub-utility //! - `Vec<T: Generator>` picks a random generator to generate the object //! - `Vec<T: Modifier>` picks a random modifier to modify the object //! //! It is common to use `enum` instead of `struct` to combine variants with `Vec<T>`. //! //! Modification requires `undo` and `redo` for backtracking and replication. //! //! ### Utility Epistomology //! //! Epistomology is philosophy of knowledge. //! Utility Epistomology means philosophy of utility knowledge. //! //! Utility optimization consists of 3 major efficiency levels: //! //! 1. Object generation (blind utility) //! 2. Modification (target utility) //! 3. Trade-off prediction (heuristics utility) //! //! The optimized solution is a result of the 3 levels above. //! All the information that is used to evaluate the utility //! is stored in the object of interest. //! This means one can predict certain aspects of the optimal solution //! from the utility parameters, generators and modifiers. //! //! An optimal agent operating at the 1st level is required behavior to be optimally creative. //! It is able to think of anything that might be possible for a given problem. //! //! An optimal agent operating at the 2nd level is required behavior to be instrumentally rational. //! It is able to maximize its goal in the most efficient way. //! //! An optimal agent operating at the 3rd level is required behavior to be zen rational. //! It is able to predict what the optimized solution might look like if the utility was different. //! //! One motivation for developing tools for utility programming is to study //! [Zen Rationality](https://github.com/advancedresearch/path_semantics/blob/master/papers-wip/zen-rationality.pdf). extern crate rand; /// Implemented by objects that measure utility of an object. pub trait Utility<T> { /// Computes the utility of an object. fn utility(&self, obj: &T) -> f64; } /// Sums up utility from multiple sub-terms. impl<T, U: Utility<T>> Utility<T> for Vec<U> { fn utility(&self, obj: &T) -> f64 { self.iter().map(|it| it.utility(obj)).sum() } } /// Implemented by objects that generates other objects. pub trait Generator { /// The type of the object generated. type Output; /// Generate a new object. /// /// This might be indeterministic. fn generate(&mut self) -> Self::Output; } impl<T: Generator> Generator for Vec<T> { type Output = T::Output; fn generate(&mut self) -> Self::Output { let index = rand::random::<usize>() % self.len(); self[index].generate() } } /// Modifies objects in a way that can be reversed. /// /// ### Change in meaning of modifier /// /// When there are multiple modifiers in the same context, /// such as a list of modifiers, then one modification might /// change the meaning of another. /// /// For example, when an item is insert into a list: /// /// - `[0, 3]`, inserting at `1` changes to `[0, 4]` (range includes index) /// - `[2, 4]`, inserting at `0` changes to `[3, 5]` (range is after index) /// - `[0, 3]`, inserting at `3` changes to `[0, 3]` (the same) /// /// Meaning of a modifier is information that refers to information in the object. /// When the object changes, the consistency of the reference might require updating the modifier. /// /// This is what the methods `undo_meaning` and `redo_meaning` do. /// They preserve meaning even though the change originated from another modifier. pub trait Modifier<T> { /// The change applied to an object. type Change; /// Modify an object and return the change. /// /// This might be indeterministic. /// Use `redo_meaning` for applying change in meaning of modifier. fn modify(&mut self, obj: &mut T) -> Self::Change; /// Undo change made to an object. /// /// Required to be deterministic. fn undo(&mut self, change: &Self::Change, obj: &mut T); /// Redo change made to an object. /// /// Required to be deterministic. fn redo(&mut self, change: &Self::Change, obj: &mut T); /// Undo meaning change in the modifier introduced by a change. /// /// This is called after undoing change by any modifier used in same context. fn undo_meaning(&mut self, _change: &Self::Change) {} /// Redo meaning change in the modifier. /// /// This is called after modification by any modifier used in same context. fn redo_meaning(&mut self, _change: &Self::Change) {} } impl<T, U: Modifier<T>> Modifier<T> for Vec<U> { type Change = (usize, U::Change); fn modify(&mut self, obj: &mut T) -> Self::Change { let index = rand::random::<usize>() % self.len(); (index, self[index].modify(obj)) } fn undo(&mut self, change: &Self::Change, obj: &mut T) { self[change.0].undo(&change.1, obj) } fn redo(&mut self, change: &Self::Change, obj: &mut T) { self[change.0].redo(&change.1, obj) } fn undo_meaning(&mut self, change: &Self::Change) { for it in self {it.undo_meaning(&change.1)} } fn redo_meaning(&mut self, change: &Self::Change) { for it in self {it.undo_meaning(&change.1)} } } /// Modifies an object using a modifier by maximizing utility. pub struct ModifyOptimizer<M, U> { /// The modifier to modify the object. pub modifier: M, /// The measured utility. pub utility: U, /// The number of tries before giving up. pub tries: usize, /// The number of repeated modifications before backtracking. pub depth: usize, } impl<T, M, U> Modifier<T> for ModifyOptimizer<M, U> where M: Modifier<T>, U: Utility<T>, M::Change: Clone { type Change = Vec<M::Change>; fn modify(&mut self, obj: &mut T) -> Self::Change { let mut best = vec![]; let mut best_utility: f64 = self.utility.utility(obj); let mut stack = vec![]; for _ in 0..self.tries { for _ in 0..self.depth { let change = self.modifier.modify(obj); self.modifier.redo_meaning(&change); stack.push(change); let utility = self.utility.utility(obj); if best_utility < utility { best = stack.clone(); best_utility = utility; } } while let Some(ref action) = stack.pop() { self.modifier.undo(action, obj); self.modifier.undo_meaning(&action); } } for i in 0..best.len() { self.modifier.redo(&best[i], obj); self.modifier.redo_meaning(&best[i]); } best } fn undo(&mut self, change: &Self::Change, obj: &mut T) { for i in (0..change.len()).rev() { self.modifier.undo(&change[i], obj); self.modifier.undo_meaning(&change[i]); } } fn redo(&mut self, change: &Self::Change, obj: &mut T) { for i in 0..change.len() { self.modifier.redo(&change[i], obj); self.modifier.redo_meaning(&change[i]); } } }