Academic literature on the topic 'Shortcut learning'

Traditional shortest path algorithms can efficiently find the optimal paths in graphs using simple heuristics. However, formulating a simple heuristic is challenging under the road network setting since there are multiple factors to consider, such as road segment length, edge centrality, and speed limit. This study investigates how a neural network can learn to take these factors as inputs and yield a path given a pair of origin and destination. The research question is formulated as: Are neural networks applicable to real-time route planning tasks in a roadnetwork?. The proposed metric to evaluate the effectiveness of the neural network is arrival rate. The quality of generated paths is evaluated by time efficiency. The real-time performance of the model is also compared between pathfinding in dynamic and static graphs, using theabove metrics. A staggered approach is applied in progressing this investigation. The first step is to generate random graphs, which allows us to monitor the size and properties of the training graph without caring too many details in a road network. The next step is to determine, as a proof of concept, if a neural network can learn to traverse simple graphs with multiple strategies, given that road networks are in effect complex graphs. Finally, we scale up by including factors that might affect the pathfinding in real road networks. Overall, the training data is optimal paths in a graph generated by a shortest path algorithm. The model is then applied to new graphs to generate a path given a pair of origin and destination. The arrival rate and time efficiency are calculated and compared with that of the corresponding optimal path. Experimental results show that the effectiveness, i.e., arrival rate ofthe model is 90% and the path quality, i.e., time efficiency has a medianof 0.88 and a large variance. The experiment shows that the model has better performance in dynamic graphs than in static graphs. Overall, the answer to the research question is positive. However, there is still room to improve the effectiveness of the model and the paths generated by the model. This work shows that a neural network trained to make locally optimal choices can hardly give a globally optimal solution. We also show that our method, only making locally optimal choices, can adapt to dynamic graphs with little performance overhead.<br>Traditionella algoritmer för att hitta den kortaste vägen kan effektivt hitta de optimala vägarna i grafer med enkel heuristik. Att formulera en enkel heuristik är dock utmanande för vägnätverk eftersom det finns flera faktorer att överväga, såsom vägsegmentlängd, kantcentralitet och hastighetsbegränsningar. Denna studie undersöker hur ett neuralt nätverk kan lära sig att ta dessa faktorer som indata och finna en väg utifrån start- och slutpunkt. Forskningsfrågan är formulerad som: Är neuronnätverket tillämpliga på realtidsplaneringsuppgifter i ett vägnät?. Det föreslagna måttet för att utvärdera effektiviteten hos det neuronnätverket är ankomstgrad. Kvaliteten på genererade vägar utvärderas av tidseffektivitet. Prestandan hos modellen jämförs också mellan sökningen i dynamiska och statiska grafer, med hjälp av ovanstående mätvärden. Undersökningen bedrivs i flera steg. Det första steget är att generera slumpmässiga grafer, vilket gör det möjligt för oss att övervaka träningsdiagrammets storlek och egenskaper utan att ta hand om för många detaljer i ett vägnät. Nästa steg är att, som ett bevis på konceptet, undersöka om ett neuronnätverk kan lära sig att korsa enkla grafer med flera strategier, eftersom vägnätverk är i praktiken komplexa grafer. Slutligen skalas studien upp genom att inkludera faktorer som kan påverka sökningen i riktiga vägnät. Träningsdata utgörs av optimala vägar i en graf som genereras av en algoritm för att finna den kortaste vägen. Modellen appliceras sedan i nya grafer för att hitta en väg mellan start och slutpunkt. Ankomstgrad och tidseffektivitet beräknas och jämförs med den motsvarande optimala sökvägen. De experimentella resultaten visar att effektiviteten, dvs ankomstgraden av modellen är 90% och vägkvaliteten dvs tidseffektiviteten har en median på 0,88 och en stor varians. Experimentet visar att modellen har bättre prestanda i dynamiska grafer än i statiska grafer. Sammantaget är svaret på forskningsfrågan positivt. Det finns dock fortfarande utrymme att förbättra modellens effektivitet och de vägar som genereras av modellen. Detta arbete visar att ett neuronnätverk tränat för att göra lokalt optimala val knappast kan ge globalt optimal lösning. Vi visar också att vår metod, som bara gör lokalt optimala val, kan anpassa sig till dynamiska grafer med begränsad prestandaförlust.

