Generally AI - Season 2 - Episode 4: Coordinate Systems in AI and the Physical World

Turtle Robots and Logo (1940s-1967)

• The concept of a turtle robot is often used in robotics and programming, where a robot moves across a screen or physical space with a pen, allowing users to program movements and create drawings or patterns (11s).
• The Logo programming language, created by Seymour Papert in 1967, was based on this concept and used a physical moving plotter to teach programming (42s).
• The first turtle robots were invented by Grey Walter in the 1940s, using analog circuits as brains, and could perform tasks such as returning to a docking station when the battery was empty (1m24s).

Dewey Decimal System and Information Retrieval

• The Dewey Decimal System is a hierarchic classification system used in many US libraries for non-fiction books, with a range of numbers assigned to different subjects, such as history and geography (3m55s).
• Within the Dewey Decimal System, books about ancient history have call numbers in the range of 930 to 939, and books about ancient Egypt specifically have call numbers starting with 932 (4m19s).
• The use of coordinate systems and classification systems, such as the Dewey Decimal System, is relevant to AI and programming, as it allows for the organization and retrieval of information (2m29s).
• The discussion of coordinate systems and classification systems is part of a broader exploration of AI and programming concepts (2m24s).
• The process of finding information about a topic, such as ancient Egypt, can be done through various methods, including searching through a card catalog or asking a reference librarian for assistance (4m39s).
• A card catalog is an index that maps keywords to a call number or multiple call numbers, allowing users to locate physical books on a shelf (5m15s).
• University libraries in the US often use a classification hierarchy, such as the Dewey Decimal system, to assign call numbers to books and organize them physically on shelves (5m27s).
• The physical order of books on shelves typically matches their numeric order, making it easier to locate specific books (6m17s).

Information Retrieval in the 21st Century and AI

• In the past, searching for information required browsing through a card catalog or asking a librarian, whereas in the 21st century, internet searches and online resources like Wikipedia have become more common (7m3s).
• The rise of AI has led to the development of tools like ChatGPT, which can generate essays and answers to questions, but may not always provide accurate or reliable information (7m18s).
• ChatGPT's limitations include the need to cite sources and the potential for inaccuracies or made-up information, as it is only trained on available data (7m37s).
• To address these limitations, a new technology called Retrieval-Augmented Generation (RAG) has emerged, which combines the strengths of language models with the ability to retrieve relevant data before processing it (8m21s).
• RAG involves providing a language model with relevant text, such as the content of a history book, to improve its ability to answer questions or generate summaries (8m27s).
• However, RAG also raises the challenge of determining what content to provide to the language model (8m49s).
• The goal is to automate the process of finding relevant content in an electronic database, which is a task of information retrieval, and to scale it up to make it more efficient (8m54s).

Retrieval-Augmented Generation (RAG)

