The driver scheduling problem (DSP) is type of problem in operations research and theoretical computer science. The DSP consists of selecting a set of duties (assignments) for the drivers or pilots of vehicles (e.g., buses, trains, boats, or planes) involved in the transportation of passengers or goods, within the constraints of various legislative and logistical criteria. == Criteria and modelling == This very complex problem involves several constraints related to labour and company rules and also different evaluation criteria and objectives. Being able to solve this problem efficiently can have a great impact on costs and quality of service for public transportation companies. There is a large number of different rules that a feasible duty might be required to satisfy, such as Minimum and maximum stretch duration Minimum and maximum break duration Minimum and maximum work duration Minimum and maximum total duration Maximum extra work duration Maximum number of vehicle changes Minimum driving duration of a particular vehicle Operations research has provided optimization models and algorithms that lead to efficient solutions for this problem. Among the most common models proposed to solve the DSP are the Set Covering and Set Partitioning Models (SPP/SCP). In the SPP model, each work piece (task) is covered by only one duty. In the SCP model, it is possible to have more than one duty covering a given work piece. In both models, the set of work pieces that needs to be covered is laid out in rows, and the set of previously defined feasible duties available for covering specific work pieces is arranged in columns. The DSP resolution, based on either of these models, is the selection of the set of feasible duties that guarantees that there is one (SPP) or more (SCP) duties covering each work piece while minimizing the total cost of the final schedule.
Neural network Gaussian process
A Neural Network Gaussian Process (NNGP) is a Gaussian process (GP) obtained as the limit of a certain type of sequence of neural networks. Specifically, a wide variety of network architectures converges to a GP in the infinitely wide limit, in the sense of distribution. The concept constitutes an intensional definition, i.e., a NNGP is just a GP, but distinguished by how it is obtained. == Motivation == Bayesian networks are a modeling tool for assigning probabilities to events, and thereby characterizing the uncertainty in a model's predictions. Deep learning and artificial neural networks are approaches used in machine learning to build computational models which learn from training examples. Bayesian neural networks merge these fields. They are a type of neural network whose parameters and predictions are both probabilistic. While standard neural networks often assign high confidence even to incorrect predictions, Bayesian neural networks can more accurately evaluate how likely their predictions are to be correct. Computation in artificial neural networks is usually organized into sequential layers of artificial neurons. The number of neurons in a layer is called the layer width. When we consider a sequence of Bayesian neural networks with increasingly wide layers (see figure), they converge in distribution to a NNGP. This large width limit is of practical interest, since the networks often improve as layers get wider. And the process may give a closed form way to evaluate networks. NNGPs also appears in several other contexts: It describes the distribution over predictions made by wide non-Bayesian artificial neural networks after random initialization of their parameters, but before training; it appears as a term in neural tangent kernel prediction equations; it is used in deep information propagation to characterize whether hyperparameters and architectures will be trainable. It is related to other large width limits of neural networks. === Scope === The first correspondence result had been established in the 1995 PhD thesis of Radford M. Neal, then supervised by Geoffrey Hinton at University of Toronto. Neal cites David J. C. MacKay as inspiration, who worked in Bayesian learning. Today the correspondence is proven for: Single hidden layer Bayesian neural networks; deep fully connected networks as the number of units per layer is taken to infinity; convolutional neural networks as the number of channels is taken to infinity; transformer networks as the number of attention heads is taken to infinity; recurrent networks as the number of units is taken to infinity. In fact, this NNGP correspondence holds for almost any architecture: Generally, if an architecture can be expressed solely via matrix multiplication and coordinatewise nonlinearities (i.e., a tensor program), then it has an infinite-width GP. This in particular includes all feedforward or recurrent neural networks composed of multilayer perceptron, recurrent neural networks (e.g., LSTMs, GRUs), (nD or graph) convolution, pooling, skip connection, attention, batch normalization, and/or layer normalization. === Illustration === Every setting of a neural network's parameters θ {\displaystyle \theta } corresponds to a specific function computed by the neural network. A prior distribution p ( θ ) {\displaystyle p(\theta )} over neural network parameters therefore corresponds to a prior distribution over functions computed by the network. As neural networks are made infinitely wide, this distribution over functions converges to a Gaussian process for many architectures. The notation used in this section is the same as the notation used below to derive the correspondence between NNGPs and fully connected networks, and more details can be found there. The figure to the right plots the one-dimensional outputs z L ( ⋅ ; θ ) {\displaystyle z^{L}(\cdot ;\theta )} of a neural network for two inputs x {\displaystyle x} and x ∗ {\displaystyle x^{}} against each other. The black dots show the function computed by the neural network on these inputs for random draws of the parameters from p ( θ ) {\displaystyle p(\theta )} . The red lines are iso-probability contours for the joint distribution over network outputs z L ( x ; θ ) {\displaystyle z^{L}(x;\theta )} and z L ( x ∗ ; θ ) {\displaystyle z^{L}(x^{};\theta )} induced by p ( θ ) {\displaystyle p(\theta )} . This is the distribution in function space corresponding to the distribution p ( θ ) {\displaystyle p(\theta )} in parameter space, and the black dots are samples from this distribution. For infinitely wide neural networks, since the distribution over functions computed by the neural network is a Gaussian process, the joint distribution over network outputs is a multivariate Gaussian for any finite set of network inputs. == Discussion == === Infinitely wide fully connected network === This section expands on the correspondence between infinitely wide neural networks and Gaussian processes for the specific case of a fully connected architecture. It provides a proof sketch outlining why the correspondence holds, and introduces the specific functional form of the NNGP for fully connected networks. The proof sketch closely follows the approach by Novak and coauthors. ==== Network architecture specification ==== Consider a fully connected artificial neural network with inputs x {\displaystyle x} , parameters θ {\displaystyle \theta } consisting of weights W l {\displaystyle W^{l}} and biases b l {\displaystyle b^{l}} for each layer l {\displaystyle l} in the network, pre-activations (pre-nonlinearity) z l {\displaystyle z^{l}} , activations (post-nonlinearity) y l {\displaystyle y^{l}} , pointwise nonlinearity ϕ ( ⋅ ) {\displaystyle \phi (\cdot )} , and layer widths n l {\displaystyle n^{l}} . For simplicity, the width n L + 1 {\displaystyle n^{L+1}} of the readout vector z L {\displaystyle z^{L}} is taken to be 1. The parameters of this network have a prior distribution p ( θ ) {\displaystyle p(\theta )} , which consists of an isotropic Gaussian for each weight and bias, with the variance of the weights scaled inversely with layer width. This network is illustrated in the figure to the right, and described by the following set of equations: x ≡ input y l ( x ) = { x l = 0 ϕ ( z l − 1 ( x ) ) l > 0 z i l ( x ) = ∑ j W i j l y j l ( x ) + b i l W i j l ∼ N ( 0 , σ w 2 n l ) b i l ∼ N ( 0 , σ b 2 ) ϕ ( ⋅ ) ≡ nonlinearity y l ( x ) , z l − 1 ( x ) ∈ R n l × 1 n L + 1 = 1 θ = { W 0 , b 0 , … , W L , b L } {\displaystyle {\begin{aligned}x&\equiv {\text{input}}\\y^{l}(x)&=\left\{{\begin{array}{lcl}x&&l=0\\\phi \left(z^{l-1}(x)\right)&&l>0\end{array}}\right.\\z_{i}^{l}(x)&=\sum _{j}W_{ij}^{l}y_{j}^{l}(x)+b_{i}^{l}\\W_{ij}^{l}&\sim {\mathcal {N}}\left(0,{\frac {\sigma _{w}^{2}}{n^{l}}}\right)\\b_{i}^{l}&\sim {\mathcal {N}}\left(0,\sigma _{b}^{2}\right)\\\phi (\cdot )&\equiv {\text{nonlinearity}}\\y^{l}(x),z^{l-1}(x)&\in \mathbb {R} ^{n^{l}\times 1}\\n^{L+1}&=1\\\theta &=\left\{W^{0},b^{0},\dots ,W^{L},b^{L}\right\}\end{aligned}}} ==== ==== z l | y l {\displaystyle z^{l}|y^{l}} is a Gaussian process We first observe that the pre-activations z l {\displaystyle z^{l}} are described by a Gaussian process conditioned on the preceding activations y l {\displaystyle y^{l}} . This result holds even at finite width. Each pre-activation z i l {\displaystyle z_{i}^{l}} is a weighted sum of Gaussian random variables, corresponding to the weights W i j l {\displaystyle W_{ij}^{l}} and biases b i l {\displaystyle b_{i}^{l}} , where the coefficients for each of those Gaussian variables are the preceding activations y j l {\displaystyle y_{j}^{l}} . Because they are a weighted sum of zero-mean Gaussians, the z i l {\displaystyle z_{i}^{l}} are themselves zero-mean Gaussians (conditioned on the coefficients y j l {\displaystyle y_{j}^{l}} ). Since the z l {\displaystyle z^{l}} are jointly Gaussian for any set of y l {\displaystyle y^{l}} , they are described by a Gaussian process conditioned on the preceding activations y l {\displaystyle y^{l}} . The covariance or kernel of this Gaussian process depends on the weight and bias variances σ w 2 {\displaystyle \sigma _{w}^{2}} and σ b 2 {\displaystyle \sigma _{b}^{2}} , as well as the second moment matrix K l {\displaystyle K^{l}} of the preceding activations y l {\displaystyle y^{l}} , z i l ∣ y l ∼ G P ( 0 , σ w 2 K l + σ b 2 ) K l ( x , x ′ ) = 1 n l ∑ i y i l ( x ) y i l ( x ′ ) {\displaystyle {\begin{aligned}z_{i}^{l}\mid y^{l}&\sim {\mathcal {GP}}\left(0,\sigma _{w}^{2}K^{l}+\sigma _{b}^{2}\right)\\K^{l}(x,x')&={\frac {1}{n^{l}}}\sum _{i}y_{i}^{l}(x)y_{i}^{l}(x')\end{aligned}}} The effect of the weight scale σ w 2 {\displaystyle \sigma _{w}^{2}} is to rescale the contribution to the covariance matrix from K l {\displaystyle K^{l}} , while the bias is shared for all inputs, and so σ b 2 {\displaystyle \sigma _{b}^{2}} makes the z i l {\displaystyle z_{i}^{l}} for different datapoints more similar and
Generalized iterative scaling
In statistics, generalized iterative scaling (GIS) and improved iterative scaling (IIS) are two early algorithms used to fit log-linear models, notably multinomial logistic regression (MaxEnt) classifiers and extensions of it such as MaxEnt Markov models and conditional random fields. These algorithms have been largely surpassed by gradient-based methods such as L-BFGS and coordinate descent algorithms.
Genetic programming
Genetic programming (GP) is an evolutionary algorithm, an artificial intelligence technique mimicking natural evolution, which operates on a population of programs. It applies the genetic operators selection according to a predefined fitness measure, mutation and crossover. The crossover operation involves swapping specified parts of selected pairs (parents) to produce new and different offspring that become part of the new generation of programs. Some programs not selected for reproduction are copied from the current generation to the new generation. Mutation involves substitution of some random part of a program with some other random part of a program. Then the selection and other operations are recursively applied to the new generation of programs. Typically, members of each new generation are on average more fit than the members of the previous generation, and the best-of-generation program is often better than the best-of-generation programs from previous generations. Termination of the evolution usually occurs when some individual program reaches a predefined proficiency or fitness level. It may and often does happen that a particular run of the algorithm results in premature convergence to some local maximum that is not a globally optimal or even good solution. Multiple runs (dozens to hundreds) are usually necessary to produce a very good result. It may also be necessary to have a large starting population size and variability of the individuals to avoid pathologies. == History == The first record of the proposal to evolve programs is probably that of Alan Turing in 1950 in "Computing Machinery and Intelligence". There was a gap of 25 years before the publication of John Holland's 'Adaptation in Natural and Artificial Systems' laid out the theoretical and empirical foundations of the science. In 1981, Richard Forsyth demonstrated the successful evolution of small programs, represented as trees, to perform classification of crime scene evidence for the UK Home Office. Although the idea of evolving programs, initially in the computer language Lisp, was current amongst John Holland's students, it was not until they organised the first Genetic Algorithms (GA) conference in Pittsburgh that Nichael Cramer published evolved programs in two specially designed languages, which included the first statement of modern "tree-based" genetic programming (that is, procedural languages organized in tree-based structures and operated on by suitably defined GA-operators). In 1988, John Koza (also a PhD student of John Holland) patented his invention of a GA for program evolution. This was followed by publication in the International Joint Conference on Artificial Intelligence IJCAI-89. Koza followed this with 205 publications on "genetic programming", a term coined by David Goldberg, also a PhD student of John Holland. However, it is the series of 4 books by Koza, starting in 1992 with accompanying videos, that really established GP. Subsequently, there was an enormous expansion of the number of publications with the Genetic Programming Bibliography, surpassing 10,000 entries. In 2010, Koza listed 77 results where genetic programming was human competitive. The departure of GP from the rigid, fixed-length representations typical of early GA models was not entirely without precedent. Early work on variable-length representations laid the groundwork. One notable example is messy genetic algorithms, which introduced irregular, variable-length chromosomes to address building block disruption and positional bias in standard GAs. Another precursor was robot trajectory programming, where genome representations encoded program instructions for robotic movements—structures inherently variable in length. Even earlier, unfixed-length representations were proposed in a doctoral dissertation by Cavicchio, who explored adaptive search using simulated evolution. His work provided foundational ideas for flexible program structures. In 1996, Koza started the annual Genetic Programming conference, which was followed in 1998 by the annual EuroGP conference, and the first book in a GP series edited by Koza. 1998 also saw the first GP textbook. GP continued to flourish, leading to the first specialist GP journal and three years later (2003) the annual Genetic Programming Theory and Practice (GPTP) workshop was established by Rick Riolo. Genetic programming papers continue to be published at a diversity of conferences and associated journals. Today there are nineteen GP books including several for students. === Foundational work in GP === Early work that set the stage for current genetic programming research topics and applications is diverse, and includes software synthesis and repair, predictive modeling, data mining, financial modeling, soft sensors, design, and image processing. Applications in some areas, such as design, often make use of intermediate representations, such as Fred Gruau's cellular encoding. Industrial uptake has been significant in several areas including finance, the chemical industry, bioinformatics and the steel industry. == Methods == === Program representation === GP evolves computer programs, traditionally represented in memory as tree structures. Trees can be easily evaluated in a recursive manner. Every internal node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable). Non-tree representations have been suggested and successfully implemented, such as linear genetic programming, which perhaps suits the more traditional imperative languages. The commercial GP software Discipulus uses automatic induction of binary machine code ("AIM") to achieve better performance. μGP uses directed multigraphs to generate programs that fully exploit the syntax of a given assembly language. Multi expression programming uses three-address code for encoding solutions. Other program representations on which significant research and development have been conducted include programs for stack-based virtual machines, and sequences of integers that are mapped to arbitrary programming languages via grammars. Cartesian genetic programming is another form of GP, which uses a graph representation instead of the usual tree based representation to encode computer programs. Most representations have structurally noneffective code (introns). Such non-coding genes may seem to be useless because they have no effect on the performance of any one individual. However, they alter the probabilities of generating different offspring under the variation operators, and thus alter the individual's variational properties. Experiments seem to show faster convergence when using program representations that allow such non-coding genes, compared to program representations that do not have any non-coding genes. Instantiations may have both trees with introns and those without; the latter are called canonical trees. Special canonical crossover operators are introduced that maintain the canonical structure of parents in their children. === Initialisation === The methods for creation of the initial population include: Grow creates the individuals sequentially. Every GP tree is created starting from the root, creating functional nodes with children as well as terminal nodes up to a certain depth. Full is similar to the Grow. The difference is that all brunches in a tree are of same predetermined depth. Ramped half-and-half creates a population consisting of m d − 1 {\displaystyle md-1} parts and a maximum depth of m d {\displaystyle md} for its trees. The first part has a maximum depth of 2, second of 3 and so on up to the m d − 1 {\displaystyle md-1} -th part with maximum depth m d {\displaystyle md} . Half of every part is created by Grow, while the other part is created by Full. === Selection === Selection is a process whereby certain individuals are selected from the current generation that would serve as parents for the next generation. The individuals are selected probabilistically such that the better performing individuals have a higher chance of getting selected. The most commonly used selection method in GP is tournament selection, although other methods such as fitness proportionate selection, lexicase selection, and others have been demonstrated to perform better for many GP problems. Elitism, which involves seeding the next generation with the best individual (or best n individuals) from the current generation, is a technique sometimes employed to avoid regression. === Crossover === In genetic programming two fit individuals are chosen from the population to be parents for one or two children. In tree genetic programming, these parents are represented as inverted lisp like trees, with their root nodes at the top. In subtree cro
Pruning (artificial neural network)
In deep learning, pruning is the practice of removing parameters from an existing artificial neural network. The goal of this process is to reduce the size (parameter count) of the neural network (and therefore the computational resources required to run it) whilst maintaining accuracy. This can be compared to the biological process of synaptic pruning which takes place in mammalian brains during development. == Node (neuron) pruning == A basic algorithm for pruning is as follows: Evaluate the importance of each neuron. Rank the neurons according to their importance (assuming there is a clearly defined measure for "importance"). Remove the least important neuron. Check a termination condition (to be determined by the user) to see whether to continue pruning. == Edge (weight) pruning == Most work on neural network pruning does not remove full neurons or layers (structured pruning). Instead, it focuses on removing the most insignificant weights (unstructured pruning), namely, setting their values to zero. This can either be done globally by comparing weights from all layers in the network or locally by comparing weights in each layer separately. Different metrics can be used to measure the importance of each weight. Weight magnitude as well as combinations of weight and gradient information are commonly used metrics. Early work suggested also to change the values of non-pruned weights. == When to prune the neural network? == Pruning can be applied at three different stages: before training, during training, or after training. When pruning is performed during or after training, additional fine-tuning epochs are typically required. Each approach involves different trade-offs between accuracy and computational cost.
GeneXus
GeneXus is a low code, cross-platform, knowledge representation-based development tool, mainly oriented towards enterprise-class applications for web applications, smart devices, and the Microsoft Windows platform. GeneXus uses mostly declarative language to generate native code for multiple environments. It includes a normalization module, which creates and maintains an optimal database structure based on user views. The languages for which code can be generated include COBOL, Java, Objective-C, RPG, Ruby, Visual Basic, and Visual FoxPro. Some of the DBMSs supported are Microsoft SQL Server, Oracle, IBM Db2, Informix, PostgreSQL, and MySQL. GeneXus was developed by Uruguayan company ARTech Consultores SRL which later renamed to Genexus SA. The latest version is GeneXus 18, which was released on November 10, 2022.
Bioz
Bioz is a search engine for life science experimentation. == History == Bioz was founded by Karin Lachmi and Daniel Levitt. Lachmi is a scientist who completed her postdoc in molecular and cellular biology at the Stanford University School of Medicine. During her lab work she found little available data regarding preferable lab tools, reagents and related products for experimentation. There are 50,000 vendors selling 300 million scientific products. She decided to start the company in order to provide researchers with adequate information for that purpose. Co-founder Daniel Levitt is an entrepreneur who sold his company WebAppoint to Microsoft in the year 2000. He also co-founded the company StemRad. At Bioz, Lachmi serves as the Chief Scientific Officer and Levitt serves as the chief executive officer. Bioz claims to have over a million researcher-users from 196 countries. Among the investors are Esther Dyson and the Stanford-StartX Fund. The company's advisory board includes Nobel Laureates in Chemistry Michael Levitt, Roger Kornberg, and Ada Yonath. == Technology == The company uses artificial intelligence, machine learning and natural language processing in order to extract experimentation data from scientific articles, such as the products that researchers used, the companies that supply the products, the protocol conditions that researchers selected, and the types of experiments and techniques. The algorithm ranks products based on how frequently they were used by researchers in their experiments, how recently a product was used, and the impact factor of the journal. The algorithm's output is a Bioz stars score for each product that was mentioned in an article. Bioz is a data-driven platform for product recommendations, which is contrary to platforms such as TripAdvisor and OpenTable that are based on user-generated reviews and ratings. The recommendations and scoring system that the company has developed are meant to assist researchers with the process of developing future medications and finding cures for diseases. They are guided towards products and techniques that were previously used by other researchers when planning and performing experiments. The company's revenue is based on selling SaaS subscriptions to researchers in biopharma companies. They also charge product suppliers for content syndication.