Randomness has proved to be a powerful tool in all of computation. It is pervasive in areas such as networking, machine learning, computer graphics, optimization, computational number theory and is "necessary" for cryptography. Though randomized algorithms and protocols assume access to "truly" random bits, in practice, they rely on the output of "imperfect" sources of randomness such as pseudo-random number generators or physical sources. Hence, from a theoretical standpoint, it becomes important to view randomness as a resource and to study the following fundamental questions pertaining to it: Extraction: How do we generate "high quality" random bits from "imperfect" sources? Randomization: How do we use randomness to obtain efficient algorithms? Derandomization: How (and when) can we "remove" our dependence on random bits? In this thesis, we consider important problems in these three prominent and diverse areas pertaining to randomness. In randomness extraction, we present extractors for "oblivious bit fixing sources". In (a non-traditional use of) randomization, we have obtained results in machine learning (learning juntas) and proved hardness of lattice problems. While in derandomization, we present a deterministic algorithm for a fundamental problem called "identity testing". In this thesis we also initiate a complexity theoretic study of Hilbert's 17th problem. Here identity testing is used in an interesting manner. A common theme in this work has been the use of tools from areas such as number theory in a variety of ways, and often the techniques themselves are quite interesting.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T15:18:49Z No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5)<br>Made available in DSpace on 2015-07-17T15:18:49Z (GMT). No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5) Previous issue date: 2015-02-26<br>The network optimization problems (NOP) are common to several areas such as engineering, transport and telecommunications, and have been objects of intense research and studies. Among the classical NOP are the problems of Shortest Path (SPP), Max Flow (MFP) and Traveling Salesman (TSP), which are usually studied in undergraduate and graduate courses such as Industrial Engineering, Computer Science, Information Systems and Logistics, with the use of resources such as chalk and blackboard that hinder the teacher's work, in the sense of showing the functioning of algorithms that solve these problems while maintaining students' motivation for learning. In this context, it is proposed in this research, a computational tool, characterized as a Learning Object (OA) and called TASNOP - Teaching Algorithms for Solving Network Optimization Problems, whose purpose is to contribute to students' understanding about concepts from NOP and, mainly, the functioning of algorithms A*, Greedy Search and Dijkstra used for resolution of SPP, Ford-Fulkerson employed in the resolution of MFP and the Nearest Neighbor to solve the TSP. It is important to highlight that the proposed OA can be accessed through web and also employed in distance learning environments (DLE). Experiments conducted in 2014 with 129 students of Computer Science, from which 51 performed an exercise using the TASNOP and 78 without this tool, confirm that students who used the TASNOP performed better in solving the proposed exercise, corroborating the idea that the OA helped to improve their understanding about the algorithms discussed in this research. In addition, the 51 students who employed the TASNOP answered a questionnaire about it use and, the answers indicated that the TASNOP shows a potential to be used as a learning support tool.<br>Os problemas de otimização em redes (POR) são comuns a diversas áreas como engenharia, transportes e telecomunicações, e têm sido objetos de intensas pesquisas e estudos. Entre os POR clássicos estão os problemas de Caminho Mínimo (PCM), Fluxo Máximo (PFM) e Caixeiro Viajante (PCV), os quais normalmente são estudados em cursos de graduação e pós-graduação tais como Engenharia de Produção, Ciência da Computação, Sistemas de Informação e Logística, com a utilização de recursos como giz e lousa, o que dificulta o trabalho do professor, no sentido de mostrar o funcionamento dos algoritmos que solucionam esses problemas, mantendo a motivação dos alunos para a aprendizagem. Neste contexto, propõe-se nesta pesquisa, uma ferramenta computacional, caracterizada como um Objeto de Aprendizagem (OA) denominado TASNOP - Teaching Algorithms for Solving Network Optimization Problems, cuja finalidade é contribuir para compreensão dos alunos sobre conceitos de POR e, principalmente, sobre o funcionamento dos algoritmos A*, Busca Gulosa, e Dijkstra, usados para resolução do PCM, Ford-Fulkerson empregado na resolução de PFM e o algoritmo Vizinho mais Próximo para resolução do PCV. É importante ressaltar que o OA proposto pode ser acessado via web e, inclusive, ser acoplado em ambientes de ensino a distância (EaD). Experimentos realizados no ano de 2014 envolvendo 129 alunos do curso de Ciência da Computação, dos quais 51 resolveram um exercício com o uso do TASNOP e 78 sem o seu uso, permitiram verificar que os alunos que utilizaram o TASNOP obtiveram melhor desempenho na resolução do exercício proposto, corroborando a ideia de que o OA contribuiu para melhorar suas compreensões acerca dos algoritmos abordados nesta pesquisa. Em adição, os 51 alunos que usaram o TASNOP responderam a um questionário sobre o seu uso e, com base nessas respostas, ficou evidente o potencial do TASNOP como uma ferramenta de apoio ao ensino.

