Kaggle Winners Walkthroughs: Santa 2024 - The Perplexity Permutation Puzzle with Team Hamiltonians

What this episode is about

Team Hamiltonians presents their winning solution for the Santa 2024 competition, focusing on a combinatorial optimization problem evaluated by a costly LLM. They discuss their unique search algorithm and lightweight neural network pruning method, highlighting their diverse backgrounds in data science, physics, and finance, which enabled efficient algorithmic implementation and optimization techniques.

Key takeaways

• When experts unite, algorithmic synergy shines—three minds, distinct paths, one winning solution!
• A lightweight CNN proving that sometimes, less is more—accuracy not in numbers, but in ranking!
• Forget blackboxes: neighborhood searches are the new optimizers, thriving on similarity like social media feeds.
• Pruning is the unsung hero—turning computational chaos into streamlined searches with finesse and flair.
• Restart mechanisms: like rebooting your brain after a mental block—essential for navigating local minima!

Who speaks in this episode?

• Team Hamiltonians (Host) · 14 min speaking

What is discussed, and when

1. 0:00 – 3:00: iterated local search method, JMA model, neural network based pruning, Santa 2024 competitions
2. 6:00 – 9:00: JMA model, CNN
3. 9:00 – 12:00: neural network based pruning, beam search

Notable quotes from "Kaggle Winners Walkthroughs: Santa 2024 - The Perplexity Permutation Puzzle with Team Hamiltonians"

• Huristic optimization techniques. It's an advantage in this competition I think. we also have a deep passion for Santa competitions as you see in the screen and would like to…

  about Santa 2024 competitions · at 1:24

• And that means neighborhood search is a still viable approach. Now also it was crucial to optimize search process to minimize the number of calls to the JMA model for scoring.

  about JMA model · at 2:33

• As applied making it well suited for maintaining the square coration with this neural network based pruning. our final search procedure was as follows. The new additions are highlighted in blue.

  about neural network based pruning · at 9:24

• This led to better results unfortunately at least by the competition's end. one major approach we tested was the beam search as it was maybe closer to genetic algorithm with…

  about beam search · at 10:53

• Yeah, conclusion to summarize our iterated ro search method enhanced by lightweight neural network was highly effective under the computational constraint.

  about iterated local search method · at 12:56

Who and what is mentioned in this episode?

Companies & orgs

• Hamiltonians — Company · Main speaker · 1 mention · first at 0:03
  Team presenting the winning solution in the Santa 2024 competitions.
  Maybe still of interest. Okay. So the background our team consists of three kagu competition ground masters each with a different professional background and is a data scientist at the tech company number is a PhD student in physics and.

Concepts & topics

• iterated local search method — Concept · Key argument · 1 mention · first at 2:55
  Core algorithm used by the team to solve the combinatorial optimization problem in the Santa 2024 competitions.
• JMA model — Concept · Framework · 2 mentions · first at 2:43
  Model used for scoring in the competition, crucial for evaluating solutions.
• neural network based pruning — Concept · Strategy · 2 mentions · first at 2:58
  Technique used to reduce computational costs by estimating scores of candidate solutions without full evaluation.
• CNN — Concept · Strategy · 1 mention · first at 8:59
  Lightweight neural network architecture used for pruning in the solution.
  Our model architecture was a one-dimensional resonant with sweet and excitation blocks where in sequences were embedded and the model was trying to minimize L1.
• beam search — Concept · Referenced work · 1 mention · first at 11:00
  Alternative search method experimented with but not used in the final solution.

Places & events

• Santa 2024 competitions — Event · Business focus · 1 mention · first at 0:08
  Competition where the team presented their winning solution involving combinatorial optimization.

Full transcript with timestamps

