This master's thesis describes the design of effective working artificial neural network in FPGA Virtex-5 series with the maximum use of the possibility of parallelization. The theoretical part contains basic information on artificial neural networks, FPGA and VHDL. The practical part describes the used format of the variables, creating non-linear function, the principle of calculation the single layers, or the possibility of parameter settings generated artificial neural networks.

The study has investigated what knowledge Swedish upper secondary school teachers, who teach mathematics in the courses 1a, 1b or 1c, express about the teaching of linear functions. Furthermore, the study investigated what teachers believe students need to learn, which instructional activities teachers believe they use and what difficulties teachers perceives in teaching. To investigate this semi-structured interviews were carried out with nine teachers, which in turn have then been analyzed using the PCK based tool CoRe together with thematic analysis. The results show that the participating teachers both address aspects of their teaching that are common to several teachers and that are unique to one teacher. The conclusion that can be drawn from the results is that the teachers express that students need to learn to: make everyday connections, understand the transition between and the meaning of representation and understand the concept of a function. The instructional activities used include: digital tools, review, assignments and unique practical exercises. The difficulties identified are: lack of prior knowledge, lack of interest in functions, modeling of linear functions, the parameters k and m, the notation f(x) and the difference between f(x)=a and f(a). / I studien undersöks vilken kunskap lärare som undervisar i kurserna matematik 1a, 1b eller 1c ger uttryck för i undervisningen av linjära funktioner. Vidare har studien undersökt vad lärare anser att elever behöver lära sig, vilka undervisningsmoment lärare anger att de använder samt vilka svårigheter lärare upplever kring undervisningen. För att ta reda på detta har semistrukturerade intervjuer med nio verksamma gymnasielärare genomförts, som sedan har analyserats med det PCK-baserade verktyget CoRe tillsammans med tematisk analys. Resultatet visar att de deltagande lärarna både tar upp aspekter kring sin undervisning som är gemensamma för flera lärare och som är unika för en lärare. Den slutsats som kan dras utifrån resultatet är att lärarna anser att elever behöver lära sig: att göra vardagliga kopplingar, förstå övergången mellan och innebörden av representationsformer samt förstå funktionsbegreppet. Vidare använder lärarna undervisningsmoment som: digitala verktyg, genomgångar, självständigt arbete i läromedel samt unika praktiska övningar. De svårigheter som lärarna identifierat är: bristande förkunskaper, bristande intresse av funktioner, modellering av linjära funktioner, parametrarna k och m, notationen f(x) samt skillnaden på f(x)=a och f(a).