Aujourd'hui, le problème de stationnement devient l'un des enjeux majeurs de la recherche dans la planification des transports urbains et la gestion du trafic. En fait, les conséquences de l'absence de places de stationnement ainsi que la gestion inadéquate de ces installations sont énormes. L'objectif de cette thèse est de fournir des algorithmes efficaces et robustes afin que les conducteurs gagnent du temps et de l'argent et aussi augmenter les revenus des gestionnaires de parking. Le problème est formulé comme un problème d'affectation multi-objectifs dans des environnements statique et dynamique. Tout d'abord, dans l'environnement statique, nous proposons de nouvelles heuristiques en deux phases pour calculer une approximation de l'ensemble des solutions efficaces pour un problème bi-objectif. Dans la première phase, nous générons l'ensemble des solutions supportées par un algorithme dichotomique standard. Dans la deuxième phase, nous proposons quatre métaheuristiques pour générer une approximation des solutions non supportées. Les approches proposées sont testées sur le problème du plus court chemin bi-objectif et le problème d'affectation bi-objectif. Dans le contexte de l'environnement dynamique, nous proposons une formulation du problème sous forme d'un programme linéaire en nombres entiers mixtes qui est résolue à plusieurs reprises sur un horizon de temps donné. Les fonctions objectives considérées, permettent un équilibre entre la satisfaction des conducteurs et l'intérêt du gestionnaire de parking. Deux approches sont proposées pour résoudre ce problème d'affectation dynamique avec ou sans phase d'apprentissage. Pour renforcer la phase d'apprentissage, un algorithme à estimation de distribution est proposé pour prévoir la demande future. Pour évaluer l'efficacité des algorithmes proposés, des essais de simulation ont été effectués. Aussi une mise en œuvre pilote a été menée dans le parking à l'Université de Valenciennes en utilisant une plateforme existante, appelée Context Aware Transportation Services (CATS), qui permet le déploiement dynamique de services. Cette plate-forme peut dynamiquement passer d'une approche à l'autre en fonction du contexte. Enfin cette thèse s'inscrit dans le projet SYstem For Smart Road Applications ( SYFRA)<br>The parking problem is nowadays one of the major issues in urban transportation planning and traffic management research. In fact, the consequences of the lack of parking slots along with the inadequate management of these facilities are tremendous. The aim of this thesis is to provide efficient and robust algorithms in order to save time and money for drivers and to increase the income of parking managers. The problem is formulated as a multi-objective assignment problem in static and dynamic environments. First, for the static environment, we propose new two-phase heuristics to calculate an approximation of the set of efficient solutions for a bi-objective problem. In the first phase, we generate the supported efficient set with a standard dichotomic algorithm. In the second phase we use four metaheuristics to generate an approximation of the non-supported efficient solutions. The proposed approaches are tested on the bi-objective shortest path problem and the biobjective assignment problem. For the dynamic environment, we propose a mixed integer linear programming formulation that is solved several times over a given horizon. The objective functions consist of a balance between the satisfaction of drivers and the interest of the parking managers. Two approaches are proposed for this dynamic assignment problem with or without learning phase. To reinforce the learning phase, an estimation of distribution algorithm is proposed to predict the future demand. In order to evaluate the effectiveness of the proposed algorithms, simulation tests have been carried out. A pilot implementation has also been conducted in the parking of the University of Valenciennes, using an existing platform called framework for context aware transportation services, which allows dynamic deployment of services. This platform can dynamically switch from one approach to another depending on the context. This thesis is part of the project SYstem For Smart Road Applications (SYFRA)