0:00 Then uh thank you for the introduction and on behalf of team Hamiltonians uh I will present our winning solution for the Santa 2024 competitions. Uh in this talk I will first uh briefly uh introduce our backgrounds then I will provide a summary of our solutions. A following that uh will explain the two key differentiators our search algorithm and the pruning method using a lightweight neural network. Uh finally I will touch on some experimental approaches that were not included in our final simulation but maybe still of interest. Okay. So the background uh our team uh consists of three kagu competition ground masters each with a different professional background and is a a data scientist at the tech company number is a PhD student in physics and I'm a qu at an investment bank uh but we share an expertise in a numerical analysis and notably all of us have participated in Japan and well-known

1:15 competitive programming contests. So this experience help us rapidly implement the algorithmic and huristic optimization techniques. It's an advantage in this competition I think. Uh we we also have a deep passion for Santa competitions as you see in the screen and would like to take this opportunity to express our gratitude to the admins of organizing it each year actually we've got to know each other on the Santa leaders I think and that's next is a solution overview um to briefly summarize the competition task.

2:03 Uh it was a combinatorial optimization problem where the objective function was computed by a LLM and the complexity calculation was a computationally very expensive and near blackbox u making it difficult to apply existing histic collisions or some uh program specific techniques. Uh however we assume that uh of course similar texts will likely have similar scores and that means uh neighborhood search is a still viable approach. Now also it was crucial to optimize search process to minimize the number of calls to the JMA model for scoring.

2:49 Well uh uh in essence our approach can be uh described as an uh iterated local search method enhance with uh neural network based pruning. So it we we improved the countless solutions through local approach and applied portions when reaching the local optima and also used the lightweight neural network to estimate the scores and promising candidate. Now while this sounds very simple in principle and I will now break down the details on each steps. Yeah, such algorithms uh our search process begin by generating the neighboring solutions based on the current best solution. We employed uh two types of operations. The first is just insertion uh moving a short world sequence to the different random positions and the other is uh finding already sold the subsequences within the solution and insert a short random sequences to it and resold the segment. Uh through the observations uh we notice that the store uh the salted

4:13 segment frequently appeared in good solutions uh leading us to exploit this property. uh this property is also uh mentioned in the cover discussion I think and yeah we we emulated the neighboring solution using these two operations and then applied the depths first search to for the hill climbing or greedy search and each neighbors was evaluated by JMA and if the candidate had a lower peroxy and current best solution. We accepted it and continued the search. We also introduced a flesh based DFS strategy and that allowing us to accept uh nonimproving solutions up to a certain limit to escape shallow local optima. Yeah, this method uh this DFS enable uh deeper and more effective local searches. uh despite that the operation itself are not too complex. I think uh it is effectively enhanced to include other many kind of neighborhood operations. Uh the the the the DFS acceptance ratio was that this pro uh

5:38 higher tolerance at the shallow depths and gradually tightening at the deeper levels. Um this uh this approach maybe resembles simulated unlaying in that it allows escaping the local optima on similar a smaller scale but this is uh deterministic search and kick strategy uh uh despite our enhanced deubs uh local optimize still a challenge uh to escape the we used a kick mechanism which applied a strong probation such as uh multiple London swaps or just a segment destructions. Uh since uh excessive probation sometimes made it impossible to return even to the known solutions.

6:34 Uh we implemented a restart mechanism to revert to the best solution when necessary. Uh here is just a example of score transition during the search. The xaxis represent the total such steps count and the y-axis shows the perplexity score for the program ID5. The local search steadily improves the score then under goss due to the cakes but it ultimately lees a better solution than before. Um to to improve the efficiency uh we also incorporated several additional techniques such as a terminations of local search and batch computation for gem obations and also casting of computed scores. the it is uh simply be used in the following search and but also used in the training of the pruning model that I will describe in the next sections. Uh at this uh at this stage I we have achieved a competitive result with only a few improvement left to the solutions if I remember correctly.