Problems involving optimal sequential making in uncertain dynamic systems arise in domains such as engineering, science and economics. Such problems can often be cast in the framework of Markov Decision Process (MDP). Solving an MDP requires computing the optimal value function and the optimal policy. The idea of dynamic programming (DP) and the Bellman equation (BE) are at the heart of solution methods. The three important exact DP methods are value iteration, policy iteration and linear programming. The exact DP methods compute the optimal value function and the optimal policy. However, the exact DP methods are inadequate in practice because the state space is often large and in practice, one might have to resort to approximate methods that compute sub-optimal policies. Further, in certain cases, the system observations are known only in the form of noisy samples and we need to design algorithms that learn from these samples. In this thesis we study interesting theoretical questions pertaining to approximate and learning algorithms, and also present an interesting application of MDPs in the domain of crowd sourcing. Approximate Dynamic Programming (ADP) methods handle the issue of large state space by computing an approximate value function and/or a sub-optimal policy. In this thesis, we are concerned with conditions that result in provably good policies. Motivated by the limitations of the PBE in the conventional linear algebra, we study the PBE in the (min, +) linear algebra. It is a well known fact that deterministic optimal control problems with cost/reward criterion are (min, +)/(max, +) linear and ADP methods have been developed for such systems in literature. However, it is straightforward to show that infinite horizon discounted reward/cost MDPs are neither (min, +) nor (max, +) linear. We develop novel ADP schemes namely the Approximate Q Iteration (AQI) and Variational Approximate Q Iteration (VAQI), where the approximate solution is a (min, +) linear combination of a set of basis functions whose span constitutes a subsemimodule. We show that the new ADP methods are convergent and we present a bound on the performance of the sub-optimal policy. The Approximate Linear Program (ALP) makes use of linear function approximation (LFA) and offers theoretical performance guarantees. Nevertheless, the ALP is difficult to solve due to the presence of a large number of constraints and in practice, a reduced linear program (RLP) is solved instead. The RLP has a tractable number of constraints sampled from the original constraints of the ALP. Though the RLP is known to perform well in experiments, theoretical guarantees are available only for a specific RLP obtained under idealized assumptions. In this thesis, we generalize the RLP to define a generalized reduced linear program (GRLP) which has a tractable number of constraints that are obtained as positive linear combinations of the original constraints of the ALP. The main contribution here is the novel theoretical framework developed to obtain error bounds for any given GRLP. Reinforcement Learning (RL) algorithms can be viewed as sample trajectory based solution methods for solving MDPs. Typically, RL algorithms that make use of stochastic approximation (SA) are iterative schemes taking small steps towards the desired value at each iteration. Actor-Critic algorithms form an important sub-class of RL algorithms, wherein, the critic is responsible for policy evaluation and the actor is responsible for policy improvement. The actor and critic iterations have deferent step-size schedules, in particular, the step-sizes used by the actor updates have to be generally much smaller than those used by the critic updates. Such SA schemes that use deferent step-size schedules for deferent sets of iterates are known as multitimescale stochastic approximation schemes. One of the most important conditions required to ensure the convergence of the iterates of a multi-timescale SA scheme is that the iterates need to be stable, i.e., they should be uniformly bounded almost surely. However, the conditions that imply the stability of the iterates in a multi-timescale SA scheme have not been well established. In this thesis, we provide veritable conditions that imply stability of two timescale stochastic approximation schemes. As an example, we also demonstrate that the stability of a widely used actor-critic RL algorithm follows from our analysis. Crowd sourcing (crowd) is a new mode of organizing work in multiple groups of smaller chunks of tasks and outsourcing them to a distributed and large group of people in the form of an open call. Recently, crowd sourcing has become a major pool for human intelligence tasks (HITs) such as image labeling, form digitization, natural language processing, machine translation evaluation and user surveys. Large organizations/requesters are increasingly interested in crowd sourcing the HITs generated out of their internal requirements. Task starvation leads to huge variation in the completion times of the tasks posted on to the crowd. This is an issue for frequent requesters desiring predictability in the completion times of tasks specified in terms of percentage of tasks completed within a stipulated amount of time. An important task attribute that affects the completion time of a task is its price. However, a pricing policy that does not take the dynamics of the crowd into account might fail to achieve the desired predictability in completion times. Here, we make use of the MDP framework to compute a pricing policy that achieves predictable completion times in simulations as well as real world experiments.