• The concept of RAG (Retrieval-Augmented Generation) is introduced, which involves automatically assigning a call number to an LLM prompt, allowing for direct retrieval of relevant books (9m36s).
• An encoder is used to map an arbitrary blob of text into a point in a vector space, with the requirement that points near each other in the space represent texts with similar meanings, known as an embedding (10m5s).
• The encoder is applied to the prompt and to all the books in the universe, resulting in vectors for each, and the vectors close to the prompt vector are retrieved (10m30s).
• The problem of encoding data is discussed, specifically the use of BERT as the encoder, which results in a 768-dimensional embedding vector, making it challenging to define what it means to be nearby in this space (10m57s).
• The concept of distance functions is introduced, and the need for a similarity measure, such as cosine similarity, to determine the similarity between vectors in the embedding space (12m21s).
• The dot product, also known as the inner product, is explained as a way to calculate the similarity between two vectors, and its geometric interpretation is described as the length of the first vector times the length of the second vector times the cosine of the angle between them (12m35s).
• The cosine of the angle between two vectors can be calculated by dividing the dot product by the length of the two vectors, resulting in a value between -1 and 1, where 1 means the vectors are pointing in the same direction and -1 means they are pointing in opposite directions (13m21s).
• Cosine similarity is a measure of how similar two vectors are, with a value closer to 1 indicating that the vectors are more similar, and is used because the magnitude of the vectors is not important, only their direction (13m51s).
• In high-dimensional spaces, the Curse of Dimensionality occurs, where points are concentrated near the surface of a sphere, making the magnitude of vectors less important and the direction more important (14m38s).
• The dot product can be used as a shortcut to calculate cosine similarity because the magnitudes of vectors in high-dimensional spaces are often similar, and GPUs are efficient at calculating dot products (15m45s).
• The original RAG paper used maximum inner product search, which involves calculating the dot product of a query vector with all document vectors and selecting the ones with the largest dot product (16m18s).
• The problem with this approach is that it requires calculating the dot product against every document for each new prompt, resulting in linear complexity, which is inefficient for large libraries (16m40s).
• A better way to search is needed, with a complexity of log(n) being more desirable, similar to index search in a database (17m5s).
• Nearest neighbor search is a well-studied problem that can be solved using approximate or exact nearest neighbors, with the former being a subset of the latter (17m15s).
• A space partitioning tree and branch and bound algorithm can be used for nearest neighbor search, resulting in an average complexity of log in, although this is not guaranteed (17m31s).
• In lower dimensional spaces, this strategy is usually better, but it's not guaranteed to achieve log in complexity (17m46s).
• Approximate nearest neighbor search (ANN) is used in many applications, including those at scale, and has different trade-offs between speed, quality, and memory usage (18m15s).
• Quality in ANN is measured using metrics like recall, which refers to the percentage of relevant results retrieved by a query (18m37s).
• Hierarchical Navigable Small World (HNSW) is a popular algorithm for ANN that uses a graph-based approach and is used in many vector databases (18m56s).
• HNSW is a unique graph with low average shortest path length and high clustering coefficient, making it navigable and hierarchical (19m39s).
• The algorithm uses a decentralized greedy search algorithm to achieve logarithmic scaling and is used to find nearest neighbors in a given space (19m53s).
• The concept of HNSW can be analogized to library stacks and pyramids, with multiple boxes or layers representing different levels of density (20m24s).
• Some libraries, like the engineering library at North Carolina State University, use robots to retrieve books from the stacks, similar to how HNSW navigates through a graph (20m43s).

Coordinate Systems and Map Projections

• The most popular format for representing a map and location in software is WGS84, but there are many ways to do so, and the choice of coordinate system can be important for user data and finding locations.
• The history of coordinate systems is longer than just computers, as people have wanted to know who owned what land and how to get somewhere for a long time.
• There are different ways to project a map, including projecting a sphere onto a cylinder, cone, or flat disc, each with its own compromises, such as preserving angles or sizes.
• The Mercator projection, used by Google Maps, preserves angles but distorts sizes, making Greenland appear larger than it actually is compared to Australia.
• The Gall-Peters projection, also known as the equal area projection, preserves the proportional relationships between areas on the map and the Earth.
• Azimuthal equidistance projections preserve distances from the center of the map, making them useful for navigation, and are used for the emblem of the United Nations.
• Different countries have chosen different projections for their national mapping agencies, such as the Ordnance Survey in the UK.
• The Ordinance Survey Meridian was chosen in 1801, 50 years before the newer prime meridian was released, and it is now two prime meridian switches away from the current one (26m9s).
• The Ordinance Survey Maps are still used today, possibly for determining land ownership, and they have a different prime meridian line than the current one (26m25s).
• The use of different prime meridians can cause confusion, especially when comparing old documents to GPS coordinates (27m27s).

RD Coordinate System in the Netherlands