L'objectif de ce travail de thèse est de proposer des approches algorithmiques permettant de traiter la problématique du routage adaptatif (RA) dans un réseau de communication à trafic irrégulier. L'analyse des algorithmes existants nous a conduit à retenir comme base de travail l'algorithme Q-Routing (QR); celui-ci s'appuie sur la technique d'apprentissage par renforcement basée sur les modèles de Markov. L'efficacité de ce type de routage dépend fortement des informations sur la charge et la nature du trafic sur le réseau. Ces dernières doivent être à la fois, suffisantes, pertinentes et reflétant la charge réelle du réseau lors de la phase de prise de décision. Pour remédier aux inconvénients des techniques utilisant le QR, nous avons proposé deux algorithmes de RA. Le premier, appelé Q-Neural Routing, s'appuie sur un modèle neuronal stochastique pour estimer et mettre à jour les paramètres nécessaires au RA. Afin d'accélérer le temps de convergence, une deuxième approche est proposée : K-Shortest path Q-Routing. Elle est basée sur la technique de routage multi chemin combiné avec l'algorithme QR, l'espace d'exploration étant réduit aux k meilleurs chemins. Les deux algorithmes proposés sont validés et comparés aux approches traditionnelles en utilisant la plateforme de simulation OPNET, leur efficacité au niveau du RA est mise particulièrement en évidence. En effet, ceux-ci permettent une meilleure prise en compte de l'état du réseau contrairement aux approches classiques.

Дисертаційна робота присвячене розв'язання науково-технічної задачі зі створення інформаційної технології моделювання ефективного контролю за топологією однорангової мобільної радіомережі, що само налагоджується, тактичного рівня й управління зміною показників її функціонування в умовах впливу радіоперешкод та радіоелектронної протидії (РЕБ). У дисертаційній роботі вперше запропоновано нова топологія, що відрізняється від відомих тим, що включає елементи навчання поведінки мережі в умовах перешкод. Введені нові процеси інтелектуальної системи керування вузлом мобільної радіомережі: пошукова настройка рівня шумів або сигналу перешкоди на вхідному тракті комунікатора та контроль зв'язності комутації вузлів мобільної радіомережі. Запропоновано новий метод самонастроювання радіомережі на основі градієнтного підходу, що відрізняється від відомих, інтеграцією градієнтного алгоритму налаштування ваги сусідніх вузлів і пошуку найкоротшого маршруту в мережі, що підлягає впливу перешкод, що адекватно вирішення завдань ітераційної оптимізації. Отримано нові результати для моделювання радіомережі, що відрізняються від відомих тим, що виконано моделювання радіомережі на основі градієнтного алгоритму навчання, які підтверджуються теоретичними дослідженнями й практичними результатами. Запропоновано технологію автоматизованої обробки даних з графічним представленням топології радіомережі за допомогою геоінформаційної системи ArcGIS-10 американської компанії ESRI, яка дозволяє оцінити стійкість мережевої структури в динамічній зміні та виявити кордони стійкої зв'язності вузлів комутації радіомережі. Такий підхід є новою варіацією яка розширює межі розв'язання задачі розподілу трафіку і перешкодостійкості радіомережі з урахуванням структури мережевої топології. Практичне значення отриманих результатів моделювання та експериментальне дослідження підтвердило правильність запропонованих рішень та отриманих теоретичних результатів.<br>The scientific degree thesis is devoted to solve the task to create an efficient modeling technology for network topology of peer-to-peer mobile self-adaptive tactical military radio network and to manage the changing performance indicators of such radio network under radio frequency interference and defense. The scientific thesis first time offered a brand new topology differing from existing ones, that researches network behavior under circumstances of interference and radiofrequency defense. Innovative intellect management of mobile radio network node were introduced: search adjustment of the noise level or interference signal on entry of communicator and connectivity control of the radio network nodes. Main difference of current intellectual system is mechanism of data/knowledge storage and processing (knowledge base block) for efficient activities in uncertain (lack of information) and random circumstance. The knowledgebase contains the control system, it’s goals and management principles, decision making structure and the control object itself. The control system can be contributed with learning sub-system, that generalizes the accumulated experience, which is show on pic [55]. The subsystem for control, gathering, storage and processing of data measures mobile nodes and general radio network parameters. The decision making subsystem was build thinking about unification of control functions into independent groups to separate network management on subsystems and ensure easier math modeling of network management. The new gradient approach of self-adapted radio network was proposed, that differs from known methods by gradient setting of neighboring nodes weight and search of close path in network affected by interference. Dijkstra algorithm is a search procedure of the shortest path at weighted oriented graph. Algorithm works by steps, starting from first radio network node: on each step it refers to one node, and reduces marks and stops execution when all radio network nodes are visited. Dijkstra algorithm is resourceful, but given the knowledge of network topology and path to necessary peak, the router always knows an alternative route to the required node, in case of fall of any node of the path. Self-learning is a key feature for solving complex problems, that cannot be solved in usual way. The difficulty of constructing such network is to choose invariant features for describing of input data so the differences are caused only by random factors, such as noise. In this case, the informative features will be the vector representation of the symbols on which the noise component or interference was applied. Among the major types of neuro networks, including deep learning networks, the BP (back propagation) structure of neuro network is widely used, because it has features of self-adaptation, and recognition is computation-efficient. The algorithm of non-linear optimization (Levenberg–Marquardt algorithm) which is applied for search of minimal strategy – linear approximation and gradient descent. According to the simulation procedure, we determine the neural network BP with three layers. The initial structure has two layers, the number of neurons in the first layer is 33, and in the second - 27, which corresponds to the number of network outputs. The network training function allows to assess the quality of network configuration by constructing a regression line in which the proportionality factor allows to determine the degree of correlation between input and output data. In this case, there is a high degree of correlation between input and output data, R = 0.999. Training in this example results in an error of 1.52 · 10-5, due to the complexity of the output data. The learning took only eight epochs. The BP multilayer neural network self-adapting algorithm is a controlled algorithm. In fact, it's an iterative method of gradient search for the best parameters in these conditions, which is characterized by the simplicity of the classification task in terms of "input-output" and reliability. New results of radio network modeling are obtained. On the one hand, they differ from the known ones in that the radio network modeling is performed on the basis of gradient learning algorithm. On the other hand, the results are confirmed by theoretical researches and practical results. The proposed geo information technology of automated data processing with a graphical representation of the radio network topology using the geographic information system ArcGIS-10 of the American company ESRI, which allows to assess the stability of the network structure in dynamic change and identify the limits of stable connectivity of radio switching nodes. This approach is a new variation that expands the boundaries of solving the problem of traffic distribution and noise immunity of the radio network, taking into account the structure of the network topology. The practical significance of the obtained simulation results and experimental research confirmed the correctness of the proposed solutions and the obtained theoretical results.

