Upgrade to Pro — share decks privately, control downloads, hide ads and more …

WebValley 2022 Python Programming

WebValley 2022 Python Programming

Support Slides for the Python Programming Course for the FBK WebValley Summer School 2022 (https://webvalley.fbk.eu)

Valerio Maggio

July 20, 2022
Tweet

More Decks by Valerio Maggio

Other Decks in Programming

Transcript

  1. Materials Shout out to Giuseppe Mastrandrea 
 (GH @giuseppemastrandrea) •

    Lecture materials for this class has been adapted from https://github.com/WebValley2022/python-programming
  2. Introduction The Programming Game The Program 👩💻 🧑💼 The Programmer

    The User uses 
 (i.e. coding) provides generates Output data The WebValley Team Input data • So a Program: • asks the user for some input data • makes some computations • returns a value or a series of values passed to Programming Language to create
  3. Quick Check and Recap • Q: What is Python? •

    A: Programming language • Q: What is a program? • A: A program is a software that resolves a particular task/problem • Key Components: • User • Input data • Output data • (soon) Algorithm!
  4. The Problem What we’ll work on for the next hours

    • We will implement an innovative Pokémon Search Engine • iow, our software program will look for the K top Pokémon that are most similar to some input Pokémon characteristics (i.e. the search query) • The search query (i.e. input data to our program) will be some characteristics (numbers) denoting a Pokémon
  5. The Problem • Q: What do we mean by "most

    similar to the search query” ? • Q: What kind of data can a user provide to our program ? • Q: (once we’ve clari f ied this) 
 what are the instructions to actually solve the problem? • The problem is: 
 “(somehow) determine what Pokémons are most similar to a speci f ied set of characteristics denoting a Pokémon provided by the user.” • There's a lot of ambiguity in what we just said
  6. The Algorithm • The algorithm is the heart of our

    software • Input Data (search query given by the user). A series of numbers representing a Pokémon: • HP (Hit Points) • Speed • Attack • Defense • Special Attack • Special Defence • The search query then will be a series of numbers • Based on those numbers, the program will return (output data) A list of K Pokémons • K is a parameter of the algorithm
  7. The Program Pokémon Search Engine K 
 (Parameter) HP (Hit

    Points) Speed Attack Defense Special Attack Special Defence Input Data // Search Query // Pokémon The Program
  8. How to Proceed? • Breaking down a problem into many

    small sub-problems (i.e. Tasks) • For example: 
 Problem: “start from a bunch of numbers and extract K Pokémons according to certain similarity measure” • What will our algorithm do? • Search for the K Pokèmon with the highest “similarity” • Breakdown into Tasks • Compare the data inserted by the user and those of existing Pokémon • Generalisation -> compare any pair of Pokémon • Sort the results of the comparison • Return the top K
  9. How to Proceed? • Task 1: • Ask the user

    for Pokémon data and store them accordingly • Task 2: • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  10. Let’s get cracking! • Task 1: • Ask the user

    for Pokémon data and store them accordingly • Task 2: • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  11. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  12. Task 2 2 Similarity Function • What can we use

    to compare two series of numbers? • A Pokémon with these scores (user's inputs) should be compared with all the other existing Pokémons • So.. time to acquire some Pokémon Data • CSV f ile (Comma Separated Values) with all data from all generations of Pokemon • Task 2.a.1: Read and Store Pokémon Data
  13. Get Pokemon Dataset • I am going to add the

    data to the repository • Q: What’s the git command I am going to type in ? • Once done, here is how to get a copy of the data • git pull origin main
  14. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  15. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  16. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  17. Task 2 2.b Similarity Function 30 43 55 68 78

    39 45 58 60 80 Bulbasaur Ivysaur Venusaur Chameleon Chameleon Charizard • What function to get a similarity degree? • Hypothesis: let's start from just 1 feature (e.g., hit points)
  18. Task 2.b Introducing Tuxemon 30 43 55 68 78 39

    45 58 60 80 Bulbasaur Ivysaur Venusaur Charmeleon Chameleon Charizard Tuxemon 64 K=1: Ivysaur K=2: Ivysaur, Charmeleon K=3: Ivysaur, Charmeleon, Charizard
  19. Task 2 2.b Similarity Function • Let's add another attribute

    (attack) • We still have to compute a distance • In this case we calculate the distance on a 2D plane 40 53 65 78 90 30 43 55 68 80 54, 55 78, 84 58, 64 39, 52 80, 82 60, 62 45, 49
  20. Task 2 2.b Similarity Function • Euclidean distance • We

    use Pythagoras Theorem • The distance is the green line (hypotenuse) of the triangle in f igure
  21. Task 2 2.b Similarity Function Adding more axes on our

    chart makes our formula slightly more complex 3 Dimensions (HP, Attack, Defence): 4 Dimensions (HP, Attack, Defence, Special Attack): n Dimensions:
  22. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  23. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  24. Let’s get cracking! • Task 1: ✅ • Ask the

    user for Pokémon data and store them accordingly • Task 2: ✅ • (+1) Read all Pokémon data and store accordingly • De f ine the Pokémon Similarity Function • Compute similarity between the search query and existing Pokémon • Return the top K most similar Pokémon • Task 3: • Return and Show algorithm’s output • (what will be the algorithm output?)
  25. Bonus Track • Visualise Results: • Using Jupyter we can

    show images of the K nearest Pokémon! • Visual feedback • Images taken from https://veekun.com/dex/downloads and rescaled