Policy gradient method

Policy gradient methods are a class of reinforcement learning algorithms and a sub-class of policy optimization methods. Unlike value-based methods which learn a value function to derive a policy, policy optimization methods directly learn a policy function π {\displaystyle \pi } that selects actions without consulting a value function. For policy gradient to apply, the policy function π θ {\displaystyle \pi _{\theta }} is parameterized by a differentiable parameter θ {\displaystyle \theta } . == Overview == In policy-based RL, the actor is a parameterized policy function π θ {\displaystyle \pi _{\theta }} , where θ {\displaystyle \theta } are the parameters of the actor. The actor takes as argument the state of the environment s {\displaystyle s} and produces a probability distribution π θ ( ⋅ ∣ s ) {\displaystyle \pi _{\theta }(\cdot \mid s)} . If the action space is discrete, then ∑ a π θ ( a ∣ s ) = 1 {\displaystyle \sum _{a}\pi _{\theta }(a\mid s)=1} . If the action space is continuous, then ∫ a π θ ( a ∣ s ) d a = 1 {\displaystyle \int _{a}\pi _{\theta }(a\mid s)\mathrm {d} a=1} . The goal of policy optimization is to find some θ {\displaystyle \theta } that maximizes the expected episodic reward J ( θ ) {\displaystyle J(\theta )} : J ( θ ) = E π θ [ ∑ t = 0 T γ t R t | S 0 = s 0 ] {\displaystyle J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\gamma ^{t}R_{t}{\Big |}S_{0}=s_{0}\right]} where γ {\displaystyle \gamma } is the discount factor, R t {\displaystyle R_{t}} is the reward at step t {\displaystyle t} , s 0 {\displaystyle s_{0}} is the starting state, and T {\displaystyle T} is the time-horizon (which can be infinite). The policy gradient is defined as ∇ θ J ( θ ) {\displaystyle \nabla _{\theta }J(\theta )} . Different policy gradient methods stochastically estimate the policy gradient in different ways. The goal of any policy gradient method is to iteratively maximize J ( θ ) {\displaystyle J(\theta )} by gradient ascent. Since the key part of any policy gradient method is the stochastic estimation of the policy gradient, they are also studied under the title of "Monte Carlo gradient estimation". == REINFORCE == === Policy gradient === The REINFORCE algorithm, introduced by Ronald J. Williams in 1992, was the first policy gradient method. It is based on the identity for the policy gradient ∇ θ J ( θ ) = E π θ [ ∑ t = 0 T ∇ θ ln ⁡ π θ ( A t ∣ S t ) ∑ t = 0 T ( γ t R t ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})\;\sum _{t=0}^{T}(\gamma ^{t}R_{t}){\Big |}S_{0}=s_{0}\right]} which can be improved via the "causality trick" ∇ θ J ( θ ) = E π θ [ ∑ t = 0 T ∇ θ ln ⁡ π θ ( A t ∣ S t ) ∑ τ = t T ( γ τ R τ ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau }){\Big |}S_{0}=s_{0}\right]} Thus, we have an unbiased estimator of the policy gradient: ∇ θ J ( θ ) ≈ 1 N ∑ n = 1 N [ ∑ t = 0 T ∇ θ ln ⁡ π θ ( A t , n ∣ S t , n ) ∑ τ = t T ( γ τ − t R τ , n ) ] {\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau =t}^{T}(\gamma ^{\tau -t}R_{\tau ,n})\right]} where the index n {\displaystyle n} ranges over N {\displaystyle N} rollout trajectories using the policy π θ {\displaystyle \pi _{\theta }} . The score function ∇ θ ln ⁡ π θ ( A t ∣ S t ) {\displaystyle \nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})} can be interpreted as the direction in the parameter space that increases the probability of taking action A t {\displaystyle A_{t}} in state S t {\displaystyle S_{t}} . The policy gradient, then, is a weighted average of all possible directions to increase the probability of taking any action in any state, but weighted by reward signals, so that if taking a certain action in a certain state is associated with high reward, then that direction would be highly reinforced, and vice versa. === Algorithm === The REINFORCE algorithm is a loop: Rollout N {\displaystyle N} trajectories in the environment, using π θ t {\displaystyle \pi _{\theta _{t}}} as the policy function. Compute the policy gradient estimation: g i ← 1 N ∑ n = 1 N [ ∑ t = 0 T ∇ θ t ln ⁡ π θ ( A t , n ∣ S t , n ) ∑ τ = t T ( γ τ R τ , n ) ] {\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau ,n})\right]} Update the policy by gradient ascent: θ i + 1 ← θ i + α i g i {\displaystyle \theta _{i+1}\leftarrow \theta _{i}+\alpha _{i}g_{i}} Here, α i {\displaystyle \alpha _{i}} is the learning rate at update step i {\displaystyle i} . == Variance reduction == REINFORCE is an on-policy algorithm, meaning that the trajectories used for the update must be sampled from the current policy π θ {\displaystyle \pi _{\theta }} . This can lead to high variance in the updates, as the returns R ( τ ) {\displaystyle R(\tau )} can vary significantly between trajectories. Many variants of REINFORCE have been introduced, under the title of variance reduction. === REINFORCE with baseline === A common way for reducing variance is the REINFORCE with baseline algorithm, based on the following identity: ∇ θ J ( θ ) = E π θ [ ∑ t = 0 T ∇ θ ln ⁡ π θ ( A t | S t ) ( ∑ τ = t T ( γ τ R τ ) − b ( S t ) ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })-b(S_{t})\right){\Big |}S_{0}=s_{0}\right]} for any function b : States → R {\displaystyle b:{\text{States}}\to \mathbb {R} } . This can be proven by applying the previous lemma. The algorithm uses the modified gradient estimator g i ← 1 N ∑ n = 1 N [ ∑ t = 0 T ∇ θ t ln ⁡ π θ ( A t , n | S t , n ) ( ∑ τ = t T ( γ τ R τ , n ) − b i ( S t , n ) ) ] {\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t=0}^{T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}|S_{t,n})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau ,n})-b_{i}(S_{t,n})\right)\right]} and the original REINFORCE algorithm is the special case where b i ≡ 0 {\displaystyle b_{i}\equiv 0} . === Actor-critic methods === If b i {\textstyle b_{i}} is chosen well, such that b i ( S t ) ≈ ∑ τ = t T ( γ τ R τ ) = γ t V π θ i ( S t ) {\textstyle b_{i}(S_{t})\approx \sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })=\gamma ^{t}V^{\pi _{\theta _{i}}}(S_{t})} , this could significantly decrease variance in the gradient estimation. That is, the baseline should be as close to the value function V π θ i ( S t ) {\displaystyle V^{\pi _{\theta _{i}}}(S_{t})} as possible, approaching the ideal of: ∇ θ J ( θ ) = E π θ [ ∑ t = 0 T ∇ θ ln ⁡ π θ ( A t | S t ) ( ∑ τ = t T ( γ τ R τ ) − γ t V π θ ( S t ) ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t=0}^{T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau =t}^{T}(\gamma ^{\tau }R_{\tau })-\gamma ^{t}V^{\pi _{\theta }}(S_{t})\right){\Big |}S_{0}=s_{0}\right]} Note that, as the policy π θ t {\displaystyle \pi _{\theta _{t}}} updates, the value function V π θ i ( S t ) {\displaystyle V^{\pi _{\theta _{i}}}(S_{t})} updates as well, so the baseline should also be updated. One common approach is to train a separate function that estimates the value function, and use that as the baseline. This is one of the actor-critic methods, where the policy function is the actor and the value function is the critic. The Q-function Q π {\displaystyle Q^{\pi }} can also be used as the critic, since ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T γ t ∇ θ ln ⁡ π θ ( A t | S t ) ⋅ Q π θ ( S t , A t ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot Q^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]} by a similar argument using the tower law. Subtracting the value function as a baseline, we find that the advantage function A π ( S , A ) = Q π ( S , A ) − V π ( S ) {\displaystyle A^{\pi }(S,A)=Q^{\pi }(S,A)-V^{\pi }(S)} can be used as the critic as well: ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T γ t ∇ θ ln ⁡ π θ ( A t | S t ) ⋅ A π θ ( S t , A t ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot A^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]} In summary, there are many unbiased estimators for ∇ θ J θ {\textstyle \nabla _{\theta }J_{\theta }} , all in the form of: ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T ∇ θ ln ⁡ π θ ( A t | S t ) ⋅ Ψ t | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\su