In many optimization problems, the relationship between the objective and parameters is not known. The objective function itself may be stochastic such as a long-run average over some random cost samples. In such cases finding the gradient of the objective is not possible. It is in this setting that stochastic approximation algorithms are used. These algorithms use some estimates of the gradient and are stochastic in nature. Amongst gradient estimation techniques, Simultaneous Perturbation Stochastic Approximation (SPSA) and Smoothed Functional(SF) scheme are widely used. In this thesis we have proposed a novel multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for unconstrained as well as constrained optimization. The algorithm uses the smoothed functional scheme for estimating the gradient and the quasi-Newton method to solve the optimization problem. The algorithm is shown to converge with probability one. We have also provided here experimental results on the problem of optimal routing in a multi-stage network of queues. Policies like Join the Shortest Queue or Least Work Left assume knowledge of the queue length values that can change rapidly or hard to estimate. If the only information available is the expected end-to-end delay as with our case, such policies cannot be used. The QN-SF based probabilistic routing algorithm uses only the total end-to-end delay for tuning the probabilities. We observe from the experiments that the QN-SF algorithm has better performance than the gradient and Jacobi versions of Newton based smoothed functional algorithms. Next we consider constrained routing in a similar queueing network. We extend the QN-SF algorithm to this case. We study the convergence behavior of the algorithm and observe that the constraints are satisfied at the point of convergence. We provide experimental results for the constrained routing setup as well. Next we study reinforcement learning algorithms which are useful for solving Markov Decision Process(MDP) when the precise information on transition probabilities is not known. When the state, and action sets are very large, it is not possible to store all the state-action tuples. In such cases, function approximators like neural networks have been used. The popular Q-learning algorithm is known to diverge when used with linear function approximation due to the ’off-policy’ problem. Hence developing stable learning algorithms when used with function approximation is an important problem. We present in this thesis a variant of Q-learning with linear function approximation that is based on two-timescale stochastic approximation. The Q-value parameters for a given policy in our algorithm are updated on the slower timescale while the policy parameters themselves are updated on the faster scale. We perform a gradient search in the space of policy parameters. Since the objective function and hence the gradient are not analytically known, we employ the efficient one-simulation simultaneous perturbation stochastic approximation(SPSA) gradient estimates that employ Hadamard matrix based deterministic perturbations. Our algorithm has the advantage that, unlike Q-learning, it does not suffer from high oscillations due to the off-policy problem when using function approximators. Whereas it is difficult to prove convergence of regular Q-learning with linear function approximation because of the off-policy problem, we prove that our algorithm which is on-policy is convergent. Numerical results on a multi-stage stochastic shortest path problem show that our algorithm exhibits significantly better performance and is more robust as compared to Q-learning. Future work would be to compare it with other policy-based reinforcement learning algorithms. Finally, we develop an online actor-critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process(MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multistage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2015-12-16T11:02:24Z No. of bitstreams: 1 talespulinhoramos.pdf: 6134665 bytes, checksum: 349537ae72f568271488022944942fb6 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2015-12-16T11:20:33Z (GMT) No. of bitstreams: 1 talespulinhoramos.pdf: 6134665 bytes, checksum: 349537ae72f568271488022944942fb6 (MD5) / Made available in DSpace on 2015-12-16T11:20:33Z (GMT). No. of bitstreams: 1 talespulinhoramos.pdf: 6134665 bytes, checksum: 349537ae72f568271488022944942fb6 (MD5) Previous issue date: 2015-02-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O Sistema Interligado Nacional (SIN) apresenta cerca de 150 usinas hidráulicas e o planejamento de médio prazo contempla entre 5 e 10 anos de estudo, a representação do sistema à usinas individualizadas faz com que a resolução do problema seja muito custoso computacionalmente. Para isso, o sistema é representado a partir de sistemas equivalentes de energia. Existe um trabalho anterior onde foi realizado a flexibilização da modelagem do sistema, denominada modelagem híbrida, em que parte do sistema é representado através de sistemas equivalentes de energia e outra é representada à usinas individualizadas com a produtibilidade constante. Desta forma, consegue-se um maior detalhamento nos estudos de médio prazo mantendo a complexidade do sistema em um nível adequado computacionalmente. Este trabalho apresenta a modelagem híbrida entre sistemas equivalentes de energia e à usinas individualizadas, porém, considerando as não linearidades das usinas hidráulicas. As não linearidades das usinas basicamente se dão em relação a variação do nível do reservatório e da vazão defluente (vazão turbinada acrescida da vazão vertida), o que implica diretamente na geração hidráulica. A proposta consiste em modelar a geração hidráulica das usinas (Função de Produção Hidráulica - FPH), que é uma função analítica não linear e não convexa, por uma função linear por partes convexa que represente adequadamente a função de produção hidráulica analítica. Há um trabalho anterior onde a FPH é aproximada por uma função linear por partes em duas etapas, inicialmente a função é aproximada nas dimensões do armazenamento e do turbinamento e, em uma segunda etapa, é adicionado a contribuição do vertimento. Já neste trabalho, a FPH é aproximada por uma função linear por partes obtida em apenas uma etapa para as três dimensões a partir do algoritmo Convex Hull. Assim, é possível resolver o problema de médio prazo considerando parte do sistema representado de forma equivalente e outra parte de forma individualizada considerando a variação da geração hidráulica em função do volume armazenado, vazão turbinada e vertida (se houver influência no canal de fuga). / The National Interconnected Power System (NIPS) presents around 150 hydraulic plants and the medium term planning contemplates between 5 to 10 years of study, the representation of the system to individualized plants makes the problem impracticable in computing; then the system is represented from equivalent systems of energy. There is an alternative of modeling flexibility of the system named hybrid modeling, in which part of the system is represented through equivalent systems of energy and the other is represented to individualized plants with constant productivity. As a consequence, it is obtained greater detail in the long term studies, maintaining the complexity of the system in an adequate level in computing. This paper presents the hybrid modeling between equivalent systems of energy and individualized plants. However, it considers non-linearities on generation of hydraulic plants. The non-linear characteristic on generation function basically comes from the influence of the reservoir level (head term) and the release term (turbinated outflow added to spilled outflow). The suggestion is to model the hydraulic generation of the plants (Hydraulic Production Function - HPF), which is a non-linear and non-convex analytical function, into a convex piecewise linear function that represents appropriately the function of the analytical hydraulic production. It will be described in detail in this paper the technique used to obtain this piecewise linear function by applying the Convex Hull algorithm to guarantee the convexity of this function. To conclude, it is possible to solve the problem of long term considering part of the system represented by equivalent form and the other part in individualized manner considering the variation of the hydraulic generation in relation to the volume stored, turbaned and spilled outflow.