碩士<br>國立臺灣師範大學<br>教育政策與行政研究所<br>103<br>The Shortcut to Professionals: A Case Study on Professional Learning Community of Chinese Independent School in Malaysia Abstract The purpose of this study was to understand the operation of teachers’ professional learning communities (PLCs) in Lotus Chinese Independent School in the past four years. The research aimed to explore how PLCs practices affected teachers’ professional growth in Lotus Chinese Independent School, including their professional capacity and sense of identity as teachers working in a Chinese Independent School. The research was a case study based on first-hand observation, document reviews, interviews with ten teachers and administrators in Lotus Chinese Independent School, and the resarcher’s reflection notes. The findings of the study were the following. Lotus Chinese Independent School adopted top-down leadership to promote the goal of providing students equal learning qualities. Led by various subject leaders, PLCs were built through cooperation, shared practice, and shared leadership. Senior teachers’ willing to take part also played a significant role to smooth the process. In addition, three obstacles (on the levels of institution, individual, and society, respectively) of the operation of PLCs were spotted. On the bright side, PLCs improved teachers’ professional capacity and advanced the professional conversations between senior teachers and less-experienced ones. It trimed the time needed for new teachers to fit in. On the down side, however, there were obstacles on both the levels of institution and individual which weakened teachers’ sense of identity as Chinese Independent School’s teachers. Based on these findings, suggestions are generated for the administrators, senior teachers, and new teachers of Lotus Chinese Independent School, as well as for other Chinese Independent Schools interested in starting their own PLCs and for the United Chinese School Committees Association of Malaysia (UCSCAM) on this regard. Suggestions for further studies are provided.