Ordered dithering

Ordered dithering is any image dithering algorithm which uses a pre-set threshold map tiled across an image. It is commonly used to display a continuous image on a display of smaller color depth. For example, Microsoft Windows uses it in 16-color graphics modes. With the most common "Bayer" threshold map, the algorithm is characterized by noticeable crosshatch patterns in the result. == Threshold map == The algorithm reduces the number of colors by applying a threshold map M to the pixels displayed, causing some pixels to change color, depending on the distance of the original color from the available color entries in the reduced palette. The first threshold maps were designed by hand to minimise the perceptual difference between a grayscale image and its two-bit quantisation for up to a 4x4 matrix. An optimal threshold matrix is one that for any possible quantisation of color has the minimum possible texture so that the greatest impression of the underlying feature comes from the image being quantised. It can be proven that for matrices whose side length is a power of two there is an optimal threshold matrix. The map may be rotated or mirrored without affecting the effectiveness of the algorithm. This threshold map (for sides with length as power of two) is also known as a Bayer matrix or, when unscaled, an index matrix. For threshold maps whose dimensions are a power of two, the map can be generated recursively via: M 2 n = 1 ( 2 n ) 2 [ 4 M n 4 M n + 2 J n 4 M n + 3 J n 4 M n + J n ] = J 2 ⊗ M n + 1 n 2 M 2 ⊗ J n , {\displaystyle \mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}{\begin{bmatrix}4\mathbf {M} _{n}&4\mathbf {M} _{n}+2\mathbf {J} _{n}\\4\mathbf {M} _{n}+3\mathbf {J} _{n}&4\mathbf {M} _{n}+\mathbf {J} _{n}\end{bmatrix}}=\mathbf {J} _{2}\otimes \mathbf {M} _{n}+{\frac {1}{n^{2}}}\mathbf {M} _{2}\otimes \mathbf {J} _{n},} where J n {\displaystyle \mathbf {J} _{n}} are n × n {\displaystyle n\times n} matrices of ones and ⊗ {\displaystyle \otimes } is the Kronecker product. While the metric for texture that Bayer proposed could be used to find optimal matrices for sizes that are not a power of two, such matrices are uncommon as no simple formula for finding them exists, and relatively small matrix sizes frequently give excellent practical results (especially when combined with other modifications to the dithering algorithm). This function can also be expressed using only bit arithmetic: M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2 == Pre-calculated threshold maps == Rather than storing the threshold map as a matrix of n {\displaystyle n} × n {\displaystyle n} integers from 0 to n 2 {\displaystyle n^{2}} , depending on the exact hardware used to perform the dithering, it may be beneficial to pre-calculate the thresholds of the map into a floating point format, rather than the traditional integer matrix format shown above. For this, the following formula can be used: Mpre(i,j) = Mint(i,j) / n^2 This generates a standard threshold matrix. for the 2×2 map: this creates the pre-calculated map: Additionally, normalizing the values to average out their sum to 0 (as done in the dithering algorithm shown below) can be done during pre-processing as well by subtracting 1⁄2 of the largest value from every value: Mpre(i,j) = Mint(i,j) / n^2 – 0.5 maxValue creating the pre-calculated map: == Algorithm == The ordered dithering algorithm renders the image normally, but for each pixel, it offsets its color value with a corresponding value from the threshold map according to its location, causing the pixel's value to be quantized to a different color if it exceeds the threshold. For most dithering purposes, it is sufficient to simply add the threshold value to every pixel (without performing normalization by subtracting 1⁄2), or equivalently, to compare the pixel's value to the threshold: if the brightness value of a pixel is less than the number in the corresponding cell of the matrix, plot that pixel black, otherwise, plot it white. This lack of normalization slightly increases the average brightness of the image, and causes almost-white pixels to not be dithered. This is not a problem when using a gray scale palette (or any palette where the relative color distances are (nearly) constant), and it is often even desired, since the human eye perceives differences in darker colors more accurately than lighter ones, however, it produces incorrect results especially when using a small or arbitrary palette, so proper normalization should be preferred. In other words, the algorithm performs the following transformation on each color c of every pixel: c ′ = n e a r e s t _ p a l e t t e _ c o l o r ( c + r × ( M ( x mod n , y mod n ) − 1 / 2 ) ) {\displaystyle c'=\mathrm {nearest\_palette\_color} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-1/2\right){\mathclose {}}\right)} where M(i, j) is the threshold map on the i-th row and j-th column, c′ is the transformed color, and r is the amount of spread in color space. Assuming an RGB palette with 23N evenly distanced colors where each color (a triple of red, green and blue values) is represented by an octet from 0 to 255, one would typically choose r ≈ 255 N {\textstyle r\approx {\frac {255}{N}}} . (1⁄2 is again the normalizing term.) Because the algorithm operates on single pixels and has no conditional statements, it is very fast and suitable for real-time transformations. Additionally, because the location of the dithering patterns always stays the same relative to the display frame, it is less prone to jitter than error-diffusion methods, making it suitable for animations. Because the patterns are more repetitive than error-diffusion method, an image with ordered dithering compresses better. Ordered dithering is more suitable for line-art graphics as it will result in straighter lines and fewer anomalies. The values read from the threshold map should preferably scale into the same range as the minimal difference between distinct colors in the target palette. Equivalently, the size of the map selected should be equal to or larger than the ratio of source colors to target colors. For example, when quantizing a 24 bpp image to 15 bpp (256 colors per channel to 32 colors per channel), the smallest map one would choose would be 4×2, for the ratio of 8 (256:32). This allows expressing each distinct tone of the input with different dithering patterns. === A variable palette: pattern dithering === == Non-Bayer approaches == The above thresholding matrix approach describes the Bayer family of ordered dithering algorithms. A number of other algorithms are also known; they generally involve changes in the threshold matrix, which changes the distribution of the "noise" introduced by all kinds of dithering (the difference between the original image and the dithered image). === Halftone === Halftone dithering performs a form of clustered dithering, creating a look similar to halftone patterns, using a specially crafted matrix. === Void and cluster === The Void and cluster algorithm uses a pre-generated blue noise as the matrix for the dithering process. The blue noise matrix keeps the Bayer's good high frequency content, but with a more uniform coverage of all the frequencies involved shows a much lower amount of patterning. The "voids-and-cluster" method gets its name from the matrix generation procedure, where a black image with randomly initialized white pixels is gaussian-blurred to find the brightest and darkest parts, corresponding to voids and clusters. After a few swaps have evenly distributed the bright and dark parts, the pixels are numbered by importance. It takes significant computational resources to generate the blue noise matrix: on a modern computer a 64×64 matrix requires a couple seconds using the original algorithm. This algorithm can be extended to make animated dither masks which also consider the axis of time. This is done by running the algorithm in three dimensions and using a kernel which is a product of a two-dimensional gaussian kernel on the XY plane, and a one-dimensional Gaussian kernel on the Z axis. === Simulated Annealing === Simulated annealing can generate dither masks by starting with a flat histogram and swapping values to optimize a loss function. The loss function controls the spectral properties of the mask, allowing it to make blue noise or noise patterns meant to be filtered by specific filters. The algorithm can also be extended over time for animated dither masks with chosen temporal properties.

Taguchi loss function

The Taguchi loss function is graphical depiction of loss developed by the Japanese business statistician Genichi Taguchi to describe a phenomenon affecting the value of products produced by a company. Praised by Dr. W. Edwards Deming (the business guru of the 1980s American quality movement), it made clear the concept that quality does not suddenly plummet when, for instance, a machinist exceeds a rigid blueprint tolerance. Instead 'loss' in value progressively increases as variation increases from the intended condition. This was considered a breakthrough in describing quality, and helped fuel the continuous improvement movement. The concept of Taguchi's quality loss function was in contrast with the American concept of quality, popularly known as goal post philosophy, the concept given by American quality guru Phil Crosby. Goal post philosophy emphasizes that if a product feature doesn't meet the designed specifications it is termed as a product of poor quality (rejected), irrespective of amount of deviation from the target value (mean value of tolerance zone). This concept has similarity with the concept of scoring a 'goal' in the game of football or hockey, because a goal is counted 'one' irrespective of the location of strike of the ball in the 'goal post', whether it is in the center or towards the corner. This means that if the product dimension goes out of the tolerance limit the quality of the product drops suddenly. Through his concept of the quality loss function, Taguchi explained that from the customer's point of view this drop of quality is not sudden. The customer experiences a loss of quality the moment product specification deviates from the 'target value'. This 'loss' is depicted by a quality loss function and it follows a parabolic curve mathematically given by L = k(y–m)2, where m is the theoretical 'target value' or 'mean value' and y is the actual size of the product, k is a constant and L is the loss. This means that if the difference between 'actual size' and 'target value' i.e. (y–m) is large, loss would be more, irrespective of tolerance specifications. In Taguchi's view tolerance specifications are given by engineers and not by customers; what the customer experiences is 'loss'. This equation is true for a single product; if 'loss' is to be calculated for multiple products the loss function is given by L = k[S2 + ( y ¯ {\displaystyle {\bar {y}}} – m)2], where S2 is the 'variance of product size' and y ¯ {\displaystyle {\bar {y}}} is the average product size. == Overview == The Taguchi loss function is important for a number of reasons—primarily, to help engineers better understand the importance of designing for variation.

Receptron

The receptron (short for "reservoir perceptron") is a neuromorphic data processing model — specifically neuromorphic computing — that generalizes the traditional perceptron, by incorporating non-linear interactions between inputs. Unlike classical perceptron, which rely on linearly independent weights, the receptron leverages complexity in physical substrates, such as the electric conduction properties of nanostructured materials or optical speckle fields, to perform classification tasks. The receptron bridges unconventional computing and neural network principles, enabling solutions that do not require the training approaches typical of artificial neural networks based on the perceptron model. == Algorithm == The receptron is an algorithm for supervised learning of binary classifiers, so a classification algorithm that makes its predictions based on a predictor function, combining a set of weights with the feature vector. The mathematical model is based on the sum of inputs with non-linear interactions: S = ∑ k = 1 n x j w ~ j ( x → ) | S ∈ R {\displaystyle S=\sum _{k=1}^{n}x_{j}{\widetilde {w}}_{j}({\vec {x}})|S\in R} (1) where j ∈ [ 1 , n ] {\displaystyle j\in [1,n]} and w ~ j {\displaystyle {\widetilde {w}}_{j}} are non-linear weight functions depending on the inputs, x → {\displaystyle {\vec {x}}} . Nonlinearity will typically make the system extremely complex, and allowing for the solution of problems not solvable through the simpler rules of a linear system, such as the perceptron or McCulloch Pitts neurons, which is based on the sum of linearly independent weights: S = ∑ k = 1 n x j w j p {\displaystyle S=\sum _{k=1}^{n}x_{j}w_{j}^{p}} (2) where w j {\displaystyle w_{j}} are constant real values. A consequence of this simplicity is the limitation to linearly separable functions, which necessitates multi-layer architectures and training algorithms like backpropagation As in the perceptron case, the summation in Eq. 1 origins the activation of the receptron output through the thresholding process, Y ( x 1 , . . . , x n ) = { 1 if S > th 0 if S ≤ th {\displaystyle Y(x_{1},...,x_{n})={\begin{cases}1&{\text{if }}S>{\text{th}}\\0&{\text{if }}S\leq {\text{th}}\end{cases}}} (3) where th is a constant threshold parameter. Equation 3 can be written by using the Heaviside step function. The weight functions w ~ ( x → ) {\displaystyle {\widetilde {w}}({\vec {x}})} can be written with a finite number of parameters w j 1 . . . j n {\displaystyle w_{j_{1}...j_{n}}} , simplifying the model representation. One can Taylor-expand w ~ ( x → ) {\displaystyle {\widetilde {w}}({\vec {x}})} and use the idempotency of Boolean variables ( x j ) q = x j ∀ q ≥ 1 {\displaystyle (x_{j})^{q}=x_{j}\forall q\geq 1} such that S ′ = b + ∑ k = 1 n x j w ~ j ( x → ) {\displaystyle S'=b+\sum _{k=1}^{n}x_{j}{\widetilde {w}}_{j}({\vec {x}})} can be written as S ′ ( x → ) = b + ∑ j w j x j + ∑ j < k w j k x j x k + ∑ j < k < l w j k l x j x k x l + . . . {\displaystyle S'({\vec {x}})=b+\sum _{j}w_{j}x_{j}+\sum _{j

Influence diagram

An influence diagram (ID) (also called a relevance diagram, decision diagram or a decision network) is a compact graphical and mathematical representation of a decision situation. It is a generalization of a Bayesian network, in which not only probabilistic inference problems but also decision making problems (following the maximum expected utility criterion) can be modeled and solved. ID was first developed in the mid-1970s by decision analysts with an intuitive semantic that is easy to understand. It is now adopted widely and becoming an alternative to the decision tree which typically suffers from exponential growth in number of branches with each variable modeled. ID is directly applicable in team decision analysis, since it allows incomplete sharing of information among team members to be modeled and solved explicitly. Extensions of ID also find their use in game theory as an alternative representation of the game tree. == Semantics == An ID is a directed acyclic graph with three types (plus one subtype) of node and three types of arc (or arrow) between nodes. Nodes: Decision node (corresponding to each decision to be made) is drawn as a rectangle. Uncertainty node (corresponding to each uncertainty to be modeled) is drawn as an oval. Deterministic node (corresponding to special kind of uncertainty that its outcome is deterministically known whenever the outcome of some other uncertainties are also known) is drawn as a double oval. Value node (corresponding to each component of additively separable Von Neumann-Morgenstern utility function) is drawn as an octagon (or diamond). Arcs: Functional arcs (ending in value node) indicate that one of the components of additively separable utility function is a function of all the nodes at their tails. Conditional arcs (ending in uncertainty node) indicate that the uncertainty at their heads is probabilistically conditioned on all the nodes at their tails. Conditional arcs (ending in deterministic node) indicate that the uncertainty at their heads is deterministically conditioned on all the nodes at their tails. Informational arcs (ending in decision node) indicate that the decision at their heads is made with the outcome of all the nodes at their tails known beforehand. Given a properly structured ID: Decision nodes and incoming information arcs collectively state the alternatives (what can be done when the outcome of certain decisions and/or uncertainties are known beforehand) Uncertainty/deterministic nodes and incoming conditional arcs collectively model the information (what are known and their probabilistic/deterministic relationships) Value nodes and incoming functional arcs collectively quantify the preference (how things are preferred over one another). Alternative, information, and preference are termed decision basis in decision analysis, they represent three required components of any valid decision situation. Formally, the semantic of influence diagram is based on sequential construction of nodes and arcs, which implies a specification of all conditional independencies in the diagram. The specification is defined by the d {\displaystyle d} -separation criterion of Bayesian network. According to this semantic, every node is probabilistically independent on its non-successor nodes given the outcome of its immediate predecessor nodes. Likewise, a missing arc between non-value node X {\displaystyle X} and non-value node Y {\displaystyle Y} implies that there exists a set of non-value nodes Z {\displaystyle Z} , e.g., the parents of Y {\displaystyle Y} , that renders Y {\displaystyle Y} independent of X {\displaystyle X} given the outcome of the nodes in Z {\displaystyle Z} . == Example == Consider the simple influence diagram representing a situation where a decision-maker is planning their vacation. There is 1 decision node (Vacation Activity), 2 uncertainty nodes (Weather Condition, Weather Forecast), and 1 value node (Satisfaction). There are 2 functional arcs (ending in Satisfaction), 1 conditional arc (ending in Weather Forecast), and 1 informational arc (ending in Vacation Activity). Functional arcs ending in Satisfaction indicate that Satisfaction is a utility function of Weather Condition and Vacation Activity. In other words, their satisfaction can be quantified if they know what the weather is like and what their choice of activity is. (Note that they do not value Weather Forecast directly) Conditional arc ending in Weather Forecast indicates their belief that Weather Forecast and Weather Condition can be dependent. Informational arc ending in Vacation Activity indicates that they will only know Weather Forecast, not Weather Condition, when making their choice. In other words, actual weather will be known after they make their choice, and only forecast is what they can count on at this stage. It also follows semantically, for example, that Vacation Activity is independent on (irrelevant to) Weather Condition given Weather Forecast is known. == Applicability to value of information == The above example highlights the power of the influence diagram in representing an extremely important concept in decision analysis known as the value of information. Consider the following three scenarios; Scenario 1: The decision-maker could make their Vacation Activity decision while knowing what Weather Condition will be like. This corresponds to adding extra informational arc from Weather Condition to Vacation Activity in the above influence diagram. Scenario 2: The original influence diagram as shown above. Scenario 3: The decision-maker makes their decision without even knowing the Weather Forecast. This corresponds to removing informational arc from Weather Forecast to Vacation Activity in the above influence diagram. Scenario 1 is the best possible scenario for this decision situation since there is no longer any uncertainty on what they care about (Weather Condition) when making their decision. Scenario 3, however, is the worst possible scenario for this decision situation since they need to make their decision without any hint (Weather Forecast) on what they care about (Weather Condition) will turn out to be. The decision-maker is usually better off (definitely no worse off, on average) to move from scenario 3 to scenario 2 through the acquisition of new information. The most they should be willing to pay for such move is called the value of information on Weather Forecast, which is essentially the value of imperfect information on Weather Condition. The applicability of this simple ID and the value of information concept is tremendous, especially in medical decision making when most decisions have to be made with imperfect information about their patients, diseases, etc. == Related concepts == Influence diagrams are hierarchical and can be defined either in terms of their structure or in greater detail in terms of the functional and numerical relation between diagram elements. An ID that is consistently defined at all levels—structure, function, and number—is a well-defined mathematical representation and is referred to as a well-formed influence diagram (WFID). WFIDs can be evaluated using reversal and removal operations to yield answers to a large class of probabilistic, inferential, and decision questions. More recent techniques have been developed by artificial intelligence researchers concerning Bayesian network inference (belief propagation). An influence diagram having only uncertainty nodes (i.e., a Bayesian network) is also called a relevance diagram. An arc connecting node A to B implies not only that "A is relevant to B", but also that "B is relevant to A" (i.e., relevance is a symmetric relationship).

Light scanning photomacrography

Light Scanning Photomacrography (LSP), also known as Scanning Light Photomacrography (SLP) or Deep-Field Photomacrography, is a photographic film technique that allows for high magnification light imaging with exceptional depth of field (DOF). This method overcomes the limitations of conventional macro photography, which typically only keeps a portion of the subject in acceptable focus at high magnifications. == Historical background == The principles of LSP were first documented in the early 1960s by Dan McLachlan Jr., who highlighted its capability for extreme focal depth in microscopy and in 1968 patented the process. The technique was revived and further developed in the 1980s by photographers such as Darwin Dale and Nile Root, a faculty member at the Rochester Institute of Technology. In the early 1990s, William Sharp and Charles Kazilek, both researchers at Arizona State University, also published articles describing their technique and system setup for capturing SLP images. == Predecessor to stack image photography == Light Scanning Photomacrography offered a powerful analog tool for high-detail imaging in the age of film photography. It provided a comprehensive depth of field, making it invaluable in scientific and biomedical photography. As technology and techniques continue to evolve, LSP has been replaced by digital image focus stacking. This technique uses a collection of images captured in series at different focal depths, which are then processed using computer software to create a single image with a greater focus depth than any single image. == LSP technique and results == LSP involves the use of a thin plane of light that scans across the subject, which is mounted on a stage moving perpendicular to the film plane. The technique utilizes traditional optics and is governed by the physical laws of depth of field. By moving the subject through a narrow band of illumination, the entire subject can be recorded in sharp focus from the nearest details to the farthest ones. This analog process produces sharp and detailed images by slowly recording the image on film as the specimen passes through the sheet of light that is thinner than the effective DOF. Because the image is captured at the same relative distance from the camera lens, the resulting images are axonometric rather than perspective projection, which is what the human eye sees and is typically captured by a film camera. Because all parts of an LSP image are captured at the same distance from the lens, relative measurements can be taken from an LSP photograph and can be used for comparison. == Equipment and setup == A typical LSP setup includes: A stage that can move the subject perpendicular to the film plane. Light sources, in some cases modified projectors, are used to project a thin plane of light. A camera mounted on a stable stand such as a tabletop copy stand. In 1991, Sharp and Kazilek described their SLP system that used three Kodak Ektagraphic slide projectors with zoom lenses to create a thin plane of light. The projectors each had a slide mount with two razor blades placed edge-to-edge to create a thin slit for the light to pass through. The image was captured using a Nikon FE-2 SLR camera mounted above the specimen. Kodachrome 25 slide film was used to record the image and to minimize film grain size and maximize image sharpness == Commercial systems == A commercial SLP instrument was produced by the Irvine Optical Corp. Their DYNAPHOT system was based on a photomacroscope and could capture images on 4x5 film. The instrument came with two or three illumination sources and a motorized specimen stage. The system advertised a 2X – 40X magnification range and the ability to capture images in black and white and color. Other systems have been developed by Nile Root and Theodore Clarke and reported higher magnification (up to 100X). == LSP process == Alignment and Focusing: The light sources are aligned and focused to project a thin, consistent plane of light across the subject. Stage Movement: The subject stage moves at a controlled speed, scanning through the plane of light. Image Capture: The camera shutter is set to a long exposure or can be opened and closed manually. As the subject moves through the illuminated plane, it is recorded on the film. This process is very much like painting an image onto the film using photons instead of paint. == Applications == LSP was particularly useful in biomedical photography, where it was used to document magnified subjects with increased depth of field over traditional macro and micro photography. It has been employed to capture detailed images of biological specimens, such as imaging small insects and their parts. SLP has been used to document shell collections for scientific documentation and research. Other applications include forensic science, mineralogy, and the imaging of fractured surfaces and parts == Advantages and challenges of LSP imaging == === Advantages === Exceptional depth of field: Subjects are rendered in sharp focus throughout. High magnification: Detailed images at significant magnification without sacrificing DOF. Analog precision: Provides a non-digital solution with accurate image representation. Versatility: Can be used for a range of subject sizes, from macro to non-macro scales. === Challenges === Technical complexity: Requires precise setup and alignment. Exposure time: Typically requires long exposure times due to the scanning process. Contrast control: The highly directional lighting can create harsh shadows and high contrast, which may need to be managed. Digital competition: Focus stacking has largely replaced LSP in the digital era due to convenience and flexibility. == DIY contributions == Enthusiasts and researchers have contributed to the development and accessibility of LSP by creating and sharing DIY guides. These contributions have enabled others to build their own LSP systems using readily available materials and components. Nile Root's publications provide detailed instructions and recommendations for constructing an LSP setup. These DIY systems have allowed a wider audience to explore and utilize the benefits of LSP imaging in various fields.

Multiple discriminant analysis

Multiple Discriminant Analysis (MDA) is a multivariate dimensionality reduction technique. It has been used to predict signals as diverse as neural memory traces and corporate failure. MDA is not directly used to perform classification. It merely supports classification by yielding a compressed signal amenable to classification. The method described in Duda et al. (2001) §3.8.3 projects the multivariate signal down to an M−1 dimensional space where M is the number of categories. MDA is useful because most classifiers are strongly affected by the curse of dimensionality. In other words, when signals are represented in very-high-dimensional spaces, the classifier's performance is catastrophically impaired by the overfitting problem. This problem is reduced by compressing the signal down to a lower-dimensional space as MDA does. MDA has been used to reveal neural codes.