8:01 Next is neuron network based ping. Uh the key challenge was the high computational cost of scoring via JMA and although the completely replacing it with a distilled model seemed too difficult. We thought that uh detecting obviously poor candidate for only pling was somehat feasible and to achieve this we use uh lightweight uh one-dimensional CNN which was trained online during the search. uh the model uh did not need to predict the absolute scores accurately. Instead, it needed to maintain the correct rankings or the corrections among the candidate solutions.

8:59 uh our uh model architecture was a one-dimensional resonant uh with sweet and excitation blocks where in sequences were embedded and the model was trying to minimize L1 loss against the publicity actual publicity. The L1 ROS was chosen for its robustness as applied making it well suited for maintaining the square coration with this uh neural network based pruning. Uh our final search procedure was as follows. The new additions are highlighted in blue. Now since the uh neural network was trained online uh we applied an uh epion like strategy uh it keeps small number of random candidate to prevent biases in the training data and this over pruning method could significantly accelerate the search and allowing us to find the winning solution within two weeks or three weeks or so of the competition s and finally yeah I will briefly mention some approaches we experimented but did not included in our

10:32 final solutions um after achieving the winning score we can't yeah of course I continued exploring potential improvement yeah of course we didn't know it is a global optimum or best achievable score during the competition. But uh eventually I know this led to better results unfortunately at least by the competition's end. Uh one one major approach we tested was the beam search as it was maybe closer to genetic algorithm with local search. I mean that we we maintain the multiple solution candidly at the same time optimizing them while preserving diversity using some criteria such as the edge entropy or size of longest common subsequences in each other. This method tries to search explore solution spaces.

11:37 So uh instead of the kicks expanding the film widths and search explorer more and more sol potential solutions may be more appropriate but yeah it's so it seems slow down the search again and we we also experimented with best for search instead of BFS but uh it appears it's sold down the search and additionally While we initially worried about the biases in the neuronet network training data, but it seemed to be a known issue and other yeah other standard optimization methods such as accumulated allaying and genetic algorithms and lymphos which was introduced in the public discussion were also tested.

12:36 But on result, it did not outperform ILS in terms of search speed and adaptivity in the search method improvements. Yeah, I mean it is so interesting to see other teams succeeded to obtain the best scores using these algorithms. Yeah, conclusion uh to to summarize our uh iterated ro search method enhanced by lightweight neural network was highly effective under the computational constraint uh by leveraging the observation of sort segment in good solution and also DFS based local search and kick probations. discovered the wide search space enough and furthermore the new uh lightweight uh estimator based pruning with casting and batch evaluations. Uh this all drastically reduce the cost of general scoring and leading us to our final solution efficiently. Yeah, this concludes my presentation and thank you for attention.

13:50 Uh, I'll be happy to answer any questions.

Questions about this episode

Who speaks in "Kaggle Winners Walkthroughs: Santa 2024 - The Perplexity Permutation Puzzle with Team Hamiltonians"?

Team Hamiltonians (Host).

What is "Kaggle Winners Walkthroughs: Santa 2024 - The Perplexity Permutation Puzzle with Team Hamiltonians" about?

Team Hamiltonians presents their winning solution for the Santa 2024 competition, focusing on a combinatorial optimization problem evaluated by a costly LLM. They discuss their unique search algorithm and lightweight neural network pruning method, highlighting their diverse backgrounds in data science, physics, and finance, which enabled efficient algorithmic implementation and optimization…

What is mentioned in this Kaggle episode?

7 people, works and ideas are mentioned, including iterated local search method, JMA model, neural network based pruning, Santa 2024 competitions, CNN, Hamiltonians. Each one on this page links to its own page with every episode that mentions it.

How long is "Kaggle Winners Walkthroughs: Santa 2024 - The Perplexity Permutation Puzzle with Team Hamiltonians"?

The episode runs 14 min; the transcript is about 1,514 words in 13 timestamped sections.

More from Kaggle

• All analyzed episodes
• People mentioned on Kaggle
• Topics mentioned on Kaggle