Aprendizaje automático para categorizar los veredictos Time-limit en jueces en línea

APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS VEREDICTOS TIME-LIMIT EN JUECES EN LÍNEA MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS IN ONLINE JUDGES TRABAJO FIN DE GRADO CURSO 2022-2023 AUTOR MIGUEL MENÉNDEZ GALINDO DIRECTORES PEDRO PABLO GÓMEZ MARTÍN MARCO ANTONIO GÓMEZ MARTÍN GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS VEREDICTOS TIME-LIMIT EN JUECES EN LÍNEA MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS IN ONLINE JUDGES TRABAJO DE FIN DE GRADO EN INGENIERÍA INFORMÁTICA AUTOR MIGUEL MENÉNDEZ GALINDO DIRECTORES PEDRO PABLO GÓMEZ MARTÍN MARCO ANTONIO GÓMEZ MARTÍN CONVOCATORIA: SEPTIEMBRE 2023 GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID SEPTIEMBRE DE 2023 DEDICATION To all students who have experienced the frustration of TLE throughout their learning process. 2 ACKNOWLEDGMENTS To Pedro and Marco for the time and patience invested in this work in the easy moments and especially in the difficult ones; it would not have been possible without them. 3 RESUMEN APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS VEREDICTOS TIME-LIMIT EN JUECES EN LÍNEA El uso de jueces en línea se ha popularizado como una herramienta para mejorar las habilidades de programación al medir la eficiencia de las soluciones y comprobar su cumplimiento de los requisitos del problema. Sin embargo, cuando una solución excede el tiempo límite, el juez proporciona poca información sobre la causa del error. Con el objetivo de mejorar la información en los veredictos ofrecidos por los jueces, este estudio propone extender su funcionalidad implementando un módulo de pistas. Este módulo será capaz de informar a los usuarios sobre la causa de los veredictos obtenidos, centrándose exclusivamente en los veredictos de tiempo límite excedido o TLE. Para lograr este objetivo se plantea clasificar los veredictos TLE en tres categorías: bucles infinitos, planteamientos erróneos y soluciones poco óptimas. El módulo clasifica las soluciones haciendo uso de una pieza capaz de predecir el orden de complejidad de una solución envíada al juez, cronometrando su tiempo de ejecución para una serie de casos de prueba. Para esta pieza existen dos implementaciones, una basada en modelos de inteligencia artificial y otra basada en funciones de regresión. El objetivo de este trabajo consiste en mejorar la experiencia de usuario al utilizar jueces en línea, sin reemplazarlos, aumentando la cantidad de detalles información proporcionada por el sistema de veredictos en los jueces en línea. Palabras clave Juez en línea, Veredicto, TLE, Modelo de IA, Funcion de regresion. 4 ABSTRACT MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS IN ONLINE JUDGES The use of online judges has become popular as a tool to improve programming skills by measuring the efficiency of solutions and checking their compliance with problem requirements. However, when a solution exceeds the time limit, the judge provides little information about the cause of the error. In order to improve the information in the verdicts provided by judges, this study proposes to extend its functionality by implementing a clue module capable of informing users about the cause of the obtained verdicts, focusing exclusively on time-limit exceeded or TLE verdicts. To achieve this goal, we propose to classify TLEs into three categories: infinite loops, wrong approaches and suboptimal solutions. The module classifies the solutions by making use of a part capable of predicting the order of complexity of a solution sent to the judge, timing its execution time for a series of test cases. For this part there are two implementations, one based on artificial intelligence models and the other based on regression functions. This work aims to improve the user experience when interacting with online judges, without replacing them, by increasing the amount of detailed information provided by the verdict system on the online judges. Key words Online judge, Verdict, TLE, AI model, Regression function. 5 Content index Chapter 1 - Introduction........................................................................................................... 1 1.1 Motivation.........................................................................................................................1 1.2 Objectives.........................................................................................................................2 1.3 Work plan..........................................................................................................................3 1.4 Project repository............................................................................................................. 4 Chapter 2 - State of the art.......................................................................................................5 2.1 Introduction...................................................................................................................... 5 2.2 Online judges................................................................................................................... 5 2.3 Execution time measurement........................................................................................ 9 2.4 Sequential machine learning models based on supervised learning.....................10 2.5 Regression algorithms with supervised learning......................................................... 14 Chapter 3 - Application architecture....................................................................................16 3.1 Project structure.............................................................................................................16 3.2 Complexity order predictor.......................................................................................... 19 3.3 Execution time measurer.............................................................................................. 20 3.4 Data model...................................................................................................................... 22 Chapter 4 - Complexity predictor based on Neural Networks...........................................23 4.1 Pseudo-random generator of training data...............................................................24 4.2 Classifier based on neural networks............................................................................ 26 Chapter 5 - Complexity predictor based on regression functions.....................................29 Chapter 6 - Validation of the complexity predictor module based on regression..........31 6.1 Generic validations....................................................................................................... 31 6.2 Specific validations........................................................................................................34 Chapter 7 - Conclusions and future work............................................................................. 37 7.1 Conclusions.....................................................................................................................37 7.2 Future work..................................................................................................................... 38 Chapter 8 - Bibliography..........................................................................................................40 6 Figure index Figure 1: Sequential model..............................................................................................12 Figure 2: Recurrent sequential model..............................................................................12 Figure 3: Usage of activation functions............................................................................13 Figure 4: Clue module use case...................................................................................... 16 Figure 5: Data flow in the clue module.............................................................................18 Figure 6: Diagram of the inner flow of the clue module................................................... 19 Figure 7: Complexity predictor diagram...........................................................................19 7 Table index Table 1: Problems evaluated by the module.............................................................. 33 Table 2: Module precision classified by complexities.................................................33 Table 3: Erasmús solution measurements................................................................. 35 Table 4: Complexity predictions of the solutions to Erasmús.....................................36 8 ●[PE] Presentation Error: the provided solution generates the correct outputs, but the space and tab format is not correct. ●[WA] Wrong Answer: the uploaded solution is wrong as it does not generate the output defined by the problem statement for at least one of the provided inputs. ●[CE] Compilation Error: the judge wasn’t able to compile the given solution. ●[RTE] Run Time Error: the user's solution raises an exception during execution, for example dividing by zero. ●[TLE] Time Limit Exceeded: the provided solution couldn’t generate an output in the timeframe defined for this problem. ●[MLE] Memory Limit Exceeded: the uploaded solution exceeded the maximum memory limit allowed during execution. ●[OLE] Output Limit Exceeded: the users solution exceeded the maximum number of output characters during execution. ●[RF] Restricted Function: the solution performed an operation that the judge considered dangerous and aborted its execution. ●[IE] Internal Error: the judge suffered a problem during execution external to the solution under evaluation. ●[IQ] In Queue: the solution is in the queue and hasn’t been analyzed yet. From a regular user’s point of view, each of this verdicts indicate a different problem in the uploaded solution and thus should focus on different ideas in order to find and solve the problem, these being: ●PE: the user should review all of the line endings and spacings in the format used to generate the output. ●WA: verify the statement in order to ensure it has been correctly interpreted, also test the limit cases or large inputs in order to verify the output. ●RTE: similarly to the previous verdict, verify the more special cases in order to ensure the program doesn't break while processing them. ●TLE: review the algorithm checking if it may be further optimized or implemented in a different way reducing its complexity. ●MLE: analyze how the program processes data and try to find a way that stores less amounts for generating the outputs. ●OLE: verify that the program correctly detects the end of the input data and what is being written to the output. When defining problems in an online judge, problem setters usually have an objective in mind like limiting the complexity of accepted solutions or force them to process data without storing it in a clever manner. For example a problem setter may define a problem so that users can practice sorting algorithms. The objective in mind may be to accept only efficient solutions, forcing users to figure out faster sorting 7 algorithms to solve the problem in efficient complexities like O(n*log(n)). This is achieved by defining a small time frame for solutions to generate their output and large provide test cases for the evaluation process. If the problem is intended for beginners, the problem setter may then raise the maximum time available in order to also accept solutions of O(n²) and lower the test case size, considering as valid bubble sort algorithms as well. Another example, this time regarding memory usage, is forcing users to implement solutions that read and process data without storing it, by setting a small memory amount allowed and providing large test cases. As shown by the previous examples, time and memory limits are very important, and problems with high TLE or MLE verdicts usually are designed for users to face them and improve their solutions in a specific way. This information about a problem can give a hint on where its difficulty resides, this is the reason why participants in competitive programming are only allowed to see their own verdicts. Problem setters face a complex task when defining these limits, as judges usually support multiple programming languages for users to solve problems and each language has a different processing speed. For example comparing Java and C++, a O(n²) solution in C++ may be quicker than a O(n*log(n)) solution in Java for small enough test cases. This presents a big challenge for problem setters as they need to define limits and test cases that slow languages can achieve, while also limiting more complex solutions in quicker languages. To solve this issue, problem setters usually need to design a variety of solutions in multiple languages, some more efficient and some purposely slow in order to measure the time and memory usage and accurately define these limits. From a regular user’s point of view, receiving TLE as a verdict usually causes a lot of frustration as beginner programmers usually try to further optimize their solution that in most cases has the wrong complexity. This ends up in multiple uploads of the same solution without any real improvement towards the desired solution and tends to make users think the problem setter was too strict when defining the time limit. On the other hand, more experienced developers that code an algorithm with the right complexity completely redo their solution, thinking they are suffering from the previously mentioned case. In both of the cases mentioned above the judge generates a TLE verdict lacking further details on the root cause of the error, which could be very helpful towards the user. In fact it could provide extra information about how to solve the problem, this information shouldn’t be specific to the current problem but treat the issue generically. For example when receiving a WA verdict, the judge could provide the test case that failed to the user so that it can be validated locally and corrected. The goal behind this 8 project is to generate clues, similar to the one described for WA verdicts applied to TLEs. The generic clue proposed is to determine in which of the following categories the TLE found in the evaluated solution falls into: ●Caused by an infinite loop: the solution contains an infinite loop that prevents execution from terminating, resulting in exceeding the time limit. ●Caused by wrong complexity: the uploaded solution uses an algorithm with a complexity worse than the one expected by the problem statement. ●Caused by lack of optimization: the given solution utilizes an algorithm that does have the expected complexity but the implementation is too inefficient. After this classification, the judge would be able to provide the user with a generic clue, complementing the TLE verdict, that further informs him about the root cause of the error and how to treat it. This should result in less frustration for users while utilizing the online judge and a lower amount of wrong consecutive uploads of solutions with the same underlying problem. 2.3 Execution time measurement Time measurements are a fundamental part of the evaluation process of a program's performance, but achieving accurate results can be very difficult due to different factors. In computer systems there are a multitude of processes running in the background and the execution time of a specific program may be affected by the rest. Also consecutive executions of the same program may result in different measurements due to different factors such as having the data on disk or on cache as their access speeds are very different. The most common problems found while measuring execution times are the following: ●Variability in results: Execution times of the same program may vary among consecutive executions due to external factors like the current system’s load or fluctuations in the system’s resource. ●Noise: The operating system and other background processes may interfere with the process being measured negatively impacting the accuracy of the measurements. ●Tools: the use of inadequate tools for measuring the execution times may also introduce errors on the measurements. ●Clock resolution: choosing a resolution that fits the kind of programs that will be executed is key as for example, measuring quick processes in milliseconds may result in similar results while measuring different size executions. 9 When measuring solutions, the judge launches a process for the solution with a set of test cases, measuring the duration of this process and obtaining the execution time. This can be a problem because it also considers as execution time the creation and termination of the process. This time may contaminate the measurements as that time might not be negligible with respect to the rest of the processing time, especially in languages that require the startup of a VM such as Java. Three of the most important factors to consider when facing the problem of runtime measurement are the operating system, the hardware and the program to be measured itself. In addition, it is important to carefully choose the tools used to both measure and analyze the data as they have a great impact on the results [3]. Other helpful actions that can be taken in order to further improve the accuracy of the measurements are having solutions evaluate multiple cases per execution and measuring each execution multiple times. The first mitigation measure consists of having the measured problem evaluate multiple test cases on each execution, this results in an increased execution time which mitigates the clock resolution issue. It also reduces the impact of the time used in the creation and termination of the process but increases the probability of external processes interfering as execution time is longer. The second mitigation measure consists of measuring each execution multiple times for the same set of test cases and then calculating the mean. This action considerably reduces the noise contained in the measurements, this technique is not often used by online judges but it will be used in this project as precision is key [4]. 2.4 Sequential machine learning models based on supervised learning As mentioned earlier in this paper, the objective of this project consists of providing clues to users that obtained TLE verdicts in judges. It is intended to achieve this by determining the type of TLE the user is facing and informing about its root cause. To achieve this, it is necessary to find out the complexity of the solution the user uploaded to the judge, one possible approach is to use automatic learning. Algorithms based in automatic learning enable machines to learn and make decisions using a set of training data, composed of input values and their expected outputs. This enables the algorithm to validate its own predictions during the training process. Algorithms of this kind are based on the capacity machines have to detect patterns and relationships found in data, enabling them to classify and predict new cases basing their decisions on what they have learned during training. For this project it is required to design a system capable of receiving as an input an user's solution, or a set of data obtained from this solution and produce as an output 10 the complexity order it belongs to. The issue is we don't know how to design such a program, to solve this we intend to search solutions that use an automatic learning algorithm to generate the predictions based on gathered data. The main idea is to use as input data a set of measurements performed in the users solution, the measurements contain execution time and size of the executed test case. The output should be the complexity order of the evaluated solution. There exist many different kinds of models inside the supervised automatic learning algorithms category, each with their own advantages and disadvantages. For this project we will focus on neural networks, this implementation will be further discussed in chapter 4 of this paper, but in this section we will introduce the topic. There are multiple types of neural networks, a very common type are sequential models. These kinds of networks are formed by layers of neurons located one after another, forming a sequence. The initial layer serves as the input point for the model and contains one neuron per input value that the model will receive. Similarly the last layer of the sequence serves as the output point of the network and contains one neuron per output value. The intermediate layers are in charge of transforming the input data into the expected output values. Each neuron is connected to all of the neurons in the next layer on the sequence and each connection has a weight associated with it. Using these connections and their respective weights, the value received in one neuron is transformed into a new value and transmitted into each of the neurons on the next layer. This process is carried out until reaching the last layer where the output of the network is generated for the input data provided in this execution. The following figure shows a general diagram of a neural network with three inputs, one output and one intermediate layer formed by three neurons. Figure 1: Sequential model 11 As mentioned above, in sequential models data starts at the input layer and traverses the network in a single direction until reaching the last layer of the sequence. There also are more complex types of networks in which the flow of information is not only sequential. Some neurons may include a cyclic flow of data feeding data into themselves as well as forward in the network, this enhances their ability to remember and reuse information from previous steps while processing data. This is specially useful in tasks such as language processing, text generation, translations and sequential data analysis like time sequences. The following figure aims to show how this cyclic data flow applies in a diagram similar to the one observed earlier. Figure 2: Recurrent sequential model As we have already discussed, each layer is formed by a number of neurons which are connected to each of the neurons on the next layer of the sequence with the exception of the output layer. As previously explained, each of these connections has a weight associated that helps determine the value transmitted to the neuron targeted by the connection. To determine the value received by a neuron, the network must iterate through all the neurons of the previous layer, multiplying the value stored in each neuron by the associated weight value of each connection. Then it performs a sum of all these values and applies a function to the result of this operation, this function is known as the activation function. The output of this function is the value that the neuron on the next layer receives. We have also mentioned earlier a recursive flow of data, regarding neurons connected to themselves to use data from previous steps during execution. These connections also have a function associated with them that is utilized in order to generate the value transmitted through this connection. These functions are called 12 recurrent activation functions. The following figure contains a diagram showing the calculation process of the value fed into a neuron based on the neurons located on the previous layer of the network. Figure 3: Usage of activation functions After building the structure of a neural network model, there are two more steps needed in order for the model to be used. First it needs to go through a training phase, during which it will adjust the values associated with all of its internal parameters, like the previously mentioned weights. For this process the model needs to be provided with a large set of information, the training dataset, which needs to contain a set of samples formed by input values and their expected outputs. This enables the model to process the data and compare the generated output with the one in the training data and adjust the parameter values trying to minimize this error. During this process there are two other parts of a neural network model that come into play, the loss function and the optimizer. The loss function is used by the network in order to determine the error contained in the predictions it generates. The optimizer works alongside the loss function in order to minimize the error informed by this function. There are many available options for these two pieces and the choice is influenced by the type of data the model will process but the optimal values are only found by trial and error. The same idea applies to determining the inner structure of the network. The amount of layers, what type of neurons and how many should each layer have and the activation functions they use can only be determined through an iterative process based on trial and error. 13 2.5 Regression algorithms with supervised learning Artificial intelligence models may be classified inside two large categories, depending on the problems they are designed to solve. There are classification models that receive a set of input variables and determine to which group they belong among a set of predefined categories. For example, given a set of characteristics of an animal, determine if it is a dog, a cat or a fish. The other group is regression models which receive a set of input values and produce as an output a continuous value, for example given a set of characteristics of a house, determine the price. Inside the supervised learning category, there exist models designed to solve problems of both of the previously mentioned types. Focusing on regression problems, one approach consists of using a mathematical function in order to approximate the output values based on the available inputs. Depending on the class of the function used for these approximations there exist linear regression models, quadratic, polynomic etc. Above mentioned neural network models can solve regression problems as their output is a number. At the same time they can also solve classification problems by customizing its output, either by assigning numerical values to each category or by defining the output as the probability of the input data belonging to a certain category. Regression functions as mentioned above are classified into different groups depending on the class of the function they use to generate their output. For example, let's analyze how a linear regression model works. First the model defines a generic function of the class it belongs to, in linear regression the function is y = a + b * x, where a and b are parameters, x is the input value and y is the output. After this declaration, the model is trained using a dataset that contains inputs and their expected outputs. During this process the model produces values for the parameters that appear in the function, trying to minimize the error produced by the function when evaluating the training dataset. Once this process is completed, the model substitutes the calculated values for each parameter and becomes ready to predict new cases. Other kinds of regression models work in a similar fashion but using a different mathematical function as a basis and a different amount of parameters. The kind of model used to solve a problem depends on the information it has available and the relation this data has with the output values. Algorithms based on regression may use one or more of these models in order to train a system capable of generating numerical predictions given some input information. They are used in a wide variety of scenarios, for example economic predictions, market analysis, financial risk evaluation among others. 14 So far we have looked at what regression models are, how they work and some of their typical applications, but the problem discussed in this paper is clearly a classification problem. As mentioned earlier, the problem consists in classifying solutions into a set of complexity orders. A regression model is not the typical approach to solve these kinds of problems but as it is based on complexity orders it can be very useful. In chapter 5 of this paper we will discuss how we may apply regression to in order to predict the complexity of a given solution. But the idea behind this implementation is based on the fact that complexity orders are based on mathematical functions. By evaluating the measurements of a solution with a set of regression functions, one for each considered complexity and comparing the error they produce, it is possible to determine to which complexity the analyzed solution belongs. 15 Chapter 3 - Application architecture The purpose of this project is to design a module that extends the functionality of already existing online judges. The goal of this system is providing users with extra information about the wrong verdicts obtained, focusing on solutions that result in a TLE error. 3.1 Project structure This section will discuss a theoretical structure for the proposed implementation of the module in an online judge, analyzing the parts that compose it, how each of them work and the connection to the judge itself. The first thing is to define the use case for an online judge in which the module should come into play in order to further determine how it should be integrated. As shown in the figure below, the case starts with the user submitting a solution to the judge, then it gets evaluated as a TLE and fed into the clue module. Figure 4: Clue module use case At this point, the module should receive a solution and any other data relevant in order to evaluate it and determine which of these TLE types it contains: ●Infinite loop: solutions that contain an infinite loop and their execution never terminates. ●Wrong complexity: solutions that solve the problem with a complexity greater than the one expected by the statement. ●Wrong optimization: solutions that have the right complexity but their implementation is not optimized enough. 16 Chapter 4 - Complexity predictor based on Neural Networks In the previous chapter we have described the design for the clue module and its needed inner system in order to achieve the desired results. One of its key elements is the complexity order predictor, this piece of software receives as an input a set of execution times and sizes measured from executing a solution with a series of test cases. With this input data the system determines the complexity order in which the evaluated solution can execute the test cases processed. As mentioned earlier in this paper, this module may be implemented in many different ways and during this project we will explore two different approaches, both based in supervised automatic learning. During this kind of learning process first the model gets executed with a set of known cases that contain both the input data and the solution. When designing solutions in this context it is very important to choose a data model that contains enough information for the classifier to predict the desired variables. In our case the model receives a set of execution time and size pairs as an input and is expected to produce as an output the complexity order of the data provided. In order to train a machine learning model the first requirement is a training data set that consists of a large number of solved cases with the input data and the desired output to be produced. This set must be large enough for the algorithm to learn how to solve the problem and not the individual cases in the list. At the same time the dataset must have a good balance of difference among cases. With cases too different it won't be able to predict them with sufficient precision to be useful but if they are very similar it won't be able to predict new cases with the expected precision. It is also important to have the train data be as similar as possible, if not equal to the real data this model will face in its end application. This will ensure that the training process and observed precision will apply correctly to the real cases. The last part before training is deciding what model will be used for this process and designing its inner implementation, this is partly dependent on the input and output data, as well as the characteristics of the information it will process. But it is not a trivial process and it requires a lot of room for trial and error on the developer side in order to maximize its potential. During this paper there exist two different proposals for model implementations, one based on neural networks and the other based on regression. This chapter and the next one will describe each of the implementations respectively but 23 before diving into the first model implementation the next section will explain how the training data used for both models was obtained. 4.1 Pseudo-random generator of training data As previously mentioned, training data is one of the most important parts to consider when solving a problem by using artificial intelligence algorithms based on supervised automatic learning. For this project there was no real data collection available to use as the training data, this could be gathered for example from an online judge during a set amount of time. But generating this real data by hand is too costly so this option was completely discarded. The only viable solution left unexplored was to generate synthetic data for the training process by implementing a program with these specifications. Then tune the program in order to produce data as close to real measurements as possible. This can be achieved by applying different noise percentages, multiplicative constants or sizes among other parameters. The implementation of this program takes as a basis the meaning behind complexity orders, they are functions that represent the execution cost of a program given an input length. The complexity order of an algorithm may be represented as O(f(n)) where f(n) is a mathematical function that depends on n, the input size. There exist an infinite number of complexities, as an algorithm's cost may be represented by any function. But they are grouped into complexity orders to clarify how the cost grows compared to the input size of the cases processed by the algorithm. Now let's discuss the actual function that describes the complexity, f(n). These functions are also infinite so in order to analyze them, we look at the elements depending on n it contains. For example, let's take this function f(n) = 2*n*log(n) + 3, in order to categorize it into a complexity order first we would identify and remove any values that are not dependent on the input variable. This simplifies the function to f(n)=n*log(n), now we can easily categorize this function into the linear logarithmic order. This is referred to as BigO notation and it narrows down the amount of possible orders drastically. Most of the algorithms implemented to solve problem statements in online judges fall into one of these categories, which will be the ones considered by the classifier algorithms implementations proposed in this paper: ●O(1) - Constant ●O(log(n) - Logarithmic ●O(n) - Linear ●O(n*log(n)) - Linear Logarithmic 24 ●O(n2) - Quadratic ●O(n3) - Cubic The objective of the complexity order classifier, as its name implies, is to determine in which of these categories an evaluated solution falls into, given a set of samples containing pairs of execution time and input size. The pseudo random generator then needs to be able to generate these sets of execution time and size for each of the complexity orders considered by the classifier. To achieve this first it is necessary to realize what makes a set of execution time and size pairs belong to a complexity order. When interpreted as points in a two dimensional grid, they must draw a line or curve that is based on the one drawn by the function that represents the complexity order it belongs to. In order to produce the synthetic training data, the generator program will first calculate mathematical functions similar to the original functions that describe each complexity order. Taking these functions, it will calculate their value at a certain number of points and compose in this manner a set of execution time and size pairs to be added to the training dataset, and also add the complexity to which they belong. This process would generate a set of training cases far too ideal, this is a problem because as previously mentioned in section 2, time measurements are full of noise and imperfections. So this program must be able to reproduce these imperfections in the data it generates, to achieve this behavior the program introduces noise into the values generated. It is important to note that a second version of this program was also implemented, sharing most of the ideas described so far in this section but with a small difference. Instead of generating the execution time value by mathematical operations based on the complexity order chosen, the program performs a loop of that complexity and inside it makes an arithmetic operation, all while measuring the execution time. For example, in order to generate a linear test case, the program first chooses an operation to perform, for example the logarithm of a three digit number. Then it performs this operation n times, to simulate a linear complexity and measures the execution time. Performing this operation multiple times ends up building a training sample similar to the ones obtained by the other proposed implementation. This approach produces results far more similar to real data, but it takes a lot more time to generate these results for higher complexities. Both of the described implementations produce data following the same format, it generates a file that contains one case per line, each line contains a set of execution time measurements and the size used as well as the complexity order they belong to. 25 During the testing and implementation phase of both implementations described in this paper, there have been several train dataset generations, ranging from small files considering only one complexity order to large ones with all of them. The largest files contained around 4 million cases and the smallest around 12.000. 4.2 Classifier based on neural networks After solving the training data problem described in the previous section, we will focus again on the complexity order predictor, specifically in the first implementation that is based on a neural network model. This model will use the generated train data in order to learn how to predict complexity orders based on time measurements and sizes, aiming to achieve the maximum possible accuracy. As stated in the introduction, this section will cover how a neural network model was implemented in order to determine a solution’s complexity. In order to define a model of this kind, you need to define the three main parts it is composed of: ●Input layer: the shape of this layer defined by what data the model will receive in order to generate predictions. ●Internal layers: the internal structure of the model, this is in charge of transforming the input data, through different kinds of operations, into the output data. ●Output layer: this layer’s structure is defined by the information that the model will generate as a result. As we have defined in the training data, the model will receive a set of execution time and size pairs, so the model will have two inputs per pair. The number of pairs used in this implementation is three, as this is the lowest possible number of points needed to differentiate a curve from a straight line. Increasing this number would improve the model’s capabilities to predict with greater accuracy, but it also greatly increases the cost, as each pair needs to be executed and measured. For this reason we will start by assuming that three measurements are enough, and we will define the input layer of our model with six inputs. Regarding the output layer, our model needs to determine to which of the supported categories the given input belongs. Usually neural networks output a numeric value, and for this specific case, a numeric value could be assigned to each possible complexity and interpret them after. But there exists a much better approach usually used to produce this kind of output from a neural network classifier, this was the chosen solution. It consists of having as an output an array of numbers, one for each of the possible categories the input may belong to, showing the probability of the input belonging to the category the number represents. All the numbers in the list range their 26 value between zero and one; also the sum of all this set of numbers should be one. The advantages of this approach against assigning each category a numerical value and having only one output is that it provides more information about the prediction. In the case of one numerical value it can be hard to correctly interpret a decimal value, not knowing among which categories the predictor is doubting. On the array approach, you can easily see what chance each possible outcome had and treat this information as you see fit. For these reasons, the output layer of the model contains six layers, one for each of the complexities considered in this project. Finally lets discuss the inner layer structure of the model, this is where most of the choices lay and what will mostly determine the performance of the algorithm. As there are many available options and there is no way to know which suits this problem best, the chosen approach was to test different kinds of layers and structures. Is during this process where the previously obtained training data starts to come into play, first the dataset gets splitted into two groups, a training set and a testing set, usually at a 70-30 ratio. Then the model is trained with the training set, composed of most of the data; and evaluated with the testing set, that is unknown to the model at this point. This process intends to show the accuracy of the model during training but also when presenting it with new test cases that have never been evaluated before. For this trial process the generated datasets ranged from 400.000 test cases to 4.000.000, with noise range values from 5 - 25 %. During this process it was also taken into consideration removing some of the more rarely seen complexity orders such as cubic or constant complexities to try to improve the observed results. But accuracy scores ranged between 50 - 80% at best. Also different layer types and amounts were considered, as well as the amount of neurons per layer. Regarding layer types, LSTM and GRU were the best performing ones, as they shine the most when addressing problems related to sequential data, as are time series used in this classification problem. Stacked layers of these types are capable of extracting complex patterns in the processed data, as may be the complexity in which time increases in respect to size. LSTM layers are a more complex version of GRU layers, they can extract more complex information from the input data at a higher resource cost. But having considered models with both of these layer types as well as simple Dense layers, the increase in accuracy was not enough in order to find these models viable. Regarding the amount of neurons per layer, tests have ranged from small layers with 8-12 neurons to larger ones up to 200. Again the results have not been very promising, with 64 neurons per layer obtaining close to the best accuracy while keeping the resource cost much lower. Finally stacking layers is another important part of defining the inner structure of a neural network, tests have ranged from one very large layer, even considering 1000 neurons in this case, to stacking five to ten smaller 27 layers with the neuron amounts previously discussed. In this matter, the best compromise between resource cost and accuracy was four layers with 64 neurons each. All of the previously mentioned models were implemented and tested using notebooks in Python, as it provides easy access to neural network libraries with a wide variety of high level choices at disposal. The chosen library was Keras for ease of use and documentation available. As a conclusion to this section, the analysis performed were very disappointing and it was completely discarded as a new approach was discovered. This new solution had far more promising results, even in the early stages and it will be discussed in the following chapter. 28 Chapter 5 - Complexity predictor based on regression functions As previously discussed in this paper, regression problems aim to estimate values based on previously recorded data. In automatic learning, they receive an input dataset and their goal is to predict real values not included in the input information. One approach to solve these kinds of problems is to design a solution using regression functions. The idea behind these functions is to assume that the data the problem is trying to predict follows a mathematical function, then by finding this function and solving it for any input data it will output the desired prediction as a result. In order to find the mathematical function, first you need to figure out the class of the mathematical function you want to use for generating the predictions, these classes are for example linear, polynomial or exponential among others. Once chosen a class, the idea is to find a curve equation inside this category of functions that best fits the input dataset, also known as the training data. This may be done in multiple ways, one of the most common approaches is to minimize the mean of the squared errors that the function produces on each of the inputs contained in the training dataset. The main idea is to define a generic function of the chosen category and fine tune the parameters it contains in order to minimize the previously mentioned error. For example, when treating regression problems and choosing the linear function class you would declare a generic linear equation curve as y = ax + b. Then the linear regression function would process the dataset of the particular problem and figure out the best value for the parameters aand b. Now to generate predictions for new values you need to solve the previous function substituting xwith the new input data, aand bwith the values outputted by the trained linear regression function and the result ywould be the prediction. It is important to note that the problem under evaluation in this section is a classification problem, as we need to determine the complexity order a given solution belongs to. At first sight regression is not the best approach to solve this problem but in reality complexity orders are closely related to mathematical functions, as they are expressed as curves. The idea behind this implementation is to take the measurements obtained from executing an user's solution as points in a grid and find the curve that describes them best. This is done by defining a set of complexity orders supported by the module, then training a regression function for each of them and selecting the one with the least errors generated while predicting the input data. We won't use regression functions in order to predict new data, as they usually are utilized but instead we will use 29 them to fit a curve to the current data and extract the order of the function that describes this curve. The implementation of the proposed system that is based in regression functions starts by defining a set of supported complexities, which will be the possible results of each categorization performed. The following list describes the considered orders in the code implementation as well as the functions used for each of them: ●Constant: y = a ●Logarithmic: y = a + b * log(x) ●Linear: y = a + b * x ●Linear Logarithmic: y = a + b * x * log(x) ●Square: y = a + b * x^2 ●Cubic: y = a + b * x^3 The implementation defines as the X variable the size that will serve as the input, and the Y variable as the execution time that will serve as the output value. The evaluation process then begins by fitting each of the previously described functions using regression, this outputs the unknown parameters as a result. Then using the new function obtained by substituting the parameters for their calculated values, the input variable X is fed again and the predicted results are stored. After obtaining this information the real Y data and the predicted Y data are used in order to calculate the residual sum of squares. This result is used to compare all the considered functions, choose the one with the least error as the best option and use its function class as the predicted complexity order of the evaluated solution. The only exception during this process is the constant complexity, in this concrete case the program fits a linear regression function using the input data and calculates the equation for the curve. Then it analyzes the slope of this curve, if it is lower than a predefined value, 0.1 for the current implementation, it evaluates the solution as constant. This check is performed before carrying out the previously described evaluation process, which gets skipped if the function is classified as constant. To finalize this section it is interesting to mention that smoothing the data before processing it was taken into consideration, like for example using the savgol_filter() as an initial transformation. The results observed using this kind of transformations were worse and precision was lost during the smoothing process so it was completely discarded during development. 30 Chapter 6 - Validation of the complexity predictor module based on regression The validation process of the clue module described in this paper has been carried out in two phases, an initial validation of the complexity prediction system and a second validation taking into account the whole execution flow of the clue module. In the first phase, the goal is to verify how precisely the predictor can generate the correct order of complexity of a real solution programmed by a user. In the second stage, the focus changes to the classification of the solution among the different types of TLE verdicts described at the beginning of this paper. For all of the validation process we will use real world solutions designed and implemented by users gathered from the internet in public domains. These solutions are developed to solve problems in the online judge ¡Acepta el reto! Also the datasets used to test these solutions are generated based on the problem statements in the same judge’s collection. Errors are calculated by strictly comparing if the predicted complexity order equals the expected one, but in some cases this may not be the only path to a successful classification. For example, given a solution of quadratic complexity to a problem whose worst accepted complexity is linear, let's suppose that the predictor program obtains a cubic complexity on the evaluation. The category obtained by the complexity order predictor is wrong but the obtained result from the clue module as a whole would be correct. Taking these results into account, the clue module would classify the solution as a wrong complexity TLE and give the right clue to the user. This is important as errors calculated during the validation process described in this chapter are strict, but calculating the useful error in this manner may better describe the actual precision of the module. 6.1 Generic validations In order to validate any complexity prediction system it is vital to perform the tests with data obtained from real world scenarios. Data gathered in this manner gives a better image of its performance when used in a real judge online as it is not perfect and contains noise alterations. The first step in this process is choosing a number of problems from an online judge, in this case we will use ¡Acepta el reto! It's also necessary to find multiple solutions for each of the chosen problems in order to validate the module with a variety of 31 algorithms with different execution costs inside the same complexity orders. To obtain the solutions first an exhaustive search is carried out online in github, this way it is possible to find a multitude of public solutions to problems of the chosen judge. After gathering enough problems, each with around seven different solutions and in different languages, a test case generator is needed for each of the problems. This program must be capable of generating valid input data for a chosen problem statement given a desired size as an input. To finalize this gather step, each solution must be compiled and executed with the generated test cases measuring their execution time, all these results are then stored in a text document for later use. After gathering all the real data necessary for the validation the rest of the process is fairly simple, it consists of processing all the collected data with the predictor module and measuring its performance. This is also a good moment to fine tune the classification algorithm taking into account the obtained results in order to maximize its precision. This first table below shows the problem extracted from the judge ¡Acepta el reto! It contains the problem id in the judge, its complexity order in bigO notation, the number of solutions obtained in Java and C++ and the hit percent in the predictions obtained by the classification algorithm. The errors obtained regarding the problem with id 140 should have returned a linear complexity but were predicted as constant. This is justifiable because the problem is in fact linear in respect to the number of digits of the input data but the maximum length defined by the problem is very small, this being nine digits. What this means is that the difference between executions of different input data sizes is too small for the complexity predictor to realize. # Nombre Complexity Nº Solutions Hit % C++ Java 140 Suma de Digitos O(N) 5 2 42% 151 ¿Es matriz identidad? O(N2) 3 3 100% 368 Cociendo huevos O(1) 5 1 100% 369 Contando en la arena O(N) 4 2 100% 32 to their judge. This way they would be able to obtain a large enough sample of real world data and use it in order to train an AI classifier model capable of surpassing the implementation explored in chapter 4. To finish this section and coming back to the internal complexity order predictor it could be interesting to increase the amount of single variable complexities considered in order to match all the complexities existing in most of the currently available online judges. 39 Chapter 8 - Bibliography 1. Buglione, L., Palomba, F., & Panichella, S. (2019, May). How Accurate Are Online Judges in Detecting Defects in Code Submissions?. In 2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering Education and Training (ICSE-SEET) (pp. 153-162). IEEE. 2. “Web-Based Online Judge System for Online Programming Education" by E. Correa, L. Fuentes, D. Florescu, and L. Popa.” 3. "A Study of the Measurement of Execution Time in Program Benchmarking" de Gaius Mulley y Jon Shapiro, publicado en la revista ACM SIGARCH Computer Architecture News 4. "Best Practices for Scientific Computing" de Wilson et al., publicado en la revista PLOS Biology. 5. Gómez Martín, Marco Antonio; Gómez Martín, Pedro Pablo. “Uso de software de gestión de concursos de programación para evaluación continua”. En: Marqués Andrés, Mercedes; Badía Contelles, José Manuel; Barrachina Mir, Sergio (eds.). JENUI 2013. Actas de las XIX Jornadas sobre la Enseñanza Universitaria de la Informática, Castellón, del 10 al 12 de julio de 2013. Castelló de la Plana: Publicacions de la Universitat Jaume I, 2013. ISBN 978-84-695-8051-6, pp. 293-300. 6. Turing, A. M. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society Series 2, 42, 230-265. 40