• The Netherlands uses a national triangle coordinate system called RD coordinates, which is accurate in angles but not in distances (27m56s).
• The RD coordinates are in kilometers and meters, but one kilometer or meter on the map does not necessarily equal the same distance in the real world (28m39s).
• The center of the RD map is a church in Amersfoort, and the scale is 10 cm per kilometer, which is slightly too small (29m1s).
• The error in the RD coordinates increases towards the edges of the map, with a 10 cm error per kilometer in the center and an 18 cm error per kilometer near the coast (29m41s).
• The small size and flatness of the Netherlands make it possible to project the country in a flat way, which is why the RD coordinate system is used (30m12s).
• The Netherlands is a relatively flat country, which makes its coordinate system interesting, as it uses different landmarks than the triangle coordinate system (30m21s).
• The center of the triangle coordinate system is based on a church in Amersfoort, with X coordinates ranging from 0 to 280 km (from west to east) and Y coordinates ranging from 300 to 625 km (from south to north) (30m39s).
• The coordinate system in the Netherlands has the advantage that all coordinates are positive, and Y coordinates are always larger than X coordinates, which removes confusion about which coordinate is which (31m10s).
• This system is not widely used, mostly by people doing navigation challenges, scouting, or similar activities, but it has the advantage of clear distance measurements, unlike latitude and longitude (31m54s).

History and Development of Coordinate Systems

• The distance between one latitude or one longitude is different depending on the location on Earth, but there is a conversion to nautical miles (32m26s).
• The original development of the metric system involved taking the circumference of the Earth and making fractions of it to be the meter, but it did not work out as planned (32m53s).
• There are map systems that try to keep patches the same area, but this creates problems when moving from patch to patch, as coordinates or routes may not map to the same place on another patch (33m2s).
• The original map of the Netherlands was made between 1896 and 1926, and since then, more accurate mapping tools have been developed (33m34s).
• To correct for the differences between the old and new coordinate systems, the Netherlands has published a correction grid with corrections up to 25 cm on three different occasions (34m0s).

Border Disputes and Land Ownership

• The North Carolina and South Carolina border had to be adjusted about 10 years ago due to its ambiguity, resulting in some people waking up in a different state without having to move (34m24s).
• After World War II, the Netherlands considered taking some parts of Germany as compensation, but this plan was eventually abandoned, and the regions were returned to Germany (35m1s).

Smuggling and Tax Evasion

• Before the transition, big trucks would move into the villages with loads of goods such as geese and butter, taking advantage of a loophole to avoid paying taxes (35m41s).

Church Tower Coordinate System and Surveying

• The Netherlands uses a coordinate system based on the locations of church towers to measure angles, and a separate map for height above sea level, known as the New Amsterdam ordinance (36m16s).
• This system uses screws on specific buildings to indicate points, and is also used in other Western European countries (36m35s).
• In high school, students used a similar system with surveying tools to create an accurate map of a field, measuring height differences and using a transit to ensure accuracy (36m45s).

High-Dimensional Space and Cosine Distance

• The fact that points in high-dimensional space are on a sphere and have similar magnitudes was a new and interesting discovery (37m49s).
• Adding more dimensions to a high-dimensional space could potentially provide more storage space, but this would also affect the assumption of cosine distance (38m11s).

Post Office Horizon System Scandal

• The UK's Post Office adopted a bookkeeping system called Horizon by Fujitsu, which was plagued with bugs, resulting in incorrect transactions and balances, and postmasters were sued for the shortfalls despite the system's errors (38m43s).
• The Horizon system allowed remote logins, enabling Fujitsu to change balances without the postmasters' knowledge, leading to prosecutions and criminal convictions for the postmasters (39m11s).
• A drama series called "Mr Bates versus the post office" tells the story of the impact of the software on individuals and the lengths companies will go to hide the impact of bugs (39m52s).
• The Post Office scandal is still not fully resolved and has ruined the lives of many sub-postmasters over the last 20 years (40m42s).

Township and Range System in the US

• The US uses a system called township and range to describe property in legal documents, which was invented by Thomas Jefferson after the Revolution (41m43s).
• The township and range system involves dividing land into a grid and subdividing it into smaller sections, with descriptions of property including the township, range, and section numbers (42m1s).
• Surveying was a high-status job in colonial days, with notable figures such as George Washington and Thomas Jefferson working as surveyors or designing buildings (42m42s).

Importance of Mapping in History

• The age of the Enlightenment and Renaissance was a significant period in history, marked by notable men and their achievements (42m53s).
• During this time, having good mapping skills was crucial for navigation, particularly for sailors who needed to find their way back home (42m57s).
• The ability to map and understand one's surroundings was also essential for travelers on land, as not knowing the location of roads or villages could hinder their journey (43m6s).